'스택'에 해당되는 글 5건

스택( 연결 리스트 형)

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

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

우리는 옆으로 나열된 노드를 아래로 나열된 리스트 형태로 한번 떠올려볼까요? 그리고 맨 처음의 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;

}

스택(Stack) 개념

자료구조에서 스택은 어떤 자료구조일까요? 스택은 영어 단어 자체에서 힌트를 얻을 수 있습니다.

stack은 쌓다, 무더기 이런 의미로 쓰이죠.

이 의미가 자료구조에 그대로 반영이 됩니다. 

우리는 어떤 물건을 쌓는다면 가장 먼저 쌓은 물건은 아래에 깔리고 가장 최근 쌓은 물건은 위에 쌓이게 되지요.

꺼낼때는 어떨까요?

나중에 쌓은 물건을 먼저 꺼내겠죠?

이처럼 나중에 쌓은 것이 먼저 나오고 먼저 쌓은 물건은 더 나중에 나온다 라는 개념이 LIFO(Last In First Out)이라고 합니다. 그와 반대, 먼저 들어온 것이 먼저 나간다의 개념은 FIFO(First In First Out)라고 합니다.

종류

스택은 두 가지 정도의 종류가 존재합니다.

● 배열형태의 스택

● 연결리스트 형태의 스택

두 형태는 스택을 구현하는 기능은 같더라도 효율성에서 다릅니다. 

배열형 스택은 우선 접근 속도가 빠릅니다. 하지만 다시 크기를 확장하거나 줄일때 효율성이 떨어지게 되죠. 생각해보세요. 스택 크기가 10인 스택이 데이터를 더 저장하기 위해 스택의 길이를 늘리게 되면 우선 배열의 크기를 다시 할당하고 난 후에 값을 복사해야합니다. 길이가 10인 스택이라 그렇지 크기가 크면 클 수록 성능이 저하되는 것을 알 수 있습니다.

그리고 사용자가 얼마만큼의 스택 크기가 필요한지 예측을 할 수도 없습니다.

반면 연결리스트형 스택은 가변적으로 스택의 크기를 줄였다 늘였다 할 수 있습니다. 반면 값에 접근하려면 그 효율성이 떨어지게 됩니다. 연결리스트 형 스택을 구현하려면 linked list 자료구조를 우선 알아야합니다.

스택의 사용처

스택은 함수의 호출 뿐만 아니라 수식에서도 사용되며 사용처는 많습니다. 우리가 즐겨쓰는 인터넷의 뒤로가기 역시 스택 자료구조가 쓰이게 됩니다. 심지어 미로를 찾는데에도 스택을 쓸 수 있습니다.

기본적으로 스택은 여러 언어에서 표준 라이브러리로 제공이 되긴 합니다만 어떻게 구현이 되어있는지 정도는 이해하고 있어야합니다.

아래의 코드는 배열형 스택을 c++ 코드로 구현한 것입니다. 

#include <iostream>
#define stack_size 100
using namespace std;

struct stack {
	int top = -1;
	int arr[stack_size];
	void push(int data) {
		if (top == stack_size-1) {
			printf("stack is full\n");
			return;
		}
		arr[++top] = data;
	}
	int pop() {
		if (empty()) {
			printf("stack is empty\n");
			return -1;
		}
		return arr[top--];
	}
	int peek() {
		if (empty()) {
			printf("stack is empty\n");
			return -1;
		}
		return arr[top];
	}
	bool empty() {
		return top <= -1;
	}
};
int main() {
	stack st;
	//현재 스택은 비워져있는 상태
	cout << "is stack empty? "<<st.empty() << endl;
	cout << st.pop() << endl;
	cout << st.peek() << endl;

        //for 루프가 돌면 스택은 1개만 저장 가능한 상태
	for (int i = 0; i < stack_size-1; i++)
		st.push(i + 1);

        cout << endl;
        cout << "after for loop"<<endl;
	st.push(15);
        //스택은 전부 채워져 있는 상태
	st.push(120);
        //스택에서 한 개가 비워짐, 1개 채울 수 있는 상태
	st.pop();

	st.push(120);

	cout<<endl;
        //스택이 비워지면 while루프 종료
	while(!st.empty())
		cout << st.pop() << endl;
	
}

위의 코드를 이해하기 쉽게 그림으로 표현해보겠습니다. 

1. 초기 스택의 상태는 이런 그림입니다. top은 맨 아래, -1이라는 배열의 인덱스로 쓸 수 없는 위치에 있지요.

코드를 잘 따라가 보면 이해하실 겁니다.

배열 스택을 조금 이해하셨나요?