스택(Stack)

최근 간간히 Programming Challenges를 보고 있습니다. 너무도 어려운 문제들이 많지만 나름 재미를 붙여가고 있습니다. 책의 내용 중 일부를 발췌하였습니다. 참고하세요.

스택(Stack)과 큐(Queue)는 각 항목을 내용과는 무관하게 삽입된 순서에 따라 꺼내도록 설계된 컨테이너이다.
스택은 후입선출(LIFO, last-in first-out) 규칙을 따르는 구조로서 마지막에 들어간 항목이 가장 먼저 나오는 자료구조이다.

스택의 연산에는 다음과 같은 것이 있다.

• Push(x, s) - x라는 항목을 s라는 스택 맨 위에 삽입
• Pop(s) - 스택 s의 맨 위에 있는 항목을 리턴하고 삭제
• Initialize(s) - 비어있는 스택을 생성
• Full(s), Empty(s) - 스택 s에 대하여 Push 및 Pop 연산을 적용할 수 있는지 확인

표준 스택과 큐에는 원소를 검색하는 연산이 정의되어 있지 않다는 점을 잘 기억해두세요.

상기 연산을 알아두면 자세한 구현 방법은 모르더라도 쓸 수 있는, 즉 재사용이 쉬운 스택 모듈을 만들 수 잇다.
가장 쉬운 구현법은 배열과 스택 맨 위를 나타내기 위한 인덱스 변ㅅ를 사용하는 방법이다. 또 다른 방법으로 Linked-List가 있는데 이를 이용하면 배열의 크기 제한이 걸리는 문제가 없다는 장점이 있다.

스택은 접시를 쌓아 놓은 것에 비유할 수 있다.

접시를 새로 씻고나면 그 접시는 스택 맨위에 추가된다. 즉 Push(x, s) 연산을 수행한 것이다.
그리고 접시를 사용해야 하는 사람은 맨 위에 있는 새 접시를 집어든다. 즉 Pop(s) 연산을 수행한 것이다.

접시를 올려놓거나 맨위에 있는 접시를 꺼내는 작업을 할 때는 다음에 나온느 접시에 대하여 신경 쓸 필요가 없기 때문에 이런 스택이라는 자료구조를 사용하는 것이 적합하다.

스택은 구현하기가 아주 간단한 컨테이너이기 때문에 순서가 별로 중요하지 않는 경우에는 스택을 활용하면 좋다.

중첩된 구조를 처리할 때는 스택 순서가 중요하다.
중첩된 구조의 예를 들자면 괄호로 싸여있는 공식, 재귀호출, 그래프의 깊이 우선 순회 등이 있다.