- Queue 는 선입선출의 데이터 구조이다. First - in First - out
- 앞에서 나가고, 뒤에서 들어오는 구조이므로, insertion 은 항상 rear 즉 뒤에서 일어나고, deletion 은 늘 앞에서 즉 front 에서 일어난다.
- 큐의 활용 예로는, 공항에서 이륙을 기다리는 비행기열, provider 의 명령을 임시 저장하는 Buffer 등이 있다.
- Queue 를 linear 하게 사용할 경우 발생되는 문제가 있다. 만약, 길이가 5인 배열에서, front 가 4이고 rear 가 5이라고 가정해 보자. front 는 더 이상 앞으로 갈 수가 없다. 빼는 것만 가능하니까. 그럼 메모리 여유 공간이 충분함에도 불구하고 데이터를 더이상 넣지 못하는 비효율성이 발생하게 된다.
- 따라서 linear queue 는 불가능하다.
- 개발자가 되면, 늘 memory consumption 과 power consumption 사이의 tradeoff 관계에서 고민해야 한다. 모바일 같이 작은 기기에서는 메모리보다 power 를 더 많이 쓰는 게 중요할 수도 있고, pc 에서는 power 보다는 메모리가 더 중요할 수 있다.
- Circular queue 로 linear queue 의 문제를 해결할 수 있다.
- Circular queue 에서도 front 와 back 을 사용한다. 주의할 건, back 의 경우 마지막 요소의 주소 그 자체를 가리키지만, front 의 경우 첫 번째 요소 하나 전의 노드의 주소를 가리킨다는 점이다. (그래야 front 와 back 이 서로 같아지는 상황을 미연에 방지할 수 있다.)(초기화일 때 제외)
- Circular queue 에서 Empty 는, rear 와 front 가 서로 같은 주소일 때를 의미한다. 한편 full 은 front % (배열 길이) 와 rear 에 1을 더한 수를 배열 길이로 나눈 나머지가 서로 같을 때를 의미한다. (즉 front 와 rear 가 서로 인접한 위치에 있을 때 큐가 full 하다고 이야기 한다.)
- Circular queue 에서 유의해야할 점은, 큐에 여유공간이 하나도 없으면 안된다는 것이다. 그렇게 되면, front 와 full 이 가리키는 주소가 같아져버리기 때문에 초기의 빈 상태인지 가득 찬 상태인지 구별할 수 없다. 따라서circular queue 에서 full 하다는 것은 하나의 여유공간을 남겨둔 상태를 뜻한다.
- void enqueue(QueueType *q, element item)
- 먼저 큐가 꽉 찬 상태라면, 에러 메시지를 생성해야 한다.
- q→rear 에 그 다음 인접한 노드의 주소를 넣어준다. 이때 나머지 연산을 이용한다. (q→rear+1) % 큐 길이
- q→queue[q→rear] = item 을 넣어준다.
- dequeue(QueueType *q)
- 먼저 큐가 빈 상태라면, 에러 메시지를 생성해야 한다.
- q→front = (q→front+1) % 큐의 길이 front 를 한 칸 뒤로 이동시킨다.
- Linked Queue 는 링크드 리스트로 연결된 큐를 말한다.
- front 는 첫 번째 노드의 주소를 저장하고, rear 는 마지막 노드의 주소를 저장한다. 만약 큐가 비었을 때는 둘 다 NULL 값을 가진다. 다시 한 번 기억하자. front 는 deletion, rear 는 insertion 을 담당한다.
- enqueue(QueueType *q, element item)
- malloc 을 이용해서 item 을 저장할 새로운 노드 한 개를 생성한다.
- 만약 temp 즉 새로할당된 메모리 주소가 null 이라면 메모리 주소 할당 오류를 반환한다.
- temp→item 에 item 을 넣어주고, temp→link 에는 NULL 을 넣어주어 새로운 노드에 값을 넣어준다.
- 만약 queue 가 빈 큐라면, q→front, q→rear 모두 temp 로 설정한다.
- 아니라면, q→rear→link = temp, q→rear = temp 를 해주어 큐의 rear 에 값을 넣어준다.
- dequeue(QueueType *q)
- QueueNode 타입의 주소를 저장하는 temp 변수를 만들고, 거기에 p→front 즉 front 가 가리키는 노드의 주소를 임시 저장한다.
- 만약 queue 가 비어있다면, 에러 메시지를 반환한다.
- element item 변수를 만든 다음, temp→item 즉 head 의 item 을 담는다.
- q→front = q→front→ Link 를 담는다. 만약 이렇게 만들었을 때, q→front 가 NULL 이라면, 즉 원소 한 개만 있었던 것을 지운 상태라면, rear 도 NULL 로 설정해 두어, 빈 배열이라는 것을 알려야 한다.
- 그 다음, temp 에 저장해 두었던 front 를 제거해 준다.
- double-ended queue (Deque) 는 삽입은 rear 에서, 삭제는 front 에서만 가능했던 circular queue 와 달리, front 와 rear 모두에서 삽입과 삭제가 가능하다.
