[자료구조] 스택(stack)

스택이 데이터를 저장하는 방법은 배열과 같다. 단순하게 얘기하면 원소들의 리스트다. 다만 스택에는 다음과 같은 제약이 있다.

• 데이터는 스택의 끝에만 삽입할 수 있다.
• 데이터는 스택의 끝에서만 읽을 수 있다.
• 데이터는 스택의 끝에서만 삭제할 수 있다.

접시를 스택이라고 생각해 보면 가장 위에 있는 접시를 제외하고는 다른 접시의 윗면을 볼 수 있다. 비슷하게 가장 위를 제외하고는 접시를 추가할 수도, 제거할 수도 없다(끼워넣기 안돼요). 실제로 대부분의 컴퓨터 과학책에서 스택의 끝을 top, 스택의 시작을 bottom이라고 부른다.

 

빈 스택부터 시작해서 스택의 동작을 알아보자.

 

스택에 새 값을 삽입하는 것을 스택에 푸시한다고 한다. 스택에 5를 푸시하자.

특별할 것은 없다. 그저 배열 끝에 데이터를 삽입하는 것이다. 3을 푸시하자.

0을 푸시하자.

데이터는 항상 스택의 끝에 추가되고 있다. 스택의 밑이나 중간에 0을 삽입하고 싶어도 데이터는 위에만 추가할 수 있다. 스택의 특징 때문이다. 스택의 위에서 원소를 제거하는 것을 스택으로부터 팝 한다고 한다. 팝(pop) 또한 위에서만 할 수 있다. 0을 팝 하자.

3을 팝 하자.

그러면 5만 남게 된다.

스택 연산을 묘사하는 데 사용되는 두문자는 LIFO(last in, first out)이다. 스택은 입력 받은 순서와 반대로 데이터를 처리해야 할 때(LIFO) 항상 이상적이다. 워드 프로세서의 "되돌리기" 함수나 네트워크 애플리케이션에 쓰이는 함수 호출 등에서 스택이 유용할 것이다.