1. 1 스택이란?
스택(stack)은 컴퓨터에서 믿을 수 없을 정도로 많이 사용되는 자료 구조이다. 예를 들어서 우리가 스마트폰에서 "뒤로 가기" 키를 누르면 현재 수행되는 앱이 종료되고 이전에 수행되던 앱이 다시 나타난다. 이때 스택이 사용된다. 스택을 영어사전에서 찾아보면 '(건초, 밀집 따위를 쌓아놓은) 더미, 낟가리'를 의미한다고 되어 있다. 식당에 쌓여있는 접시 더미, 책상에 쌓여있는 책, 창고에 쌓여있는 상자 등이 스택의 전형적인 예이다.
스택에는 두 가지의 기본 연산이 있다. 하나는 삽입 연산으로 push 연산이라고 하고 또 하나는 삭제 연산으로 pop 연산이라고 한다. [그림 2]는 스택에서의 일련의 push 연산과 pop 연산을 보여주고 있다. push(1)를 수행하면 비어 있는 스택에 1이 삽입된다. 다시 push(2)가 수행되면 1위에 2가 쌓이게 된다. 그다음으로 pop()이 수행되면 가장 위에 쌓여있던 2가 삭제된다.
만약 상자를 쌓을 때 만약 쌓을 공간이 없다면 상자를 쌓을 수 없다. 마찬가지로 push 연산중에 스택이 가득 차서 입력이 불가능하다면 오류가 발생한다. 또 상자더미에 상자가 있어야 만이 상자를 가져갈 수 있는 것처럼 pop 연산중에 스택에
데이터가 없어서 출력이 불가능 하다면 역시 오류가 발생한다.
위와 같은 상황을 방지하기 위해 is_empty 와 is_full 연산은 스택이 공백상태에 있는지 포화상태에 있는지를 검사하는
함수이다. create 연산은 스택을 생성한다. peek연산은 요소를 스택에서 삭제하지 않고 보기만 하는 연산이다. 이에 반하여 pop 연산은 요소를 스택에서 완전히 삭제하면서 가져온다.
- 상단(stack top) : 스택에서 입출력이 이루어지는 부분
- 하단(stack bottom) : 반대쪽 바닥 부분
- 요소(element) : 스택에 저장되는 것
- 공백 스택(empty stack) : 공백 상태의 스택
- 포화 스택(full stack) : 포화 상태의 스택(풀스택)
1.2 스택 추상자료형
스택을 추상 자료형으로 정의해 보았을 때, 스택(Stack)은 후입선출(LIFO)(Last In Frist Out)의 접근방법을 유지하는 0개 이상의 요소를 지닌 선형 리스트의 일조이라 할 수 있다.
| 연산 | 기능 |
| init() | 스택을 초기화 |
| is_empty() | 스택이 비어있는지 검사 |
| is_full() | 스택이 가득 찼는지 검사 |
| push(e) | 스택의 맨 위에 요소 e추가 |
| pop(s) | 스택의 맨 위 요소를 삭제 |
| peek(s) | 스택의 맨 위 요소를 삭제하지 않고 반환 |
1.3 스택의 구현
스택을 구현하는 방법에는 배열을 이용하는 방법과 연결 리스트를 이용하는 방법이 있다. 배열은 구현하는 방법은 간단하고 성능이 우수한 반면 스택의 크기가 고정되는 약점이 있다. 연결리스트를 이용하는 방법은 구현이 약간 복잡한 반면, 스택의 크기를 필요에 따라 가변적으로 할 수 있다. 연결리스트를 사용하는 스택은 다음에 다루어 보겠다.
앞서 추상 자료형 스택을 1차원 배열을 이용하여 구현해보자. 스택에는 여러 가지 필요한 내용을 넣을 수 있으나 여기서는 간단하게 int 타입의 정수가 저장되는 것으로 하자.
- top : 가장 최근에 입력되었던 자료를 가리키는 top변수
- stack [0].... stack [top] : 먼저 들어온 순으로 저장
- 공백상태 : top = -1
▼ 알고리즘 1.1 스택의 is_empty 연산(Pseudo code)
is_empty(s):
if top == -1
then return True
else return False위의 의사코드는 is_empty()는 스택이 비어 있는 지를 검사하기 위하여 top을 -1과 비교한다. 만약 top이 -1이면 TRUE가 반환될 것이다.
▼ 알고리즘 1.2 스택의 is_full 연산(Pseudo code)
is_full(s):
if top >= (MAX_STACK_SIZE - 1)
then return True
else return False위의 의사코드는 is_full()은 스택이 가득 차 있는지를 검사하기 위하여 top을 (MAX_STACK_SIZE - 1)과 비교하여 같으면 포화 상태로 판정한다. 한 가지 주의할 점은 C언어에서는 배열의 인덱스가 0부터 시작하므로 top의 값이 (MAX_STACK_SIZE - 1) 이면 배열의 끝까지 요소가 채워져 있음을 의미한다. 만약 top이 (MAX_STACK_SIZE - 1) 이면 더 이상의 삽입은 불가능하다.
▼ 알고리즘 1.3 스택의 push 연산(Pseudo code)
push(S, x):
if is_full(S)
then error "overflow"
else top <- top+1
stack[top] <- x위의 의사코드는 push연산을 의사 코드로 표현한 것이다. push()에서 스택에 새로운 요소를 삽입하기 전에 필요한 것은 스택이 가득 차지 않았나를 검사하는 것이다. 이것은 is_full()을 호출하여 검사한다. 스택이 가득 차 있다면 오류 메시지가 출력되고 함수는 그냥 반환된다.
push()에서는 먼저 top의 값을 증가하는 것을 유의하라. top이 가리키는 위치는 마지막으로 삽입되었던 요소이므로 top을 증가시키지 않고 삽입하면 마지막 요소가 지워지게 된다.
▼ 알고리즘 1.4 스택의 pop연산(Pseudo code)
pop(S, x):
if is_empty(S)
then error "underflow"
else e<-stack[top]
top<-top-1
return e위의 의사코드는 pop연산으로 스택에서 하나의 요소를 제거하는 연산으로 top이 가리키는 요소를 스택에서 꺼내어 외부로 건네주는 연산이다. 먼저 요소를 제거하기 전에 스택이 비어있는지를 검사해야 한다. 스택의 공백여부는 is_empty()를 호출하여 검사한다. 스택이 비어 있으면 에러 메시지를 출력한다. 스택이 비어 있지 않으면 top이 가리키는 값을 반환하고 top을 하나 감소시킨다.
2) 스택의 구현방법
2 - 1) 전역 변수로 구현하는 방법
#include<stdio.h>
#include<stdlib.h>
#define MAX_STACK_SIZE 100 //스택의 최대 크기
typedef int element; //데이터의 자료형
element stack[MAX_STACK_SIZE]; //1차원 배열
int top = -1;
//공백 상태 검출 함수
int is_empty() {
return (top == -1);
}
//포화 상태 검출 함수
int is_full() {
return (top == (MAX_STACK_SIZE - 1));
}
//삽입 함수
void push(element item) {
if (is_full()) {
fprintf(stderr, "Stack overflow:(\n");
return;
}
else stack[++top] = item;
}
//삭제함수
element pop() {
if (is_empty()) {
fprintf(stderr, "Stack underflow:(\n");
exit(1);
}
else return stack[top--];
}
element peek() {
if (is_empty()) {
fprintf(stderr, "Stack is empty:(\n");
exit(1);
}
else return stack[top];
}
int main(void) {
push(1);
push(2);
push(3);
push(4);
printf("%d\n", pop());
printf("%d\n", pop());
printf("%d\n", pop());
return 0;
}
1차원 배열과 top변수를 모두 전역 변수로 구현했다. 전역 변수로 구현되기 때문에 배열이나 top 변수를 함수의 매개 변수로 전달할 필요가 없다. 스택에 저장되는 데이터의 타입은 typedef을 이용하여 element로 정의되었다. 현재는 정수형으로 정의되어 있다. push연산은 top을 먼저 증가시킨 다음, 증가된 위치에 데이터를 저장한다. pop연산은 먼저 top이 가리키는 위치에서 데이터를 꺼내온 다음, top을 하나 감소한다.
2 - 2) 스택의 요소를 구조체로 하기
만약 스택에 저장되어야 하는 값이 정수나 문자가 아니고 더 복잡한 구조를 갖는 요소이면 어떻게 해야 할까? 예를 들면 학생에 대한 정보라면 학생의 학번, 이름, 주소 등의 정보가 요소에 포함되어야 할 것이다. 이런 경우에는 스택에 구조체를 저장하면 된다. 구조체 안에 필요한 정보를 넣으면 된다. 아래는 구조체로 이루어진 일반적인 스택에 대한 코드를 나타낸 것이다.
#include<stdio.h>
#include<stdlib.h>
#define MAX_STACK_SIZE 100
#define MAX_STRING 100
typedef struct element {
int student_no;
char name[MAX_STRING];
char address[MAX_STRING];
}element;
element stack[MAX_STACK_SIZE];
int top = -1;
//공백 상태 검출 함수
int is_empty() {
return (top == -1);
}
//포화 상태 검출 함수
int is_full() {
return (top == (MAX_STACK_SIZE - 1));
}
//삽입 함수
void push(element item) {
if (is_full()) {
fprintf(stderr, "Stack overflow :(\n");
return;
}
else stack[++top] = item;
}
//삭제 함수
element pop() {
if (is_empty()) {
fprintf(stderr, "Stack underflow :(\n");
exit(1);
}
else return stack[top--];
}
//피크 함수
element peek() {
if (is_empty()) {
fprintf(stderr, "Stack is empty :(\n");
exit(1);
}
else return stack[top];
}
int main(void) {
element ie = {
202021000,
"Kim",
"Bundang"
};
element oe;
push(ie);
oe = pop();
printf("학번 : %d\n", oe.student_no);
printf("이름 : %s\n", oe.name);
printf("주소 : %s\n", oe.address);
return 0;
}
2 - 3) 관련된 데이터를 함수의 매개변수로 전달하는 방법
앞에서 설명한 방법은 이해하기 쉽게 구현하기 쉽지만 약간의 단점이 있다. stack 배열과 top이 전역변수로 선언되기 때문에 하나의 프로그램에서 여러 개의 스택을 동시에 사용하기가 어렵다는 점이다. C++ 나 자바의 경우에는 이 문제를 객체지향의 개념을 이용하여 해결할 수 있다. 그러나 C언어에서도 이 문제를 어느 정도 완화할 수 있다.
top과 stack 배열을 하나의 구조체로 결합시키고 이 구조체의 포인터를 함수로 전달한다. 즉, StackType이라는 새로운 구조체 타입을 만들고 여기에 stack 배열과 top을 넣는다.
그리고 이 구조체에 대한 포인터를 각 함수의 매개변수로 전달하는 것이다.
아래 코드를 참고해 보자.
#include<stdio.h>
#include<stdlib.h>
#define MAX_STACK_SIZE 100
typedef int element;
typedef struct StackType { //스택을 구조체로 정의
element data[MAX_STACK_SIZE];
int top;
}StackType;
//스택 초기화 함수
void init_stack(StackType* s) {
s->top = -1; //top == -1 이면 스택이 비어있다는 의미이다.
}
//공백 상태 검출 함수
int is_empty(StackType* s) {
return (s->top == -1);
}
//포화 상태 검출 함수
int is_full(StackType* s) {
return(s->top == MAX_STACK_SIZE - 1);
}
//삽입함수
void push(StackType* s, element item) {
if (is_full(s)) {
fprintf(stderr, "Stack overflow:(\n");
return;
}
else
s->data[++(s->top)] = item;
}
//삭제함수(검출)
element pop(StackType* s) {
if (is_empty(s)) {
fprintf(stderr, "Stack underflow:(\n");
exit(1);
}
else
return s->data[(s->top)--]; //현재 데이터 필드에 있는 꼭대기의 있는 값을 꺼내서 보여주기
}
//피크함수
element peek(StackType* s) {
if (is_empty(s)) {
fprintf(stderr, "Stack is empty!:(\n");
exit(1);
}
else
return s->data[(s->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("%d\n", pop(&s));
printf("%d\n", pop(&s));
printf("%d\n", pop(&s));
printf("%d\n", pop(&s));
printf("\n스택의 맨 위에 있는 data : %d\n", peek(&s));
/*
출력 : 5 4 3 2
스택의 맨 위에 있는 data : 1
*/
return 0;
}
위의 코드에서 StackType 구조체 안에 들어 있는 변수들을 초기화하기 위하여 init_stack() 함수가 필요하다. 여기서 주의할 것은 스택을 초기화하기 위하여 1차원 배열을 0으로 채울 필요는 없다. 배열에 어떤 값이 존재하더라도 top값만 -1로 하면 스택은 비어 있는 것으로 간주된다.
구조체의 포인터를 각 함수에 전달하여야 한다는 점이다. 각 함수에서는 구조체의 포인터를 이용하여 스택을 조작한다. 이것은 C언어에서의 함수 매개변수 전달 방식이 기본적으로 값 전달 방식(Call-by-value)이기 때문이다.
즉, 구조체를 함수의 매개변수로 전달하였을 경우, 구조체의 원본이 전달되는 것이 아니라 구조체의 복사본이 함수에 전달된다.
(위의 밑줄 친 자세한 내용은 아래 포스팅을 참고!!!)
https://kgw-software-study.tistory.com/10
C언어 - 포인터와 함수에 대한 이해
1. 함수의 인자로 배열 전달하기 이번 포스팅에서는 함수의 인자로 배열 전달하는 방법에 대해서 알아보겠다. 우리가 함수호출 시 전달되는 인자의 값은 매개변수에 복사가 된다. 즉, 복사가 되
kgw-software-study.tistory.com
위의 코드를 사용하면 여러 개의 스택을 동시에 만들 수 있다는 큰 장점이 존재한다. 따라서 이제부터는 이 방식을 이용하여 각종 자료구조들을 구현하겠다.
2 - 3) 스택을 동적 메모리 할당으로 생성하는 방법
앞에서는 모두 컴파일 시간에 크기가 결정되는 1차원 배열을 사용하였다. 따라서 컴파일 시간에 필요한 스택의 크기를 알아야 하는데 실제로는 아주 어렵다. C언어에서는 malloc()을 호출하여서 실행 시간에 메모리를 할당받을 수 있다.
이 기능을 사용하면 필요할 때마다 스택의 크기를 동적으로 늘릴 수 있다.
아래 코드를 참고해 보자.
#include<stdio.h>
#include<stdlib.h>
#define MAX_STACK_SIZE 100
typedef int element;
typedef struct StackType {
element* data; //data는 포인터로 정의
int capacity; //현재 크기
int top;
}StackType;
//스택 생성 함수
//스택이 만들어질 때, 1개의 요소를 저장할 수 있는 공간을 일단 확보한다.
void init_stack(StackType* s) {
s->top = -1;
s->capacity = 1;
s->data = (element*)malloc(s->capacity * sizeof(element));
}
//스택 삭제 함수
void delete_stack(StackType* s) {
free(s->data); //동적 메모리 할당으로 스택을 생성해주었으므로 삭제할때는 메모리 해제를 해주는 free를 해준다.
}
//공백 상태 검출 함수
int is_empty(StackType* s) {
return (s->top == -1);
}
//포화 상태 검출 함수
int is_full(StackType* s) {
return (s->top == s->capacity - 1);
}
//삽입함수
void push(StackType* s, element item) {
if (is_full(s)) {
s->capacity *= 2;
s->data = (element*)realloc(s->data, s->capacity * sizeof(element));
}
s->data[++(s->top)] = item;
}
element pop(StackType* s) {
if (is_empty(s)) {
fprintf(stderr, "Stack underflow:(\n");
exit(1);
}
else return s->data[(s->top)--];
}
element peek(StackType* s) {
if (is_empty(s)) {
fprintf(stderr, "Stack is empty!:(\n");
exit(1);
}
return s->data[(s->top)];
}
int main(void) {
StackType s;
init_stack(&s);
push(&s, 1);
push(&s, 2);
push(&s, 3);
push(&s, 4);
push(&s, 5);
push(&s, 6);
printf("%d\n", pop(&s));
printf("%d\n", pop(&s));
printf("%d\n", pop(&s));
printf("%d\n", pop(&s));
printf("\n스택의 맨 위에 있는 값 : %d\n", peek(&s));
free(s.data);
//delete_stack(&s); //빠져나온 데이터는 동적 메모리 할당 해제
return 0;
}
여기서 init_stack 함수와 push 함수를 잘 살펴보자.
init_stack 함수에서는 스택이 만들어질 때, 1개의 요소를 저장할 수 있는 공간을 일단 확보한다.
그다음으로 push함수를 살펴보자. 기존의 push함수는 메모리 공간이 부족하면 오류 메시지를 출력하고 프로그램을 종료했었다. 하지만 동적 배열 스택을 활용한 프로그램에서는 메모리 공간이 부족하면 s->capacity *= 2를 통해 부족한 메모리를 2배로 더 확보한다.
참고자료 : C언어로 쉽게 풀어쓴 자료구조
'자료구조&알고리즘' 카테고리의 다른 글
| 3. tree(트리) [자료구조 & 알고리즘] (2) | 2024.05.24 |
|---|---|
| 2. 큐(queue) [자료구조 & 알고리즘] (0) | 2024.03.24 |
