Queue(큐)
먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First in First Out) 구조
나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념
영어 단어 queue: 표를 사러 일렬로 늘어선 사람들로 이루어진 줄
- 사용 예시
프린터의 출력 처리, 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황
사진출처: 위키백과
용어
insert or put or Enqueue: 큐에 자료를 넣는 것
delete or get or Dequeue: 큐에서 자료를 꺼내는 것
front or head: 데이터를 get 할 수 있는 위치
rear or tail: 데이터를 put 할 수 있는 위치
Overflow: 큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우
Underflow: 큐가 비어 있어 자료를 꺼낼 수 없는 경우
원형 큐(circular Queue)
사진 출처: <파이썬 알고리즘 인터뷰> p.260, 책만, 2020
기존의 선형 Queue는 공간이 꽉 차게 되면 더 이상 추가할 수 없다는 단점을 보완한 재활용이 가능한 구조를 가진 Queue
큐를 쓰다보면 배열의 앞 부분이 비게 되는 것을 활용해서 큐의 마지막 부분을 쓰면 다시 처음부터 큐를 채우는 형태의 큐
Enqueue를 하면 rear의 위치를 하나 뒤로 이동
Dequeue를 하면 front의 위치를 하나 뒤로 이동
rear와 front의 위치가 같을 경우는 큐가 완전히 비어 있을 경우와 큐가 모두 찼을 때 2가지 경우가 있어 구현 시 해당 부분을 잘 구현 해야한다.
Deque(Double Ended Queue)
양방향에서 데이터의 삽입, 출력이 가능한 형태의 Queue
스택과 큐의 특징을 모두 가지고 있어 필요에 따라 사용이 가능
사진 출처: https://www.geeksforgeeks.org/implement-stack-queue-using-deque/
Deque는 배열, 연결 리스트로 구현이 가능하지만 위 그림처럼, 이중 연결 리스트로 구현하는 것이 가장 좋다.
데이터의 양 끝을 head, tail로 지정하고 데이터를 삽입할 땐 연결만 시키고 head나 tail 포인터를 이동시키면 된다. 삭제 또한 마찬가지
파이썬의 deque도 이중 연결 리스트로 구현 되어있다.
