스택이란?
일종의 리스트이나, 데이터의 삽입과 삭제가 한쪽 끝에서만 이루어진다는 특징을 가지는 자료 구조이다.
스택은 일종의 바구니와 같다. 물건을 여러 개 쌓으면 가장 위의 물건을 먼저 꺼내야 아래에 있는 물건들을 차례대로 꺼낼 수 있다.
이때 가장 맨 위의 데이터는 Top이다. 데이터를 삽입하는 것을 Push한다고 하고, 데이터를 꺼내는 것을 Pop한다고 한다. 이처럼 스택 구조에서는 나중에 넣은 값이 처음으로 나오게 된다. (LIFO, Last-In, First-Out)
- 스택의 주요 연산
| 연산 | 설명 |
|---|---|
| push | 스택에 새로운 데이터를 삽입한다. |
| pop | 스택의 top에 있는 원소를 스택에서 제거하고 반환한다. |
| peek | 스택의 top의 원소를 제거하지 않고 반환한다. |
| is_empty | 스택이 비어있는지 검사한다. |
| is_full | 스택이 가득 차 있는지 여부를 검사한다. |
스택은 배열로 구현할 수도 있고 연결리스트로 구현할 수도 있다. 각각의 구현 방법에 따른 장단점이 존재하기에 필요에 따라 구현 방법을 달리 한다.
1. 배열을 이용한 스택 구현
#define MAX_CAPACITY 100
char stack[MAX_CAPACITY]; // 저장되는 데이터 타입이 char형이라고 가정한다.
int top = -1;
int is_empty();
int is_full();
void push(char ch) {
if (is_full()) return; // 스택이 가득 차면 더 이상 push할 수 없다.
top++;
stack[top] = ch;
}
char pop() {
if (is_empty()) return; // pop을 호출하기 전에 empty인지 검사해야 한다.
char tmp = stack[top];
top--;
return tmp;
}
char peek() {
if (is_empty()) return;
return stack[top];
}
int is_empty() {
return top == -1;
}
int is_full() {
return top == 100 - 1;
}2. 연결리스트를 이용한 스택 구현
- stack.c
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
Stack create() {
Stack s = malloc(sizeof(struct stack_type));
if (s == NULL)
terminate("Error in create: stack could not be created.");
s->top = NULL;
return s;
}
void destroy(Stack s) {
make_empty(s);
free(s);
}
void make_empty(Stack s) {
while (!is_empty(s))
pop(s);
}
bool is_empty(Stack s) {
return s->top == NULL;
}
void push(Stack s, Item i) {
struct node* new_node = malloc(sizeof(struct node));
if (new_node == NULL)
terminate("Error in push: stack is full.");
new_node->data = i;
new_node->next = s->top;
s->top = new_node;
}
Item pop(Stack s) {
struct node* old_top;
Item i;
if (is_empty(s))
terminate("Error in pop: stack is empty.");
old_top = s->top;
i = old_top->data;
s->top = old_top->next;
free(old_top);
return i;
}
Item peek(Stack s) {
if (is_empty(s))
terminate("Error in peek: stack is empty.");
return s->top->data;
}- stack.h
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
// 스택의 자료형
typedef int Item;
typedef struct stack_type* Stack;
struct node {
Item data;
struct node* next;
};
struct stack_type {
struct node* top;
};
static void terminate(const char* message) {
printf("%s\n", message);
exit(1);
}
Stack create();
void destroy(Stack s);
void make_empty(Stack s);
bool is_empty(Stack s);
void push(Stack s, Item i);
Item pop(Stack s);
Item peek(Stack s);연결리스트를 이용한 구현에서는 stack.c 파일과 stack.h 파일을 분리하였다. 헤더 파일에 함수들을 선언해놓음으로써 다른 코드에서 스택을 사용할 때는 stack.h 파일만 인클루드하면 편하게 스택 구조를 사용할 수 있다.
스택에 저장되는 데이터의 자료형을 변경할 시에는 헤더 파일의 Item을 int가 아닌 다른 자료형으로 수정하면 된다.
연결리스트를 통한 스택 구현에서 top은 연결리스트의 head이다.
