[자료구조] | 큐(Queue)

제롬·2022년 1월 17일
자료구조
0

자료구조

목록 보기
2/3

큐(Queue)란?

큐(Queue)란 양 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 삽입과 삭제의 위치가 제한적인 형태의 선입선출(First-In-First-Out) 구조를 갖는 선형 자료구조이다.


Java 라이브러리의 큐(Queue) 메서드 종류

자바 라이브러리의 큐 메서드에는 두가지 형태의 메서드가 있다,
첫째는 수행이 실패했을때 Exception을 발생시키는 메서드이고 둘째는 수행이 실패했을때 null 또는 false를 반환하는 메서드이다.

수행이 실패했을 때 Exception을 발생시키는 Queue 메서드

  • boolean add(E item)
    • 해당 item을 Queue에 삽입
    • 삽입에 성공하면 true를 반환, 삽입할 공간이 없는 경우는 예외발생(IllegalStatementException)를 발생시킨다.
  • E element()
    • Queue의 Head에 있는 item을 삭제하지 않고 해당 item을 반환한다.
    • 만약 Queue가 비어있으면 예외(NoSuchElementException)를 발생시킨다.
  • E remove()
    • Queue의 Head에 있는 item을 삭제하고 해당 item을 반환
    • 만약, Queue가 비어있으면 예외(NoSuchElementException)를 발생시킨다.

수행이 실패했을 때 null 또는 false를 반환하는 Queue 메서드

  • boolean offer(E item)
    • add(E)와 동일한 기능
    • 삽입에 성공하면 true를 반환하고 실패하면 false를 반환한다.
  • E peek()
    • element()와 동일한 기능
    • 만약, Queue가 비어있으면 null을 반환.
  • E poll()
    • remove()와 동일한 기능
    • 만약, Queue가 비어있으면 null을 반환.

큐(Queue)의 동작

선입선출 형식의 구조를 갖는다. 선입선출 형식 이란 아래 그림처럼 먼저 들어온 순서대로 나오는 방식을 말한다.

큐(Queue) 연산 종류

  • poll() : 리스트의 첫 번째 항목을 제거한다.
  • add(item) : item 하나를 큐의 가장 끝 부분에 추가한다.
  • peek() : 큐의 가장 앞에 있는 항목을 반환한다.
  • isEmpty() : 큐가 비어 있을 때 true를 반환한다.
  • size() : 큐에 들어있는 item의 개수를 반환한다.

큐(Queue)의 구현 방법

큐(Queue) 를 구현하는 방식에는 배열(Array) 을 이용해 구현하는 방식과 연결리스트(LinkedList) 를 이용해 구현하는 방식이있다.

배열(Array)을 이용한 구현의 장단점

  • [장점]
    • 배열 내 요소의 주소를 나타내는 인덱스를 통해 원하는 데이터를 빠르게 검색하여 접근가능
  • [단점]
    • 선언할 때 크기가 고정되어 배열에 들어있는 데이터 양에 따라 배열의 크기조정이 필요하다.
    • 데이터를 중간에 삽입하거나 삭제할 경우 해당 데이터 뒤에 있는 요소들의 위치를 모두 이동시켜야하는 비효율적인 상황이 발생.

연결리스트(LinkedList)를 이용한 구현의 장단점

  • [장점]
    • 데이터의 양에 상관없이 크기가 동적으로 조절된다.
    • 인덱스 대신 이전 데이터 그리고 다음 데이터의 위치를 기억하는 노드 형태를 이용한다. 따라서 리스트 중간에 데이터 삽입, 삭제시 노드들 사이에 연결된 링크들을 끊어주거나 이어주면 되기 때문에 그 과정이 용이하다.
  • [단점]
    • 데이터에 접근할 때 연결되어 있는 노드들을 따라 양 끝에서부터 순차적으로 접근해야하기 때문에 데이터 접근속도가 배열에 비해 느리다.

따라서, 모든 원소의 값을 필요로 하거나 중간 데이터를 삽입삭제할 경우 연결리스트, 특정 데이터에 접근하는것이 목적이라면 배열을 사용하는것이 좋다.


큐의 구현 - 연결 리스트로 구현한 큐

노드(Node) 구현

연결리스트로 구현된 큐에서 데이터와 데이터의 위치를 저장하는 노드(Node) 객체는 아래 그림과 같다.

연결리스트(LinkedList) 구현

위 그림같은 노드들을 연결한 형식이 아래 그림과 같은 연결리스트(LinkedList) 가 된다.

데이터 추가 구현

큐에서 데이터를 추가하는 기능은 offer() 또는 add() 에 의해 이루어진다. 데이터를 추가하는 동작은 아래 그림처럼 이루어진다.

먼저, 데이터를 추가할 노드를 생성하고 큐의 제일 마지막 노드와 연결한 후에 tail 노드를 새로 추가된 노드로 변경해준다.

데이터 삭제 구현

큐에서 데이터를 삭제하는 기능은 poll() 또는 remove() 에 의해 이루어진다. 데이터를 삭제하는 동작은 아래 그림처럼 이루어진다.

노드에 이어져있던 링크를 위 그림처럼 끊어버리는 방식으로 데이터를 삭제할 수 있다.


연결리스트(LinkedList)를 이용한 큐(Queue) 구현

class Node <E>{
    E data;
    Node<E> next; // 다음 노드의 주소를 가리키는 변수

    public Node(final E data) {
        this.data = data;
        this.next = null;
    }
}

public class LinkedListQueue<E> {
    private Node<E> head; // 큐에서 가장 처음 노드 객체를 가리키는 변수
    private Node<E> tail; // 큐에서 가장 마지막 노드 객체를 가리키는 변수
    private int size; // 큐에 담긴 요소의 개수

    public LinkedListQueue() {
        this.head = null;  
        this.tail = null; 
        this.size = 0; 
    }
    
    public boolean offer(final E e) {
        Node<E> newNode = new Node<>(e);

        if(size == 0){ 
        // 큐가 비어있을 경우
            head = newNode;
        }else{ 
        // 비어있지 않을경우 마지막 노드(tail)이 다음 노드(next)를 가리키도록 한다.
            tail.next = newNode;
        }

        tail = newNode;
        size++;

        return true;
	}

	public E poll() {
          if (size == 0) {
              // 삭제할 요소가 없다면 null 반환.
              return null;
          }

          // 삭제될 요소의 데이터를 반환하기 위한 임시 변수
          E element = head.data;

          // head 노드의 다음노드
          Node<E> nextNode = head.next;

          head.data = null;
          head.next = null;

          // head 가 가리키는 노드를 삭제된 head 노드의 다음노드를 가리키도록 변경
          head = nextNode;
          size--;

          return element;
	}
    
    public E peek() {
        // 요소가 없을경우 null 반환
        if(size == 0){
            return null;
        }
        
        return head.data;
	}
    
    public E element() {
        E element = peek();
        
        if(element == null){
            throw new NoSuchElementException();
        }
        
        return element;
	}
    
    public int size(){
		return size;
	}
    
    public int isEmpty(){
		return size == 0;
	}
    
}

offer() 는 큐의 제일 뒤에 데이터를 추가한다.
큐가 비어있다면 새 요소는 head이며 동시에 tail이 된다. 그렇기 때문에 head를 새 노드를 가리키도록 해야하고 그 외에는 tail이 가리키는 요소의 다음 노드(tail.next)를 새 노드를 가리키도록 한 뒤 tail을 새 노드로 지정한다.

poll()은 큐의 제일 앞에 데이터를 삭제하고 그 값을 반환한다.
만약, 큐가 비어있다면 null을 반환한다. 만약 비어있지 않다면 큐의 새로운 head는 삭제된 head 노드가 가리키던 다음노드(head.next)로 변경한다.


큐의 사용 - 버퍼

버퍼는 데이터를 한곳에서 다른 한곳으로 전송하는 동안 일시적으로 데이터를 보관하는 메모리의 영역이며 일반적으로 입출력 및 네트워크 관련 기능에서 이용한다.

순서대로 입력/출력/전달 되어야 하므로 FIFO방식의 큐가 이용된다.

큐의 사용 - 기타

큐는 데이터가 입력된 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

[큐의 활용 예시]

  • 너비 우선 탐색 구현(BFS)
    • 처리해야 할 노드의 리스트를 저장하는 용도로 큐를 사용한다.
    • 노드 하나를 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다.
    • 노드를 접근한 순서대로 처리할 수 있게 된다.
  • 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
  • 은행 업무
  • 프린터의 출력처리
  • 프로세스 관리
  • 윈도우 시스템의 메시지 처리기
  • 콜센터 고객 대기시간
  • 캐시(Cache) 구현

[Reference]
자바 - 연결리스트를 이용한 Queue 구현
자료구조-배열과 연결리스트의 장단점
포스트it의 개발자 도전기
Heee's Development Blog

profile
제롬
이전 포스트

[자료구조] | 자료구조(Data Structrue)

다음 포스트

[자료구조] | 스택(Stack)

0개의 댓글