[Theory] Queue
23 Feb 2022큐(Queue)
선입선출(First In First Out)의 특성을 가지는 자료구조로 Stack과 반대의 개념을 가진다. 한 쪽 끝에서는 자료의 삽입연산만 가능하고 반대쪽 끝에서는 삭제만 가능한 구조이다.
큐의 연산종류
- Enqueue : 큐의 가장 마지막에 데이터를 추가합니다. (입력연산)
- Dequeue : 큐의 가장 맨 앞 데이터를 삭제하고 반환한다. (출력연산)
- Peek : 큐가 비어있지 않을 경우 맨 앞 데이터를 반환한다. (조회연산)
시간의 시간복잡도
큐 데이터를 삽입하거나 제거시 삽입의 경우 Front에서만 일어나고 제거의 경우 Rear에서만 일어난다. 그러므로 삽입과 삭제에 소요되는 시간복잡도는 O(1)이다. 조회는 특정 데이터를 찾을 때까지 수행해야 하므로O(n)의 시간복잡도를 가진다.
큐의 구헌
Java에서는 Stack과 동일하게 Collection 클래스로 구현 되어있다.
QueueNode
Queue의 노드객체
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class QueueNode<T> { | |
| T item; | |
| QueueNode next; | |
| public QueueNode(T item){ | |
| this.item = item; | |
| this.next = null; | |
| } | |
| } |
QueueList
Queue의 연산클래스
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class QueueList { | |
| /* Queue의 front 객체 */ | |
| QueueNode<T> front; | |
| /* Queue의 rear 객체 */ | |
| QueueNode<T> rear; | |
| /* Queue의 삽입로직 */ | |
| public void enqueue(T item) { | |
| QueueNode<T> node = new QueueNode(item); | |
| /** | |
| * Queue가 비어있을 경우 front와 rear에 방급 입력된 데이터를 넣는다. | |
| * front와 rear에는 같은 주소값의 node가 들어가므로 값을 공유한다. | |
| */ | |
| if(isEmpty()){ | |
| front = node; | |
| rear = node; | |
| return; | |
| } | |
| /** | |
| * Queue의 rear의 next에 데이터를 넣어 rear과 연결해준다. | |
| */ | |
| rear.next = node; | |
| rear = node; | |
| } | |
| /* Queue의 출력로직 */ | |
| public T dequeue() { | |
| if(isEmpty()) { throw new NoSuchElementException("Queue Empty!!"); } | |
| T item = peek(); | |
| front = front.next; | |
| if(front == null){ | |
| rear = null; | |
| } | |
| return item; | |
| } | |
| /* Queue의 조회로직 */ | |
| public T peek(){ | |
| if(isEmpty()) { throw new NoSuchElementException("Queue Empty!!"); } | |
| return front.item; | |
| } | |
| public boolean isEmpty(){ | |
| return (front == null); | |
| } | |
| } |