스택이란?
영어 Stack의 의미인 쌓다의 말 그대로 데이터를 밑에서부터 위로
차곡 차곡 쌓아 올리는 자료구조를 뜻합니다.
쉽게 설명하자면, 한번에 블럭 한 개만 넣을 수 있는 기다란 통이 있다고 가정해봅시다.
그러면 블럭을 추가 할 수록 제일 먼저 넣은 블록은 가장 바닥 쪽에 위치하게 되겠죠?
또한 블럭을 꺼내고 싶다면 가장 위에 있는 블럭부터 꺼낼 수 있겠죠?
그래서 스택의 가장 큰 특징은 가장 나중에 넣은 데이터를
가장 먼저 꺼낼 수 있다는 의미의 '후입선출(LIFO)' 입니다.
스택을 관리하기 위해 필요한 연산
그럼 이러한 자료구조를 구성한다면 어떤 연산이 필요할까요?
자료를 넣는 연산인 push()와
자료를 꺼내는 연산인 pop()
가장 최근 자료를 엿보는 peek()
등의 연산이 필요하게 됩니다.
C로 구현한 스택
아래는 C로 구현한 Stack 자료구조 입니다.
#define _CRT_SECURE_NO_WARNINGS
#define MAX_STACK_SIZE 5
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int data[MAX_STACK_SIZE];
int top;
} StackType;
// 스택 초기화
int init_stack(StackType* s)
{
s->top = -1;
}
// 스택이 비었는지 확인
int is_empty(StackType* s)
{
return (s->top == -1);
}
// 스택이 꽉 찼는지 확인
int is_full(StackType* s)
{
return (s->top == MAX_STACK_SIZE - 1); // 0부터 시작하기 때문에
}
void push(StackType* s, int item)
{
if (is_full(s)) {
fprintf(stderr, "스택 포화 에러\n");
return;
}
s->data[++(s->top)] = item; // top을 먼저 증가시키고, 대입
}
int pop(StackType* s)
{
if (is_empty(s)) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return s->data[(s->top)--]; // 데이터를 뽑아내고, top 감소
}
int peek(StackType* s)
{
if (is_empty(s)) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return s->data[s->top]; // top의 데이터 뽑기
}
int main(void)
{
StackType S;
init_stack(&S);
push(&S, 1);
push(&S, 2);
push(&S, 3);
push(&S, 4);
push(&S, 5);
printf("top: %d\n", peek(&S));
printf("remove top\n"); pop(&S); // 5삭제
printf("top: %d\n", peek(&S));
printf("remove top\n"); pop(&S); // 4삭제
printf("top: %d\n", peek(&S));
printf("remove top\n"); pop(&S); // 3삭제
printf("top: %d\n", peek(&S));
printf("remove top\n"); pop(&S); // 2삭제
printf("top: %d\n", peek(&S));
}
초기화 함수는 스택의 초기 설정을 위해 필요하구요,
공백 확인 함수는 pop 연산이 실행될 때,
만약 스택이 공백 상태이면 실행되지 않게 하기 위해 필요합니다.
포화 상태 확인 함수는 마찬가지로 push 연산이 실행될 때,
스택에 빈 자리가 없다면 실행되지 않게 하기 위해 필요합니다.
위의 코드를 실행하게 되면
top: 5
remove top
top: 4
remove top
top: 3
remove top
top: 2
remove top
top: 1
이러한 결과가 출력 됩니다.
프로그램 실행에 있어 필요한 스택 역시 가상 메모리에 적재되는데요,
스택은 지역 변수나 함수의 인자 등을 일시적으로 저장되고 사용되는 영역으로 쓰입니다.
윈도우 프로세스의 각 쓰레드는 자신만의 스택 공간을 가지고 있는데요,
이 영역은 자유롭게 읽고 쓸수 있어야 하기 때문에 읽기/쓰기 권한이 부여됩니다.
이에 대한 설명은 다음 링크를 참조하세요.
