[CLSR] 10.1 Stacks and queues (Ch.10 Elementary Data Structures)

스택과 큐는 제거 행위로 집합에서 제거될 원소가 미리 명시된 동적 집합의 일종이다.

 

스택은 후입선출(last-in, first-out; LIFO).

큐는 선입선출(first-in, first-out; FIFO).

 

구현에 다양한 방법이 있지만 여기서는 배열을 통한 구현을 다룬다.

---

Stacks

스택의 'Insert' 행위는 'Push'라 부르고 'Delete'행위는 'Pop'이라 부른다.

최대 $n$개의 원소를 가진 스택을 배열 $S[1 \cdots n]$으로 구현할 수 있다.

'$S.top$'은 가장 최근에 삽입된 원소의 배열에서의 인덱스를 나타내느 $S$의 속성(attribute)이다.

즉, 스택은 원소 $S[1 \cdots S.top]$을 가지고 있고, $S[1]$은 스택 최하단에, $S[S.top]$은 스택 최상단에 위치한다.

$S.top = 0$이면 스택에 원소가 없고 비어있는(empty) 상태로 본다.

'$Stack-Empty$'라는 쿼리 연산을 통해 스택이 비어있는지 확인할 수 있다.

빈 스택을 pop하려는 경우 stack underflow라 하고 에러 처리한다.

$S.top$이 $n$을 초과하는 경우 stack overflow라 한다.

스택과 관련된 연산들을 다음의 수도 코드로 나타낼 수 있다.(오버플로우 고려하지 않음)

• $Stack-Empty(S)$

if S.top == 0
	return TRUE
else
	return FALSE

• $PUSH(S, x)$

S.top = S.top + 1
S[S.top] = x

• $Pop(S)$

if Stack-Empty(S)
	error "underflow"
else S.top = S.top - 1
	return S[S.top + 1]

(a)에서는 스택 S가 네 원소를 가지고 있고 최상단 원소는 9이다. (b)에서는 Push(S, 17)과 Push(S, 3)이 수행되었다. (c)에서는 Pop(S)가 수행되었고 3이 return되었다. 배열 자체에 3은 남아있지만 스택에 존재하지는 않는다. (CLRS p.233)

위 그림에서는 Push와 Pop 연산을 보여준다. 각 연산은 $O(1)$이 걸린다.

---

Queues

큐에서는 'Insert'연산을 '$Enqueue$'라 하고 'Delete'연산을 '$Dequeue$'라 한다.

큐의 FIFO 특성은 은행에서 대기표를 받고 기다리는 손님들과 비슷한 방식으로 비유할 수 있다.

큐는 head와 tail을 갖는다.

원소가 enqued되면 줄 선 손님처럼 tail로 자리 잡는다.

원소가 dequed되면 맨 앞의 손님처럼 head의 원소가 dequed된다.

(a)에서는 배열 Q[1 .. 12]에서 Q[7 .. 11]에만 다섯 개의 원소를 가지고 있는 큐를 보여준다. (b)에서는 Enqueue(Q, 17), Enqueue(Q, 3), Enqueue(Q, 5)를 수행한 다음이다. (c)는 Dequeue(Q)를 수행하여 15를 반환한 직후이다. (CLRS p.234)

최대 $n-1$개의 원소를 갖는 큐는 배열 $Q[1 \cdots n]$을 통해 구현할 수 있다.

$Q.head$는 head를 가리키는 인덱스이고 $Q.tail$은 tail을 가리키는 인덱스이다.

tail은 다음 원소가 들어오게 될 위치를 가리키고 있다.

큐의 원소는 $Q.head$, $Q.head + 1$, ... , $Q.tail - 1$에 위치하고 순환하는 형태로 위치가 이어진다.

$Q.head = Q.tail$인 경우 큐가 비어있는 상태이다. 초기에는 $Q.head = Q.tail = 1$이다.

빈 큐에서 dequeue하는 경우 queue underflow이다.

$Q.head = Q.tail + 1$인 경우 큐는 꽉 찬 상태이다. 꽉 찬 큐에 enqueue 하는 경우 queue overflow이다.

다음은 큐의 각 연산들에 대한 수도코드이다(오버플로우, 언더플로우 고려하지 않음).

각 연산들은 $O(1)$이 걸린다.

• $Enqueue(Q, x)$

Q[Q.tail] = x
if Q.tail == Q.length
	Q.tail = 1
else Q.tail = Q.tail + 1

• $Dequeue(Q)$

x = Q[Q.head]
if Q.head == Q.length
	Q.head = 1
else Q.head = Q.head + 1
return x