스택이란, 데이터가 들어가는 부분과 나오는 부분이 같아, LIFO(Last in, First out), 후입선출구조를 이루는 제한적인 접근이 가능한 선형 자료구조이다.
쉽게 말해, 책을 쌓아올리면, 보통은 제일 마지막에 쌓은 책부터 꺼내는 모양과 같다고 말할 수 있겠다.
그러면 스택을 구현해보자. 이번에 스택이 동작시키기 위해 구현할 함수는 총 7가지로, 다음과 같다.
- 스택을 초기화할 init_stack
- 데이터를 추가할 push
- 제일 마지막 데이터를 제거할 pop
- 데이터가 얼마나 담겨있는지 알아낼 size
- 스택이 비었는지 체크할 empty
- 제일 마지막 데이터를 반환할 top
- 얼마나 할당받았는지 반환할 capacity
먼저 스택 구조체를 먼저 선언해보자. 얼마나 많은 데이터가 들어올지 모르기 때문에 포인터로 받아서 동적할당을 하고자 한다. 간단하게 int형 데이터를 담을 스택을 만들어 보자.
typedef struct stack{
int* _stack;
int _top;
int _max;
}stack;
_stack은 데이터를 저장할 포인터이고, _top은 제일 마지막에 들어온 데이터의 위치를 저장할 변수, _max는 할당받은 영역의 크기를 저장할 변수이다. 이때 _top은 정확한 인덱스를 가르킨다. (예를 들어 _top 데이터가 인덱스로써 1번째 위치에 있다면 _top은 1이다.)
1. init_stack
스택을 초기화하는 init_stack함수를 구현해보자.
stack* init_stack(){
stack* ret = (stack* )malloc(sizeof(stack));
ret->_top = -1;
ret->_max = 32;
ret->_stack = (int* )malloc(sizeof(int) * ret->_max);
return ret;
}
_top이 -1이라면 비어있다는 뜻으로 받아들이면 되고, 맨 처음에 할당할 영역은 32블럭정도면 충분할 것 같아서 이렇게 했다. 이렇게해서 초기화가 완료되었다면, 스택의 포인터를 반환한다.
2. push
스택에 데이터를 추가할 push를 구현해보자.
맨 처음에는 당연히 스택이 비어있을 것이다. 3과 7을 순차적으로 push하면 다음과 같을 것이다.
LIFO구조이기 때문에, 책을 쌓는 것처럼 3과 7이 들어온다. 3이 들어왔을 때는, 3이 제일 위에 있기 때문에(3밖에 없으니까) 3이 top이 된다. 이후 7이 들어오면서, 7이 top이 되고, 이후 pop을 수행한다면 7이 제일 먼저 내보내질 것이다.
이를 코드로 구현해보자. 기본적으로는 top위에 입력받은 data를 추가하지만, 문제가 생길 수 있다. 할당받은 영역 이상으로 데이터가 들어오는 경우, 다른 메모리 영역을 침범할 수 있다. 따라서, 이러한 문제가 발생하는 경우, 더 큰 영역을 할당받아야 한다. 필자의 경우 기존의 영역보다 2배크기의 영역을 새로 할당받았다. 듣기로는 C++에서도 이런식으로 처리한다고 들었던 것 같다.
여기서 질문이 생겼다. realloc은 인자로 입력받은 포인터와, 재할당한 후에 반환하는 포인터가 같음을 보장하지 않는다. 즉, 입력받은 포인터와 반환받은 포인터가 다를 수 있다. 그러면 이전에 존재하는 데이터는 어떻게 되는지가 궁금했다. 이러한 질문을 해결하기 위해 구글링을 하다가, 왠지 공식문서에 나와있을 것 같았다. 그렇게 공식문서에 들어가서 알아보았다. 그리고 realloc에 관한 문서를 찾았다.
https://en.cppreference.com/w/c/memory/realloc
realloc - cppreference.com
void *realloc( void *ptr, size_t new_size ); Reallocates the given area of memory. It must be previously allocated by malloc(), calloc() or realloc() and not yet freed with a call to free or realloc. Otherwise, the results are undefined. The reallocation i
en.cppreference.com
여기서 b)에 집중해보자. 영어를 못하지만, 단어를 찾아가면서 해석해보자면,
new_size바이트 만큼 새롭게 할당하고, 새로운 영역과 이전 영역중 더 작은 영역과 같은 메모리 영역을 복사한 후에, 이전 블록(메모리 영역)을 할당 해제합니다.
즉, realloc은 데이터를 복사해준다. 기존 데이터가 사라지는 상황은 일어나지 않는다.
void push(stack* st, int data){
if (st->_top + 1 == st->_max){
st->_max *= 2;
st->_stack = (int* )realloc(st->_stack, sizeof(int) * st->_max);
}
st->_stack[++st->_top] = data;
}
이때, _top은 이전의 top의 위치이기 때문에, 이 다음에 저장하기 위해서는 _top+1에 저장해야 한다.
3. pop
스택에서 데이터를 내보낼 pop함수를 구현해보자.
아까 push한 스택을 다시 살펴보자.
top데이터를 내보내고, top을 top-1에 위치한 데이터를 가르키게 한다. 동시에 데이터는 제거한다.
이를 코드로 옮겨보자.
void pop(stack* st){
if(st->_top != -1) {
st->_stack[st->_top--] = 0;
}
else return;
}
데이터를 제거하고, _top을 갱신하는 방법으로 구현했다.
4. size
stack구조체의 _top변수를 이용하여 알아내는 방법으로 해결했다.
int size(stack* st){
return st->_top + 1;
}
5. empty
역시 _top변수를 통해 알아낸다.
int empty(stack* st){
return st->_top == -1;
}
6. top
얘도 역시...
int top(stack* st){
return st->_stack[st->_top];
}
7. capacity
stack 구조체의 _max를 통해 알아낸다.
int capacity(stack* st){
return st->_max;
}
전체코드
#include <stdlib.h>
// implement using dynamic allocation
typedef struct stack{
int* _stack;
int _top;
int _max;
}stack;
stack* init_stack(){
stack* ret = (stack* )malloc(sizeof(stack));
ret->_top = -1;
ret->_max = 32;
ret->_stack = (int* )malloc(sizeof(int) * ret->_max);
return ret;
}
void push(stack* st, int data){
if (st->_top + 1 == st->_max){
st->_max *= 2;
st->_stack = (int* )realloc(st->_stack, sizeof(int) * st->_max);
}
st->_stack[++st->_top] = data;
}
void pop(stack* st){
if(st->_top != -1) {
st->_stack[st->_top--] = 0;
}
else return;
}
int size(stack* st){
return st->_top + 1;
}
int empty(stack* st){
return st->_top == -1;
}
int top(stack* st){
return st->_stack[st->_top];
}
int capacity(stack* st){
return st->_max;
}
테스트
스택을 구현했으니, 이제 사용해보자. 예제 코드를 올리겠다. 필자의 경우 스택을 구현한 파일을 stack.c이라고 저장하고 main에서 include했다. 원래는 헤더파일로 구성해야겠지만.... 귀찮으니 그냥 한다.
#include <stdio.h>
#include "stack.c"
void ps(stack* st){ // 스택 내부를 살펴보기 위한 함수
for (int i = 0; i <= st->_top; i++) {
printf("%3d ", st->_stack[i]);
if(i && i % 25 == 24) printf("\n");
}
printf("\n");
}
int main(){
stack* st = init_stack();
printf("%d / %d\n", size(st), capacity(st));
printf("empty -> %d\n", empty(st));
printf("----------\n");
for (int i = 1; i <= 150; i++) {
push(st, i);
}
printf("%d / %d\n", size(st), capacity(st));
printf("empty -> %d\n", empty(st));
ps(st);
printf("top -> %d\n", top(st));
printf("----------\n");
for (int i = 0; i < 160; i++) { // 입력받은 데이터보다 더 많이 pop해보면서 테스트해본다.
pop(st);
}
printf("%d / %d\n", size(st), capacity(st));
printf("empty -> %d\n", empty(st));
ps(st);
}
실행 결과
0 / 32
empty -> 1
----------
150 / 256
empty -> 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150
top -> 150
----------
0 / 256
empty -> 1
push도 문제없이 동작하는 걸 볼 수 있다. 또한, pop을 통해 _top를 감산하면서, 잘못된 값을 가지지도 않는다(-1보다 더 작은 값).
활용
그러면 스택은 어디에 쓸까? 저번 자료구조를 설명하는 글에서도(https://codejin.tistory.com/164), 스택을 활용하기에 최적인 상황에서 사용할 것이다. 스택의 특성을 다시한번 기억해보자. 스택은 후입선출, LIFO구조이다.
일단 웹 브라우저에서, 뒤로가기의 기능이 스택을 활용할 것이다. A -> B -> C의 사이트를 거쳐 D사이트에 있다고 치자. 스택에 우리가 웹사이트를 옮길때 마다, 우리가 이전에 있던 사이트를 스택에 push한다. 그러다가 뒤로가기를 수행할 때, top을 통해 이전 사이트로 이동하면서, 스택을 pop한다.
또 실행취소(undo)가 있다. 윈도우에서 문서작업하다가, 이전상황으로 돌아갈 때, ctrl + z를 쓴다. 이 역시 스택을 활용할 수 있다. 변경사항이 있을 때마다, 이를 스택에 push한다. 그러다가 undo를 실행하면, top의 상황을 가져온 후에, pop하면 된다.
느낀 점
사실 연결리스트에 비해서는 구현하는게 상당히 쉬웠다. 다음에는 C++의 클래스를 통해 여러 데이터에 적용할 수 있도록 만들어 보고 싶다.
'Data Structure' 카테고리의 다른 글
| [C] 이중 연결 리스트(Doubly Linked List)를 이용한 큐(Queue) 구현 (0) | 2022.03.02 |
|---|---|
| 자료구조란? (0) | 2022.02.18 |
| [C] 단일 연결 리스트(Single linked list) 구현 (2) | 2022.01.15 |
