queue
Q&A 정리: queue
Queue란 무엇인가?
큐는 먼저 들어온 데이터가 먼저 나가는(선입선출) 자료구조다. 은행 번호표 대기열처럼 먼저 온 사람이 먼저 서비스를 받는 원리와 같다.
Queue is a linear data structure that follows FIFO (First In First Out) Principle.
Queue에서 Front와 Rear는 각각 어디를 가리키며, Size와 Capacity의 차이는?
Front는 줄의 맨 앞(다음에 나갈 사람), Rear는 줄의 맨 뒤(가장 최근에 도착한 사람)를 가리킨다. Size는 현재 줄에 서 있는 사람 수이고, Capacity는 줄이 수용할 수 있는 최대 인원이다.
- Front / Head: Position of the entry in a queue ready to be served, that is, the first entry that will be removed from the queue, is called the front of the queue. It is also referred as the head of the queue.
- Rear / Back / Tail: Position of the last entry in the queue, that is, the one most recently added, is called the rear of the queue. It is also referred as the tail of the queue.
- Size: Size refers to the current number of elements in the queue.
- Capacity: Capacity refers to the maximum number of elements the queue can hold.
Queue의 주요 연산과 시간복잡도는?
큐의 모든 기본 연산(넣기, 빼기, 맨 앞 확인, 크기 확인 등)은 데이터 양과 무관하게 일정한 시간 안에 완료된다. 줄이 아무리 길어도 맨 앞과 맨 뒤만 다루면 되기 때문이다.
Operations Time Complexity Space Complexity enqueue O(1) O(1) dequeue O(1) O(1) front O(1) O(1) size O(1) O(1) isEmpty O(1) O(1) isFull O(1) O(1)
Queue의 Enqueue/Dequeue 연산에서 overflow와 underflow는 각각 언제 발생하는가?
큐가 꽉 찬 상태에서 데이터를 넣으려 하면 overflow(넘침) 에러가, 비어 있는 상태에서 데이터를 빼려 하면 underflow(부족) 에러가 발생한다. 만석인 극장에 입장하려는 것, 빈 극장에서 퇴장하려는 것과 같다.
- Enqueue: Adds an element to the end (rear) of the queue. If the queue is full, an overflow error occurs.
- Dequeue: Removes the element from the front of the queue. If the queue is empty, an underflow error occurs.
- Peek/Front: Returns the element at the front without removing it.
- Size: Returns the number of elements in the queue.
- isEmpty: Returns true if the queue is empty, otherwise false.
- isFull: Returns true if the queue is full, otherwise false.
Deque(Double Ended Queue)란 무엇이며, 일반 Queue와 어떻게 다른가?
일반 큐는 뒤로만 넣고 앞으로만 뺄 수 있지만, Deque는 앞뒤 양쪽 모두에서 넣고 뺄 수 있다. 양쪽 문이 모두 열린 통로라고 생각하면 된다.
- Simple Queue: Simple Queue simply follows FIFO Structure. We can only insert the element at the back and remove the element from the front of the queue. A simple queue is efficiently implemented either using a linked list or a circular array.
- Deque (Double Ended Queue): The insertion and deletion operations, both can be performed from both ends.