스택
이번 포스트에서 학습할 내용은 스택이다. 스택은, 앞서 배운 리스트보다는 훨씬 더 쉽게 동작하는 것을 확인할 수 있다. 대표적인 예제인 계산기 프로그램과 같이 구현하기에는 어려울 수는 있겠지만 내용은 어렵지 않다는 것을 다짐하면서 이 포스트를 시작해보겠다.
스택이란?
나중에 들어간 데이터가 먼저 나오는 구조 (후입선출의 구조)이다.
LIFO (Last-In, First-Out) 라고도 말할 수 있다.
대표적인 예시로는 쌓여올려진 상자더미, 쟁반 위에 쌓인 접시, 한쪽은 막히고 한쪽은 뚫린 초코볼 통 등이 있다. 즉, 입구가 하나여서 자료를 넣는다면 그 자료를 조회하거나, 삭제를 할 때에는 마지막에 넣은 자료부터 할 수 있다는 특징을 가지고 있는 것이다.
스택의 기본 연산자
구현하고자 하는 프로그램이 무엇이냐에 따라 달라질 수 있겠지만, 스택에서 쓰이는 연산자는 총 3개라고 말할 수 있다.
-
PUSH 연산자
스택에 데이터를 넣는 것을 말한다. 상자로 예시를 든다면, 아래서부터 위로 차곡차곡 쌓아올리는 것을 말할 수 있다. -
POP
스택에 있는 데이터를 빼는 것을 말한다. 차곡차곡 쌓여진 상자를 빼는 것이지만, 중간에 있는 상자를 빼면 그 기둥이 무너지기에 맨 위에있는(마지막에 넣은 자료) 상자부터 하나씩 빼는 명령어라고 말할 수 있다. -
PEEK
POP연산자와 유사하다고 말할 수 있다. 다만, 차이점은 POP연산자는 데이터를 조회한 이후 삭제를 하지만, 이 연산자는 데이터를 조회만 하고 반환하는 것이 끝이라는 것이다.
스택의 ADT
앞서 말한 연산자를 포함하며 설명할 것이기에 스택의 ADT는 많지가 않다.하나씩 보도록 하겠다.
-
스택의 초기화, 스택을 가져올 때 가장 먼저 실행해야할 코드
void StackInit(Stack * stack); -
스택이 비워있는지 여부를 확인하는 명령어, TRUE/FALSE를 반환함.
int SIsEmpty(Stack * stack); -
스택에 데이터를 저장 (PUSH연산)
void SPush(Stack * stack, Data data); -
마지막에 저장한 데이터를 삭제 후 반환 (POP 연산)
Data SPop(Stack * stack); -
마지막 데이터를 반환, 단 삭제는 하지 않는다. (PEEK 연산)
Data SPeek(Stack * stack);
스택의 구현
우리는 지금 배열 자료구조, 연결 리스트 자료구조만 학습하였다. 물론, 이 두가지를 활용해서 스택 자료구조를 구현할 수 있다. 자료구조는 또 다른 자료구조를 구현하기 위한 재료라고 생각해도 좋다.
스택의 배열 기반 구현
스택의 배열 기반 구현 그림은 다음과 같다. 처음 TopIndex를 -1로 설정하였고, 그 이후에 데이터를 PUSH하면, 데이터의 추가와 함께 TopIndex가 가리키는 값도 하나씩 증가한다. Top 변수를 활용하는 이유는 그림에서 맨 오른쪽 연산을 위해서인데, 데이터를 삭제하거나 (POP) 데이터를 조회할 때(PEEK) 인덱스가 가리키는 값을 넣을 때 편하기 때문이다.
배열의 인덱스 0을 스택의 바닥으로 정의하는데, 그 이유는 다음과 같다.
-> 길이에 상관없이 0의 요소가 스택의 바닥이 되기 때문이다.
스택의 연결리스트 기반 구현
스택의 연결리스트 구현은 앞 포스트에서 다뤘던 리스트 중에서 head와 tail이 노드의 처음과 끝을 가리키고 있다면, 데이터를 추가할 때 head에 넣어서 추가하는 것과 같다고 볼 수 있다. head에 데이터를 추가하며, 저장된 순서의 역순으로 조회(삭제)가 가능한 리스트, 즉 이를 스택을 연결리스트로 구현한 것이라고 말할 수 있다.
head를 null로 초기화 한 이후, push하여 데이터를 추가할 때 새로운 노드를 head가 가리키도록 하고, pop시에는 head->next를 head가 가르키도록 변경한 이후, 반환 한 데이터를 조회 후 free함수를 사용하여 메모리를 반환해주면 된다.
이렇게 오늘은 스택에 대하여 다루어봤다. 스택의 기본 연산자는 크게 3가지 밖에 없긴하여 쓰일일이 많이 없는 자료구조라고 생각할 수 있지만, 생각보다 스택을 활용한 알고리즘 구현이 많다는 것을 알 수 있다. 백준 문제를 풀면서 스택을 많이 응용해야하는 문제를 풀게 될 때 풀이방법을 한번 포스트 해보도록 하겠다. 다음은 큐(Queue)에 대한 학습을 마치고 오도록 하겠다.
