'자료구조 스택'에 해당되는 글 1건

스택(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이라는 배열의 인덱스로 쓸 수 없는 위치에 있지요.

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

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