자료구조 (Data Structure) (2) - 스택 (Stack) 이란?

이전 게시물에서 자료구조의 기본 개념이 되는 스택과 큐 라는 구조에 대한 간단한 설명을 게시했다. 이번에는 스택에 대해서 자세히 다뤄보려고 한다. 먼저 스택이란 책의 인용을 빌리면 아래와 같다.

스택 (Stack) 이란 박스 쌓기와 같다. 박스를 쌓을 때는 아래에서부터 차곡차곡 위로 쌓고 박스를 제거할 때는 위에서부터 하나씩 제거하게 되는데 이러한 구조가 스택과 매우 유사하다. 이를 앞의 게시물에서 설명한 핵심 함수에 비유하면 다음과 같다.
  - 삽입 (push) : 박스를 아래에서부터 한 층씩 쌓는 것
  - 삭제 (pop) : 박스를 위에서부터 한 층씩 제거하는 것
이와 같이 스택은 선입후출 (Last In First Out, LIFO) 의 방식으로 데이터를 삽입, 삭제한다. 
즉, 스택은 데이터의 삽입과 삭제가 동일한 곳에서 일어난다.

스택에 데이터가 삽입되고 삭제되는 과정을 차례로 보여주는 그림이다.                                                                                                   순서대로 push(A) -> push(B) -> push(C) -> push(D) -> push(E) -> pop() 의 연산이 진행되었음을 알 수 있다. LIFO의 방식으로 스택에서 데이터가 제거될 때는 가장 마지막에 들어온 데이터가 삭제 됨 또한 알 수 있는 그림이다.

---

파이썬에서 스택을 사용할 때는 별도의 라이브러리를 사용할 필요 없이 리스트로 스택을 구현할 수 있다. 이 때의 삽입, 삭제의 함수는 아래의 파이썬 문법을 사용해서 구현하면 된다.

• 삽입 : 스택.append(데이터)
• 삭제 : 스택.pop()

리스트를 수정하는 메서드에 해당하는 append()와 pop() 함수는 각각 리스트의 가장 뒤에 데이터를 삽입하고, 리스트의 가장 마지막 요소를 삭제하는 기능을 한다. 이로인해서 리스트를 생성하고 위의 함수들을 사용하면 쉽게 스택을 구현할 수 있는 것이다.