이번 포스팅에서는 스택의 개념과 구조, 연산과 함께 스택을 각각 정적 및 동적으로 구현하는 방법에 대해서 정리해보았습니다.
📌 주요 개념
✔️ 스택(Stack)이란?
✔️ 스택 vs 리스트 vs 큐 (비교)
✔️ 스택 연산함수
✔️ 스택 구현방법 (정적/동적)
I. 스택(Stack)이란?
스택은 컴퓨터에서 아주 많이 사용되는 자료구조입니다. 예를 들어, 스마트폰 "뒤로 가기" 키를 눌렀을 때 현재 수행되는 앱이 종료되고 바로 직전에 수행되던 앱이 다시 나타나곤 하는데요, 이때 사용되는 것이 스택입니다.
스택(stack)은 말 그대로 '쌓아놓은 더미'를 뜻합니다. 식당에 쌓여있는 접시 더미, 책상에 쌓인 책, 겹겹이 쌓인 상자 모두 스택의 예에 해당합니다. 이 중에서도 가장 대표적인 예시로 '프링글스(Pringles)'를 들 수 있겠습니다.
※ 후입선출 (LIFO: Last-In First-Out)
스택의 가장 큰 특징은 후입선출('LIFO') 입니다. 가장 최근에 들어온 데이터가 가장 먼저 나간다는 의미인데요, 이는 과자 프링글스를 생각하면 쉽습니다. 젤 나중에 넣은 칩 조각을 가장 먼저 먹게 되는 것과 같은 이치죠. 이는 먼저 들어온 데이터가 먼저 나가는 '큐(Queue)' 와의 가장 큰 차이점 이라고도 할 수 있습니다.
※ 스택 vs. 큐 vs. 리스트
스택, 큐 모두 리스트 자료구조의 특별한 경우이며, 이들 간에는 공통점과 차이점을 지닙니다.
| 자료구조 | 공통점 | 차이점 |
| 리스트(List) | 선형 자료 구조, 순서가 있다 |
읽기, 삽입(insert)과 삭제(delete)를 리스트의 어느 곳에서나 행함 |
| 스택(Stack) | 삽입(insert)과 삭제(delete)를 리스트의 한쪽(top) 에서 행함 | |
| 큐(Queue) | 삽입(insert)은 리스트의 한쪽(rear)에서 하고, 삭제(delete)는 삽입의 반대쪽(front)에서 행함 |
II. 스택의 구조 & 사용
스택은 자료의 출력 순서가 입력 순서의 역순으로 이루어질 때 아주 요긴하게 사용되는 자료구조입니다.
문서 편집기에서 '되돌리기(undo)' 기능을 구현하면 바로 직전(최근)에 실행했던 작업이 취소되곤 하지 않나요? 그때 바로 이 스택 자료구조를 사용합니다.
- 상단(stack top) : 스택에서 입출력이 이루어지는 부분
- 하단(stack bottom): 반대쪽 바닥 부분
- 요소(element): 스택에 저장되는 것
- 공백 스택(empty stack): 공백 상태의 스택
- 포화 스택(full stack): 포화 상태의 스택 (풀스택!)
※ 시스템 스택(Stack) 함수호출
- 시스템 스택(system stack) : 운영체제가 사용하는 스택
- 복귀주소 기억
: 함수의 실행이 끝나면 자신을 호출한 함수로 되돌아갑니다. 이 때 스택은 복귀할 주소를 기억하는 데 사용됩니다. 함수는 호출된 역순으로 되돌아가야 하기 때문입니다.
- 활성 레코드
: 시스템 스택에는 함수가 호출될 때마다 활성 레코드(activation record)가 만들어지며, 이곳에 복귀 주소가 저장됩니다. 활성 레코드에 생성되는 정보는 아래와 같습니다.
- 복귀 주소
- 프로그램 카운터
- 매개변수
- 함수 안에서 선언된 지역변수
시스템 스택에는 아래 그림과 같은 순서로 활성 레코드가 만들어졌다가 없어지게 됩니다.
- 사용 예시
: Undo 기능, 괄호검사, 계산기, 미로탐색 등
III. 스택 추상자료형
스택을 추상 자료형으로 정의해 보았을 때, 스택(Stack)은 후입선출(LIFO)의 접근방법을 유지하는 0개 이상의 요소를 지닌 선형 리스트의 일종이라 할 수 있습니다.
1) 스택 ADT (추상데이터타입)
- 객체: n개의 요소(element)들의 선형 리스트
| 연산 | 기능 |
| init() | 스택을 초기화 |
| create() | 스택을 생성 |
| is_empty(s) | 스택이 비어있는지 검사 |
| is_full(s) | 스택이 가득 찼는지 검사 |
| push(e) | 스택의 맨 위에 요소 e 추가 |
| pop(s) | 스택의 맨 위 요소를 삭제 |
| peek(s) | 스택의 맨 위 요소를 삭제하지 않고 반환 |
2) 스택의 연산
: 스택에 요소를 추가/삭제하는 연산과, 현재 스택 상태를 검사하는 연산들로 구성됩니다.
| 연산 | 기능 |
| top() | 스택 맨 위에 있는 데이터 값 반환 |
| push() | 스택에 데이터 삽입 |
| pop() | 스택에서 데이터 삭제하여 반환 |
| isempty() | 스택에 원소가 없으면 'True', 있으면 'False' 값 반환 |
| isfull() | 스택에 원소가 없으면 'False', 있으면 'True' 값 반환 |
II. 스택의 정적/동적 구현
스택은 이전 챕터의 리스트와 마찬가지로 정적 또는 동적의 2가지 방법으로 구현될 수 있다.
1. 스택의 정적 구현 : 1차원 배열 사용
1) 스택의 생성
- top : 가장 최근에 입력되었던 자료를 가리키는 변수
- stack[0] ... stack[top] : 먼저 들어온 순으로 저장
- 공백 상태: top = -1
// 1차원 배열의 사용
# define MAX_STACK_SIZE 100
int stack[MAX_STACK_SIZE];
/* top의 초기 값은 스택이 비어있을 때 -1 이다. */
int top = -1;
2) 스택의 삽입 (Push)
void push(int item)
{
if (top >= MAX_STACK_SIZE - 1) {
stack_full();
return;
}
stack[++top] = item;
// top ++; stack[top] = item;
}// push(x)
if is_full(S)
then error "overflow"
else top <- top + 1
data[top] <- x
3) 스택의 삭제 (Pop)
int pop() {
if (top == -1)
return stack_empty();
// int x; x = stack[top]; top--; return x;
return stack[top--];
}// pop()
if is_empty()
then error "underflow"
else e <- data[top]
top <- top-1
return e
4) 스택의 검사 ( isempty / isfull )
// 스택이 비어있는지 검사하는 함수
int isempty()
{ if (top < 0)
return(1);
else
return(0);
}// 스택이 가득 차 있는지 검사하는 함수
int isfull()
{ if (top >= MAX_STACK_SIZE -1 )
return(1);
else
return(0);
}
2. 스택의 동적 구현 : 연결 리스트 사용
- 장점: 크기가 제한되지 않음
- 단점: 구현이 복잡, 삽입/삭제 시간이 오래 걸림
1) 스택의 생성
// 요소의 타입
typedef int element;
typedef struct StackNode {
// 노드의 타입
element item;
struct StackNode *link;
} StackNode; // 연결된 스택 관련 데이터
typedef struct {
StackNode *top;
} LinkedStackType;
2) 스택의 삽입
// 삭제 함수
element pop(LinkedStackType *s)
{
if( is_empty(s) ) {
fprintf(stderr, "스택이 비어있음\n");
exit(1);
}
else{
StackNode *temp = s->top;
int item = temp->item;
s->top = s->top -> link;
free(temp);
return item;
}
}
3) 스택의 삭제
// 삭제 함수
element pop(LinkedStackType *s)
{
if( is_empty(s) ) {
fprintf(stderr, "스택이 비어있음\n");
exit(1);
}
else{
StackNode *temp = s->top;
int item = temp->item;
s->top = s->top->link;
free(temp);
return item;
}
}
[참조 문헌/자료]
- C언어로 쉽게 풀어쓴 자료구조 (개정3판)