자료구조 - 6 | 스택

스택

지금까지 선형 자료구조 중 순차 자료구조와 연결 자료구조에 대해 알아보았다. 이 두 자료구조는 단독으로 사용된다기보다는 다른 자료구조를 구현하기 위해 주로 사용된다. 실제로도 리스트를 구현하기 위해 이 두 방식을 사용해 선형 리스트와 연결 리스트를 구현할 수 있었다.

 

이번에는 단순히 데이터를 순서대로 나열하기만 하는 리스트가 아닌, 특정한 제약을 가지고 동작하는 스택이라는 자료구조에 대해 알아볼 것이다. 스택 역시 순차 자료구조와 연결 자료구조를 이용해 각각 다른 형태로 구현할 수 있으므로, 이전에 설명한 순차 자료구조와, 연결 자료구조의 개념에 대해 다시 한번 확인하기를 바란다.

스택의 개념

스택은 데이터를 접시를 쌓듯이 쌓아 올리는 형태로 저장하는 자료구조이다. 새 접시를 쌓아 올릴 때는 항상 이미 쌓아져 있는 접시의 가장 윗부분에 새로 쌓는다. 그리고 쌓아진 접시에서 접시를 하나 빼기 위해서는 가장 위에 올려진 접시만을 뺄 수 있다.

 

물론 실제로 데이터는 메모리에 저장되므로, 데이터가 높이를 가지고 쌓인다는 것은 맞지 않는다. 하지만 개념적으로는 마치 접시를 쌓듯이 동작하는 것이다. 이렇듯 스택은 가장 마지막에 삽입한 원소가 가장 먼저 삭제되는 구조인 후입 선출 구조(LIFO; Last-In-First-Out)를 가진다.

스택의 연산

스택에서는 데이터 삽입과 삭제가 가능한데, 각각 push와 pop이라고 불린다.

스택에서의 삭제인 pop은 스택에서 그 값을 삭제함과 동시에 반환한다. 쉽게 말해 스택에서 꺼내서 가져온다 라는 표현이 맞을 것 같다.

스택의 데이터 삽입(push)와 삭제(pop) 과정

---

스택의 구현

스택이라는 자료구조는 생각보다 굉장히 단순하다. 데이터를 삽입할 때에는 이미 저장된 데이터의 가장 뒤에만 삽입하고, 삭제할 때에는 가장 마지막에 삽입된 데이터만 삭제한다는 규칙만 지키면 된다. 데이터와 데이터 사이 원하는 곳에 새 값을 삽입하거나, 중간에 저장된 데이터를 삭제할 수 있다는 리스트와는 달리 삽입과 삭제의 자유도가 굉장히 낮다.

 

그렇다면 모든 걸 할 수 있는 리스트가 스택보다 훨씬 좋은 거 아니냐라는 말이 나올 수 있는데, 이에 대해서는 나중에 자세히 알아보고, 우선은 이러한 특징은 가지는 스택을 구현하는 방법에 대해 알아보도록 하자.

순차 자료구조를 이용한 스택의 구현

먼저 순차 자료구조인 1차원 배열을 이용해 스택을 구현해 보자.

 

스택을 위해 생성한 배열의 크기가 곧 스택의 크기가 될 것이고, 스택에 저장된 원소의 순서가 배열에 저장된 원소의 인덱스가 될 것이다. 또한 따로 top이라는 변수를 만들어 스택에 저장된 가장 마지막 원소에 대한 인덱스를 저장한다. 따라서 삽입과 삭제는 이 top이라는 변수에 저장된 인덱스를 이용해 진행한다. 만약 스택이 공백 상태라면 top의 값은 -1이 될 것이고, 포화 상태라면 top의 값이 n-1이 될 것이다. (n은 스택의 크기)

 

이를 그림으로 표현하면 아래와 같다.

1차원 배열을 이용한 스택

이렇게 순차 자료구조인 배열을 이용해 스택을 구현하면 매우 쉽고 빠르게 구현할 수 있다. 하지만 이전에 설명했던 순차 자료구조가 가지는 기본적인 단점들을 모두 가진다는 단점이 있다.

연결 자료구조를 이용한 스택의 구현

연결 자료구조 중 하나인 단순 연결 리스트를 이용해 스택을 구현할 수도 있다.

 

각 스택의 원소를 단순 연결 리스트의 노드의 데이터 필드에 저장한다. 이후 스택 원소의 순서에 맞게 노드의 링크 필드를 잘 연결하기만 하면 끝이다. 이때 중요한 것은 스택은 항상 가장 마지막에 원소를 삽입하고, 가장 마지막 원소를 삭제한다는 점이다. 연결 자료구조는 순차 자료구조에 비해 장점이 많지만, 특정 순서의 원소에 바로 접근하지 못한다는 단점이 있다.

 

스택에서 원소를 삽입하거나 삭제할 때마다 가장 마지막에 위치한 노드를 찾기 위해, 가장 첫 노드부터 시작해 링크 필드를 타고, 또 다음 링크 필드를 타는 과정을 계속해서 반복해야 할 것이다. 따라서 top이라는 변수를 두어 항상 단순 연결 리스트의 마지막 노드를 가리키도록 한다.

또한 기존의 단순 연결 리스트와는 달리, 링크 필드가 자신 다음의 노드를 가리키는 것이 아니라, 자신 이전의 노드를 가리키도록 하여서, 노드가 삭제될 때마다 top변수가 다음 노드로 쉽게 이동할 수 있도록 한다.

 

이를 그림으로 표현하면 아래와 같다.

단순 연결 리스트를 이용한 연결 스택

사실 쉽게 생각하면 top변수가 기존 단순 연결 리스트에서의 리스트 포인터라고 생각하면 된다. 그리고 항상 가장 첫 공간에 새 노드를 삽입하고, 가장 처음에 있는 노드만을 삭제한다고 생각하면 된다. 이렇게 생각하면 별도의 top변수를 생성할 이유도 없고, 링크 필드도 기존처럼 자신 다음의 노드를 가리키게 하면 된다.

 

꼭 가장 마지막에 데이터를 삽입하고, 가장 마지막 데이터만 삭제할 수 있다고 생각할 필요는 없다. 중요한 것은 가장 나중에 삽입된 원소를 가장 먼저 삭제하는 구조이기만 하면 된다.