5.4 스택

스택은 큐와 달리 가장 최근에 보관한 자료를 먼저 꺼내는 후입선출(LIFO, Last In First Out)형태로 동작하는 자료구조입니다.

 

스택은 배열이나 연결리스트로 구현할 수 있어요.

여기에서는 배열로 구현하는 것을 먼저 해 본 후에 미리 만든 연결리스트를 래핑하는 방법을 살펴보아요.

 

먼저 스택 구조체를 정의하세요.

스택에는 저장소와 가장 최근에 보관한 위치를 멤버로 갖고 있어야 해요.

스택에는 보관하는 동작을 Push라 부르고 꺼내는 동작을 Pop이라 불러요.

 

배열로 스택을 구현할 때는 저장소가 꽉 찼는지 확인하거나 비었는지 확인하는 기능을 제공하죠.

 

여기에서는 초기화 기능도 제공하기로 해요.

 

초기화 기능에서는 스택의 top 멤버를 -1로 초기화해요.

top은 가장 최근에 보관한 자료의 위치를 기억하고 있어야 해요.

 

꽉 찼는지 확인하는 기능에서는 top+1이 스택 크기와 같은지 비교해야겠죠.

스택이 비었는지 확인할 때는 top이 초기값 -1과 비교해요.

스택에 보관하는 Push에서는 꽉 찼는지 확인해요.

그리고 꽉 차지 않을 때는 top을 1 증가한 후에 보관해요.

스택이 비었는지 확인하는 Pop 함수는 비었는지 확인해요.

그리고 비어 있지 않을 때는 top위치의 값을 반환해야겠죠.

물론 top을 1감소해야 해요.

 

 

이 책에서는 앞서 만든 큐처럼 연결리스트를 래핑하여 만들기로 할게요.


5.4.1 스택 설계

5.4.2 스택 구현

5.4.3 스택 테스트

5.4.4 스택 소스 코드