'연결 스택 구현 원리'에 해당되는 글 1건

스택( 연결 리스트 형)

스택은 링크드리스트로도 구현할 수 있습니다.  링크드리스트의 장점을 그대로 물려받게 되면서요.

어찌 구현하면 될까요? 링크드리스트의 형태를 우선 돌이켜보면 어떻게 구현하는 지 감이 올거에요.

우리는 옆으로 나열된 노드를 아래로 나열된 리스트 형태로 한번 떠올려볼까요? 그리고 맨 처음의 Root노드를 Top으로 정의하게 된다면 연결형태의 Stack을 구현할 감이 오게 됩니다.

구현

node와 stack 구조체를 정의할 겁니다. node는 링크드리스트의 노드와 같습니다. 그리고 stack이라는 구조체는 현재 node형의 top이라는 변수를 갖고 있습니다. top은 역시 stack의 top을 말하지요. 

노드는 이렇게 생겨먹었습니다. 익숙하군요.

struct node {
	int data;
	struct node *next;
};

그리고 스택은 지금 이렇게 생겨먹었죠. 근데 top과 len(길이)밖에 없으니 무언가 공허합니다.

struct stack {
	node *top;
        int len;
        stack(){
                top=NULL;
                len=0;
        }
};

초기값 top은 NULL을 가리키고 스택 크기는 0입니다. 우리는 이 stack이라는 구조체에 연산을 삽입할 겁니다.

스택의 연산에는 isEmpty, push, peek, pop 정도가 있었지요? 추가로 스택의 size를 구하는 연산도 넣겠습니다. 이제 링크드리스트 형태로 구현해볼 것입니다.

1.size

스택의 크기가 얼만큼 되는 가에 대해 질의하는 연산입니다. 

int size() {
		return len;
}

그냥 스택의 길이만 반환하면 됩니다.

2. isEmpty

스택에 노드가 없느냐 물어보는 질의형태의 연산입니다. 만약 스택이 비어있다면 스택이 모두 비워져있는 상태이므로 top은 NULL을 가리키게 됩니다. 또는 스택의 길이를 이용하는 겁니다. 길이가 0이면 비워진 스택이 됩니다. 코드는 간단합니다.

int isEmpty() {
		//return top == NULL;
                return len == 0;
}

3. push

스택에 노드를 추가하는 연산입니다. 어떤 노드를 추가하고 그 노드의 next는 이미 기존의 top을 가리킵니다. 그리고 top을 새로운 노드로 가리키게 만들어주면 됩니다.

그림으로 더 쉽게 보도록 하시죠. 

새로운 노드가 스택에 추가되려고 기다리고 있습니다. 새로들어오는 노드의 next를 기존의 top이 가리키고 있는 노드를 가리키도록 바꾸어줍니다. 그리고 top을 다시 새로운 노드로 바꾸어주는 것이죠. 그러면 그림은 아래처럼 바뀌게 됩니다.

스택에 하나 넣었으니 스택의 크기를 하나 증가시킵니다(len++).

이것을 코드로 구현한 것이 아래의 코드입니다.

void push(int data) {
		
		node *newNode = (node*)malloc(sizeof(node));
		newNode->data = data;
		newNode->next = top;
		top = newNode;
                len++;
}

4. pop

처음 top에 있었던 데이터를 복사하고 난 후 기존 top의 next를 다시 top이 가리키도록 바꾸면 됩니다.

그리고 나서는 기존의 top 노드를 삭제해야하는 데 그것은 free함수만 사용하면 됩니다.

스택에서 하나 꺼내니까 사이즈가 줄겠죠?(len--);

pop의 연산을 아래의 코드로 구현했습니다. 

int pop() {
		
		int ret;
		if (isEmpty()) return INF;
		node *here = top;
		ret = here->data;
		top = here->next;
		free(here);
                len--;
		return ret;
	}

우선 스택이 비어있는지 확인하는 작업이 필요합니다. 스택이 비어있는데, 거기서 node를 꺼낼 수 없거든요. 새롭게 확인하는 코드를 쓰기 보다 그전에 isEmpty연산 이용하도록 합시다. 스택이 비어있다면 INF라는 무한정 큰값을 반환합니다. 

그리고 어떤 케이스에 따라서는 node 자체를 반환해야할 때가 있습니다. 그럴때는 위의 코드처럼 free함수를 하면 안됩니다. 메모리가 해제된 상태로 node 포인터를 반환하게 되어버리기 때문입니다.

5. peek

peek 연산은 pop에서 별반 다를것이 없습니다. 그냥 노드를 삭제하지 않고 데이터만 뽑아내면 되기 때문이죠.

전체코드

전체코드(C++)는 아래와 같습니다. 

#include <iostream>
#define INF 987654321

using namespace std;

struct node {
	int data;
	struct node *next;
};

struct stack {
	node *top;
        int len;
        stack(){
                top = NULL;
                len = 0;
        }
        int size() {
		return len;
	}
	int isEmpty() {
		//return top == NULL;
                return len==0;
	}

	void push(int data) {
		
		node *newNode = (node*)malloc(sizeof(node));
		newNode->data = data;
		newNode->next = top;
		top = newNode;
                len++;
	}

	int pop() {
		
		int ret;
		if (isEmpty()) return INF;
		node *here = top;
		ret = here->data;
		top = here->next;
		free(here);
                len--;
		return ret;
	}

	int peek() {
		if (isEmpty()) return INF;
		node *here = top;
		return here->data;
	}
};

stack st = { NULL };


int main() {
	
	cout << st.peek() << endl;
	for (int i = 1; i <= 3; i++) 
		st.push(i);
	

	cout << st.pop() << endl;
	cout << st.pop() << endl;
	for (int i = 4; i <= 6; i++)
		st.push(i);

	while (!st.isEmpty())
		cout << st.pop() << endl;

}