[2기 대구 이현복] Data Structure - Stack & Queue

안녕하세요.

대구 멤버십 21기 이현복 입니다.

Data Structure중 세번째 주제인 Stack과 Queue에 대한 이야기 입니다

자료구조 중 Array와 List가 대부분의 자료구조의 기본으로 활용됩니다.

그 중 스택(Stack)과 큐(Queue)는 Array와 List의 일부 특성만을 강조하여

사용의 용이성과 효율성을 살린 형태라고 할 수 있습니다.

스택(Stack)은 한쪽 끝에서 삽입 삭제가 일어나는 자료구조입니다.

Last In First Out (LIFO) 구조라고도 합니다.

스택의 기본적인 연산으로는 create, push, pop, top 가 필요합니다.

create : 새로운 스택을 생성하는 함수

push : 최상위에 데이터를 추가하는 함수

pop : 최상위 데이터를 삭제하는 함수

top : 최상위 데이터를 참조하여 보여주는 함수

스택을 배열로 구현하면 다음과 같은 형태로 구성할 수 있습니다

stack 자체를 나타내는 배열이 필요하며

데이터가 존재하는 최상위 위치를 가르키는 포인터 top이 필요합니다.

즉 배열에 포인터 하나만 있다면 스택을 만들 수 있다는 이야기 입니다.

Stack CreateStack(max stack size) ::=

#define MAX_STACK_SIZE 100    // 스택 최대 크기

typedef struct {

int key;

// other fields

} element;

element stack[MAX_STACK_SIZE];

int top = -1;                            // 스택의 top 포인터

Boolean IsEmpty(Stack) ::= top < 0;

Boolean IsFull(Stack) ::= top >= MAX_STACK_SIZE -1;

여기에서 top 포인터에 대하여 고려해 볼 필요가 있습니다.

만약 top 이 -1으로 초기화 될 경우 위의 경우와 마찬가지로 구성됩니다.

이러한 경우 top이 가르키는 위치에 데이터가 존재하지만 full 확인을 위해 조금 변경이 필요합니다.

만약 top 이 0으로 초기화 될 경우 아래처럼 구성이 됩니다.

int top = 0;

Boolean IsEmpty(Stack) ::= top < 1;

Boolean IsFull(Stack) ::= top >= MAX_STACK_SIZE;

이러한 경우 top 이전에 데이터가 존재하지만 full 확인은 편해지는 장점이 있습니다.

어떠한 상황에 사용 할 것인가에 따라 구성이 달라지게 될 것입니다.

void Push(int *top, element item) {

if ( IsFull() )

return stack_full();

stack[(*top)++] = item;

}

element Pop(int *top) {

if ( IsEmpty() )

return stack_empty();

return stack[--(*top)];

}

위와 같이 스택을 완성 할 수 있는데 (top = 0으로 한 경우)

이러한 경우 Pop시 데이터의 복사가 일어나게 된다.

따라서 다음과 같이 Pop과 Top을 구분하여 구성할 필요성이 생기게 된다.

void Pop(int *top) {

if ( IsEmpty() )

return stact_empty();

(*top)--;

}

element* Top(int top) {

if ( IsEmpty() )

return stack_empty();

return &stack[top - 1];

}

스택을 리스트로 구현하면 다음과 같이 구성할 수 있습니다.

리스트로 스택을 구성하는 가장 큰 이유는 메모리의 낭비와 Stack Full의 한계를 벗어남에 있습니다.

물론 리스트로 구성하기 때문에 포인터라는 4byte가 추가적으로 필요하지만

사용하지 않는 메모리라도 여유있게 할당 받아야하는 배열에 비해서는 장점이 있다 할 수 있습니다.

Stack CreateStack(max stack size) ::=

typedef struct _element {

int key;

// other fields

struct _element *next;

} element;

element top;

Boolean IsEmpty(Stack) ::= top->next == NULL;

Boolean IsFull(Stack) -> 필요하지 않음

void Push(element *top, element *item) {

item->next = top->next;

top->next = item;

}

void Pop(element *top) {

element* temp = top->next;

if ( IsEmpty() )

return stack_empty();

top->next = temp->next;

free(temp);

}

element* Top(element *top) {

return top->next;

}

리스트로 스택을 구성할 때 새로운 데이터의 추가나 삭제를 리스트의 끝에 하는 것 보다

헤더에 해당하는 부분에서 일어나게 되면 위치를 찾기 위한 연산이 필요하지 않다는 장점이 있습니다.

즉 리스트를 사용할 때의 단점인 검색 부분 자체를 고려하지 않음으로써 장점만을 최대한 부각시킬 수 있습니다.

큐(Queue)란 삽입과 삭제가 다른 쪽 끝에서 일어나는 자료구조입니다.

First In First Out (FIFO) 구조라고도 합니다.

큐의 기본적인 연산으로는 create, enqueue, dequeue, front 가 필요합니다.

create : 새로운 큐를 생성하는 함수

enqueue : 맨 뒤에 데이터를 추가하는 함수

dequeue : 맨 앞의 데이터를 삭제하는 함수

front : 맨 앞의 데이터를 참조하여 보여주는 함수

큐를 배열로 구현하면 다음과 같은 형태로 구성할 수 있습니다.

큐 자체를 나타내는 배열이 필요하며

데이터가 삭제될 위치를 가르킬 front와 데이터가 추가될 위치를 가르킬 rear 포인터가 필요합니다.

Stack CreateQueue(max queue size) ::=

#define MAX_QUEUE_SIZE 100    // 큐 최대 크기

typedef struct {

int key;

// other fields

} element;

element queue[MAX_QUEUE_SIZE];

int rear = 0, front = 0;                // 큐의 front, rear 포인터

Boolean IsEmpty(Queue) ::= front == rear;

Boolean IsFull(Queue) ::= rear >= MAX_QUEUE_SIZE;

void EnQueue(int *rear, element item) {

if ( IsFull() )

return queue_full();

queue[(*rear)++] = item;

}

void DeQueue(int *front, int rear) {

if ( IsEmpty() )

return queue_empty();

(*front)++;

}

element* Top(int *front, int rear) {

if ( IsEmpty() )

return queue_empty();

return &queue[(*front)];

}

위와 같이 큐를 구성할 경우 큐의 사용에 있어서 치명적인 문제가 하나가 생깁니다.

front와 rear가 증가만 하고 줄어드는 경우가 없기 때문에 큐가 일회성이 된다는 것입니다.

이를 해결하기 위해 배열을 사용할 경우 원형 큐(Circular Queue)로 구성하는 방법이 있습니다.

enqueue와 dequeue시 front와 rear에 대한 연산을 mod연산으로 변경함으로써 쉽게 변형이 가능합니다.

(*rear)++                            ->    *rear = (*rear + 1) % MAX_QUEUE_SIZE;

(*front)++                           ->    *front = (*front + 1) % MAX_QUEUE_SIZE;

rear >= MAX_QUEUE_SIZE   ->    rear == (front - 1) % MAX_QUEUE_SIZE;

단 원형 큐를 구성할 경우 full과 empty를 구분하기 위해 1개의 공간을 사용하지 못합니다.

큐를 리스트로 구현하면 다음과 같이 구성할 수 있습니다.

리스트로 큐를 구성하는 가장 큰 이유는 스택과 동일합니다.

또한 큐를 가르키는 포인터를 front와 rear 둘다 만들어도 되겠지만

원형 큐로 구성한다면 포인터 하나로도 충분히 큐를 구성할 수 있습니다.

이때 front를 이용한다면 추가연산을 위해서 찾는 과정이 필요해 집니다.

하지만 rear을 포인터로 삼게 된다면 특별히 찾지 않더라도 추가 삭제 연산을 쉽게 구현 할 수 있습니다.

Stack CreateQueue(max queue size) ::=

typedef struct _element{

int key;

// other fields

struct _element *next;

} element;

element rear;

Boolean IsEmpty(Queue) ::= rear->next == NULL;

Boolean IsFull(Queue) -> 필요하지 않음

void EnQueue(element *rear, element *item) {

if ( IsEmpty() ) {

item->next = item;

} else {

item->next = rear->next;

rear->next->next = item;

}

rear->next = item;

}

void DeQueue(element *rear) {

element *temp = rear->next->next;

if ( IsEmpty() )

return queue_empty();

if ( rear->next == temp )

rear->next = NULL;

else

rear->next->next = temp->next;

free(temp);

}

element* Front(element *rear) {

if ( IsEmpty() )

return queue_empty();

return rear->next->next;

}

스택과 큐에 대한 이야기를 진행했는데요 Array와 List의 관점에서도 중요한 점을 생각 해 볼 수 있습니다.

Array의 경우

포인터(Stack의 Top, Queue의 Front, Rear)를 이용하여 배열의 효율성을 올린다는 점 입니다.

이 후의 자료구조에서도 마찬가지 이겠지만 배열에 보조적인 포인터 변수가 추가 됨으로써

전혀 다른 새로운 자료구조로 만들 수 있습니다.

즉 포인터에 규칙을 설정하는 것에 따라 더 좋은 형태의 자료구조가 생길 수도 있다는 점이죠.

List의 경우

방향성에 대하여 고민해 보아야 합니다.

자료구조를 처음 배울때 가능 범하기 가장 쉬운 오해가 다음이니까 next에 존재해야 한다는 점입니다.

물론 위에 스택을 구현한 것을 보시면 새로운 노드는 다음이 아니라 이전에 추가 됩니다.

어떤한 분은 당연한거 아닌가 라고 생각 할 수도 있지만

이러한 고정관념을 탈피하느냐 아니냐가 얼마나 자유롭게 자료구조를 사용할 수 있는가를 결정하게 됩니다.

스택과 큐는 자료구조로서도 완성된 형태의 효율 좋은 자료구조이지만

자료구조를 공부하는 입장에서 주어진 자료구조가 아닌 자신만의 자료구조를 설계하기 위해서

생각의 틀을 벗을 수 있는 가장 좋은 예제가 아닐까 싶습니다.

자료구조 자체가 아니라 구현하기 위해 사용된 방법에 대해 생각해 볼 수 있는 기회가 되었으면 좋겠습니다.