Chapter 06. 스택의 이해와 ADT(추상 자료형) 정의

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

앞서 여러 Chapter에 걸쳐 공부한 리스트는 대표적인 선형 자료구조입니다. 그리고 이번에 배우게 될 스택이란 자료구조도 선형 자료구조의 일종입니다.

---

스택이란 총알을 저장하는 탄창에 비유할 수 있습니다. 아니면 차곡차곡 쌓이는 접시에도 비유할 수 있습니다. 이 둘의 공통점은 가장 마지막에 추가한 것일수록 가장 먼저 사용된다는 것에 있습니다.

 

총알의 경우 총알을 하나씩 탄창에 넣다 보면 가장 먼저 넣은 총알은 탄창의 가장 아래에 위치하게 됩니다. 그리고 가장 마지막에 넣은 총알이 탄창의 가장 위로 나옵니다. 따라서 이 탄창을 총에 장착하고 총알을 발사하게 되면 탄창에 넣었던 순서의 반대 순서대로 총알이 발사됩니다.

 

접시의 경우도 마찬가지입니다. 접시를 차곡차곡 쌓게 되면 아래쪽에 있는 접시를 꺼내기가 어렵습니다(물론 불가능한 것은 아니지만). 그래서 접시가 필요하다면 가장 위에 올라와 있는 접시를 사용하게 됩니다. 그리고 가장 위에 올라온 접시는 가장 나중에 쌓인 접시일 것입니다.

 

이처럼 스택은 데이터를 저장한 순서의 반대 순서대로 데이터를 사용할 수 있다는 특징이 있습니다.

---

앞서 살펴본 리스트 자료구조의 ADT는 필요에 따라서 그 정의 내용에 약간씩 차이가 있었습니다. 반면 스택의 ADT는 상대적으로 정형화되어 있습니다. 그도 그럴 것이 탄창을 가지고 우리가 할 수 있는 일이 그다지 다양하진 않습니다. 

• 탄창에 총알을 하나씩 넣는다. [push]
• 탄창에서 총알을 하나씩 뺀다(맨 위에 올라와 있는 것부터). [pop]
• 탄창의 맨 위로 어떤 총알이 올라와 있는지 확인한다. [peek]
• 탄창이 비었는지 확인한다.

특히 스택을 대표하는 넣고, 꺼내고, 들여다보는 연산을 가리켜 각각 push, pop, peek이라고 합니다. 다음은 스택 자료구조의 ADT입니다.

void StackInit(Stack* pstack);
//스택의 초기화를 진행한다.
//스택 생성 후 제일 먼저 호출이 되어야 하는 함수이다.

int SIsEmpty(Stack* pstack);
//스택이 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환한다.

void SPush(Stack* pstack, Data data);
//스택에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.

Data SPop(Stack* pstack);
//마지막에 저장된 요소를 삭제한다.
//삭제된 데이터는 반환이 된다.
//본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

Data SPeek(Stack* pstack);
//마지막에 저장된 요소를 반환하되 삭제하지 않는다.
//본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

이름 충돌의 확률을 낮추기 위해서 각각의 함수명에 스택을 뜻하는 S를 접두사로 붙였습니다. 

---

스택은 배열을 이용해서도 구현이 가능하고, 또 연결 리스트를 이용해서도 구현이 가능합니다. 따라서 다음 시간부터 배열 기반의 스택과 연결 리스트 기반의 스택을 모두 구현해 볼 것입니다.