스택(Stack)은 데이터를 관리하는 자료구조 중 하나로, Last In First Out (LIFO) 원칙에 따라 동작한다. 따라서 한 쪽 끝에서만 데이터의 입출력이 가능하다.
스택(Stack)의 사용
- 함수 호출 및 재귀 알고리즘 (복귀 주소를 기억하기 위함)
- 편집기 등에서의 되돌리기 기능
- 자료를 쌓아 올리는 동작 등
스택의 활용
- 괄호 검사
- 후위 표기식 계산
스택의 주요 연산
- Push : 스택에 데이터를 삽입하는 연산으로, 스택의 맨 위에 요소를 추가한다.
- Pop : 스택의 맨 위에 있는 데이터를 제거하는 연산이다.
- Peek 또는 Top : 스택의 맨 위에 있는 데이터를 조회하는 연산으로, 삭제하지 않고 데이터를 확인한다.
- isEmpty : 스택이 비어있는지 확인하는 연산이다.
스택 구현 방법 비교
스택을 구현하는 방법은 배열과 연결 리스트가 있다. 각 방법을 비교하면 다음과 같다.
배열(Array) 기반 스택
- 크기가 고정되어 있으므로 스택의 크기를 늘리거나 줄이는 작업에 제약이 있을 수 있다. 이로 인하여 적은 양의 데이터를 저장하는데 크기를 크게 설정하면 메모리 사용량이 많아질 수도 있다.
- 비교적 간단하고 빠르게 구현할 수 있다.
- 스택이 가득 찼을 때 새로운 요소를 추가하기 위해 배열을 재조정해야 하는 경우 성능이 떨어질 수 있다.
연결 리스트(Linked List) 기반 스택
- 크기가 동적으로 조정되므로 스택의 크기를 유연하게 조절할 수 있다.
- 연결 리스트와 관련 알고리즘에 대한 사전 이해가 필요하다.
- 요소를 삽입하거나 삭제하는 작업이 상대적으로 효율적이다.
- 메모리 상에서 노드들이 연속적으로 배치되지 않으므로 약간의 오버헤드가 발생할 수 있다.
스택의 구현
기본적인 C언어에서는 STL(Standard Template Library)이 지원되지 않으므로 코드를 직접 구현해야 한다. C++ 언어에서는 스택을 포함한 많은 라이브러리를 표준으로 지원한다. STL에는 스택 뿐 아니라 큐(Queue), 컨테이너(Container), 알고리즘(Algorithm) 등 다양한 라이브러리가 포함되어 있다. 이로 인하여 필자도 문제 해결에 있어서 C++ 언어를 자주 사용하고 있다. 물론 수행 시간도 상대적으로 빠른 편이다.
배열(Array) 기반 스택
데이터를 저장하는 1차원 배열 data와 가장 최근에 입력된 요소를 가리키는 top 변수가 필요하다. 가장 먼저 입력된 요소는 data[0]에, 가장 최근에 입력된 요소는 data[top]에 저장된다. 만약 스택이 비어 있는 상태이면 top 변수의 값은 -1이 된다.
#define MAX_SIZE 100
typedef int element; // 데이터의 자료형
// 스택 구조체 정의
typedef struct {
element data[MAX_SIZE];
int top;
} Stack;
// 스택 초기화 함수
void init_stk(Stack* stk) {
stk->top = -1;
}
// 스택이 비어있는지 확인하는 함수
int is_stk_empty(Stack* stk) {
return stk->top == -1;
}
// 스택이 가득 찼는지 확인하는 함수
int is_stk_full(Stack* stk) {
return stk->top == MAX_SIZE - 1;
}
// 스택에 데이터를 추가하는 함수
void push(Stack* stk, element item) {
if (is_stk_full(stk)) {
printf("스택 오버플로\n");
return;
}
stk->data[++(stk->top)] = item;
}
// 스택에서 데이터를 추출하는 함수
element pop(Stack* stk) {
if (is_stk_empty(stk)) {
printf("스택 언더플로\n");
return -1; // 스택이 비어있으면 임의의 값으로 처리하거나 오류를 반환할 수 있음.
}
return stk->data[(stk->top)--];
}연결 리스트(Linked List) 기반 스택
먼저 연결 리스트의 노드를 정의해야 한다. 각 노드는 데이터를 저장하는 변수와 다음 노드를 가리키는 포인터를 저장하고 있다.
#include <stdio.h>
#include <stdlib.h>
typedef int element; // 데이터의 자료형
// 연결 리스트 노드 정의
typedef struct Node {
element data;
struct Node* next;
} Node;스택은 연결 리스트의 끝에 원소를 추가하고 삭제하는 연산을 수행한다. 따라서 스택의 push(추가) 및 pop(삭제) 연산은 다음과 같이 구현할 수 있다.
// 스택 구현
typedef struct Stack {
Node* top;
} Stack;
// 스택 초기화
void init_stk(Stack* stk) {
stk->top = NULL;
}
// 스택에 요소 추가
void push(Stack* stk, element data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = stk->top;
stk->top = newNode;
}
// 스택의 요소 제거 및 반환
element pop(Stack* stk) {
if (stk->top == NULL) {
printf("스택이 비어있습니다.\n");
return -1; // 예외 처리: 스택이 비어있을 경우
}
element data = stk->top->data;
Node* temp = stk->top;
stk->top = stk->top->next;
free(temp);
return data;
}연결 리스트 기반의 스택은 동적으로 메모리를 할당하므로 사용 후에는 메모리 해제를 잊지 말아야 한다. 프로그램 종료 시에는 free 함수로 사용한 모든 메모리를 해제해야 한다.
여기에서는 int 자료형을 저장하고 있다. 만약 다른 자료형을 저장하기 위해서는 위 코드의 element 자료형을 다른 자료형으로 변경하면 된다. STL을 사용하지 않고 직접 구현해보는 것도 실력 향상에 도움이 될 수도 있다. 가능하면 STL을 사용하는 것이 바람직하다고 생각된다.