[자료구조] Stack, 스택

우리가 오늘 공부할 것은 Stack(이하 스택)이라는 자료구조이다. 일반적으로 우리가 가장 처음 배우는 자료구조가 아닐까 생각한다.

1. 정의

LIFO(Last in First out)의 자료구조. 즉 마지막에 들어간 것이 제일 처음으로 나오는 자료구조이다.

2. 특징

스택에는 큰 특징이 있지는 않다. 정의에서 말한 특징이 거의 전부이지만 조금 더 자세하게 공부를 해보도록 하자.

1. LIFO의 자료구조이다.

 Last in First out. 마지막으로 들어간 것이 가장 처음으로 나온다. 우리가 접시를 쌓으면 위에 있는 것을 제일 먼저 쓰듯이, 이 자료구조도 똑같다. 밑의 그림을 보면 이해가 조금 더 빠를 것이다.

(출처 : https://en.wikipedia.org/wiki/Stack_(abstract_data_type))

사진을 보면 알듯이 push를 하면 위에 쌓이고, pop을 하면 위에 있는 값이 빠진다. 이러한 자료구조를 stack이라고 한다.

2. 빈 스택에 pop, 꽉 찬 스택에 push

 전자의 경우는 둘 다 에러를 뿜어낸다. 비어있는 스택에서 pop을 하려고 하는데, 가장 위의 값이 없다면 당연히 문제가 생긴다. 이는 top이라는 가장 위의 값을 가져오는 메소드에서도 똑같이 에러를 뿜는다. 실제로 코드를 보면 비어있을 경우 pop을 하려고 하면 assert라고 런타임 에러를 발생시키는 함수를 불러온다. 그래서 바로 강제종료가 되버린다.

후자는 그냥 자료구조 stack을 사용할 때는 잘 일어나지 않지만 이를 overflow라고 한다.

3. 구현

구현에는 두 가지 방법이 있다. array를 사용하는 방법, linked list를 사용하는 방법.

array를 사용하는 방법

array를 사용하는 방법은 코딩코스트가 굉장히 적으며, 구현하기가 쉽다. 하지만 array의 특징상, 한번 정해진 크기를 늘리는 것은 불가능하므로, 스택의 크기가 정해져버린다. 스택의 크기가 정해져 버린다는 것은 2번 특징의 "꽉 찬 스택에 push" 라는 문제가 발생할 수 있다는 것을 뜻한다. 예를 들어 array 크기를 10으로 잡는다면 우리는 11번 이상의 push를 한다면(물론 pop이 없다는 가정하에) overflow가 발생할 수 있다는 문제점이 있다.

linked list를 사용하는 방법

반대로 linked list는 위의 문제점이 없다. 왜냐하면 계속 노드들을 동적할당하면서 넣고 빼고를 하기 때문에, heap영역의 메모리를 다 쓸 때까지 계속 push 할 수 있다. 하지만 코딩 코스트가 많이 든다.

물론 둘 다 비어있을 때 pop이나 top을 부르는 것은 언제나 조심해야한다.

코드는 http://compasstree934.tistory.com/8?category=676158 에 있다.

4. 추가 공부

c++에서 우리는 스택을 구현해서 사용하지 않는다. 왜 굳이 standard library에 확실하고 안전하게 만들어 놓은 스택이 있는데 만들어 쓰는가. 우리는 밑의 코드 처럼 선언해서 사용한다.

#include<iostream>
#include<stack>
using namespace std;

int main(){
    stack<int> s;
    s.push(1);
    s.top();
    s.pop();
    s.size();
    
    return 0;
}

이렇게 사용하는 스택은 push, pop, size 등등 많은 메소드가 있는데, 이 중에서 가장 많이 쓰이는 4가지를 어떻게 사용하는지 공부해보자.

선언은 밑의 코드처럼 

stack<넣고자_하는_변수의_타입> 스택_이름; 로 사용한다.

    stack<int> s;

그리고 메소드들을 쓸 때는 밑의 코드처럼 

스택_이름.메소드_이름(파라매터); 로 사용한다.

    s.push(1);
    s.top();
    s.pop();
    s.size();

이렇게 사용하면 굳이 구현을 하지 않더라도 사용이 가능하다.