큐(Queue)

개념

컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식, 나중에 집어넣은 데이터가 먼저 나오는 스택과는 반대되는 개념

 

구현

큐(Queue)는 연결리스트(Linked List)로 구현이 가능하다.

연결리스트란, 각 노드가 데이터와 포인터를 가지고 있고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조

단점

poll해도 메모리가 비어지는 것이 아니라 값이 들어 있던 부분에 null이 들어가고 front위치만 뒤로 옮겨 지기 때문에 추가로 offer하려고 하면 overflow가 발생한다. 이 단점을 보완한 것으로 원형큐 or 환영큐가 있다.

 

Java 라이브러리 - 큐(Queue)

Java 라이브러리에서 큐(Queue)의 메소드는 2가지 종류로 나눌 수 있다.

1. 예외발생(Throws exception) 메소드
   • add(e)
     - 용량 제한을 위반하지 않고 즉시 수행할 수 있는 경우 지정된 요소를 큐에 삽입, 가능한 공간이 없는 경우 성공시 true 리턴하고 lllegalStateException을 발생
   • remove()
     - 큐의 맨 앞 값을 얻고 삭제한다.
   • element()
     - 큐의 맨 앞 값을 얻지만 삭제하지는 않는다. 
2.  특수값 리턴(Returns special value) 메소드
   • offer(e)
     - 용량 제한을 위반하지 않고 즉시 가능한 경우 지정된 요소를 큐에 삽입
   • poll()
     - 큐의 맨 앞 값을 얻고 삭제한다. 큐가 비어있는 경우는 null을 리턴
   • peek()
     - 규의 맨 앞 값을 얻지만, 큐가 비어 있지 않은 경우는 null을 리턴

1.  

Java 라이브러리 큐(Queue) 사용 방법

큐(Queue)를 제네릭 형태로 사용할 때 큐를 구현한 클래스를 생성해서 사용

• LinkedList
  • 요소에 null 허용
  • FIFO
• PriorityQueue 
  
  • 요소에 null 허용 불가
  • 힙 데이터 구조를 기초로한 우선순위 큐
  • 구성 시간에 지정된 순서에 따라 요소를 정렬

References

https://docs.oracle.com/javase/tutorial/collections/implementations/queue.html

Queue Implementations (The Java™ Tutorials > Collections > Implementations)

https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html

Queue (Java Platform SE 7 )

https://ko.wikipedia.org/wiki/큐_(자료_구조)#연결_리스트로_구현한_큐_(링크드_큐)

큐 (자료 구조) - 위키백과, 우리 모두의 백과사전