두 개 스택으로 큐 구현하기

큐에서 디큐한 후에 남는 공간을 비워두지 않기 위해 원형 큐를 사용할 수 있는데, 스택으로 큐를 구현하는 방법도 있다. 여기서는 스택 두 개를 이용해서 큐를 구현하는 방법을 살펴본다.

먼저 큐 구조체의 정의를 살펴보자. (요소의 타입(typedef ... element)은 스택에서 정의된다.)

typedef struct queue_t { 				// 큐 타입
	stack_t instack;
	stack_t outstack;
} queue_t;

그러면 큐의 연산들은 다음과 같이 정의된다.

• init_queue: 두 개의 스택을 초기화한다.
• transfer: instack의 것을 pop하여 모두 outstack으로 옮겨 push한다. 
• enqueue: 요소를 instack에 넣는다. instack이 꽉차있으면 ERROR.
• dequeue:  outstack이 비어있으면 transfer를 한다. outstack에서 pop하고 그 요소를 리턴한다. 비어있으면 ERROR.

void transfer(queue_t* q)
{
	while (!is_empty(&q->instack))
		push(&q->outstack, pop(&q->instack));
}

transfer는 outstack이 비어있을 때 instack의 것을 pop 해서 push로 가져온다. transfer는 outstack이 비었을 때, instack의 것을 남기지 말고 모두 가져와야 순서가 LIFO를 만족한다. 항상 outstack이 비었을 때 transfer를 하므로 instack의 것을 가져오는 중간에 outstack이 풀이 될 가능성은 없다. 여기서 &q->instack처럼 앞에 &를 붙인 이유는 is_empty가 스택의 포인터를 받기 때문이다. q가 가진 instack은 객체이므로 포인터로 바꾸어 넘겨야 한다. 즉 q 객체는 내부에 스택 객체 두 개를 가지고 있다. (->가 &보다 우선순위가 높으므로 &(q->instack)이라고 쓰지 않고 &q->instack이라고 써도 같다)

 

void enqueue(queue_t* q, element item)
{
	if (is_full(&q->instack)) {
		printf("ERROR: QUEUE full\n");
		exit(1);
	}
	push(&q->instack, item);
}

enqueue에서는 항상 instack으로 push함을 주의하자. instack이 비어있으면 push할 수 없다.

element dequeue(queue_t* q)
{
	if (is_empty(&q->outstack)) {
		transfer(q);
	}
	if (is_empty(&q->outstack)) {
		printf("ERROR: QUEUE empty\n");
        exit(1);
	}
	return pop(&q->outstack);
}

dequeue는 outstack이 비어있을 때 transfer를 부른다. (그래야 LIFO 두 번으로 FIFO 효과를 낼 수 있다.) trasfer를 했는데도 outstack이 비어있다면 큐가 비어있는 것이다.

이렇게 정의된 큐는 MAX_STACK_SIZE 개 만큼의 요소를 저장할 수 있다. 최악의 경우 반 밖에 사용하지 못하지만 비어있는 공간이 그 이상으로 늘어날 걱정은 하지 않아도 된다.