스택 추상 데이터 타입
스택(stack)은 가장 최근에 들어온 데이터가 가장 위에 있고, 또 먼저 나가게 된다.
이런 입출력 형태를 후입 선출(LIFO : Last-In First-Out)이라고 한다.
스택은 이러한 후입 선출의 형식으로 입출력이 일어나는 자료 구조이다.
스택은 제일 먼저 입력된 데이터가 맨 아래에 쌓이고 가장 최근에 입력된 데이터가 가장 위에 쌓이는 구조를 가지고 있다.
스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다.
스택에서 입출력이 이루어지는 부분을 스택 상단(stack top)이라고 하고 반대쪽 바닥 부분을 스택 하단(stack bottom)이라고 한다.
스택에 저장되는 것을 요소(element)라고 부른다.
스택에 요소가 하나도 없을 때 스택을 공백 스택(empty stack)이라고 한다.
스택을 추상 자료형으로 정의해보자. 추상 자료형으로서의 스택은 스택의 상태를 변화시키는 연산들과 스택의 현재 상태를 검사하는 연산들로 구성된다.
객체 : n개의 element 타입의 요소들의 순서 있는 모임
연산 : create() - 스택을 생성한다.
is_empty(s) - 스택이 비어 있는지를 검사한다.
is_full(s) - 스택이 가득 찼는가를 검사한다.
push(s,e) - 스택의 맨 위에 요소 e를 추가한다.
pop(s) - 스택의 맨 위에 있는 요소를 삭제한다.
peek(s) - 스택의 맨 위에 있는 요소를 삭제하지 않고 반환한다.
스택에는 두 가지의 기본 연산이 있다.
하나는 삽입 연산으로 push 연산이라고 하고, 또 하나는 삭제 연산으로 pop연산이라고 한다.
is_empty와 is_full 연산은 스택이 공백 상태에 있는지와 포화 상태에 있는지를 검사하는 함수이다.
create 연산은 스택을 생성한다. peek 연산은 요소를 스택에서 삭제하지 않고 보기만 하는 연산이다.
pop 연산은 요소를 스택에서 완전히 삭제하면서 가져온다.
스택은 특히 자료의 출력 순서가 입력 순서의 역순으로 이루어져야 할 경우에 매우 간요하게 사용된다.
예를 들면 에디터에서 되돌리기(undo) 기능을 구현할 때 스택을 사용할 수 있다.
왜냐하면 수행된 명령어들 중에서 가장 최근에 수행된 것부터 되돌리기를 하여야 하기 때문이다.
가장 전형적인 스택의 사용 예는 함수 호출에서 복귀 주소를 기억하는 데 스택을 사용하는 것이다.
함수는 실행이 끝나면 가장 최근에 자신을 호출한 함수로 되돌아가야 한다.
이런 경우에 스택이 효과적으로 사용될 수 있다.
즉 함수가 호출된 순으로 스택에 현재 실행 중인 문장의 다음 번째 문장의 주소를 저장하고 하나의 함수가 끝나면 스택에서 복귀주소를 구해서 그곳으로 되돌아가는 것이다.
이 경우 사용되는 스택은 컴퓨터의 운영 체제만 사용하는 시스템 스택으로 사용자는 접근할 수 없다.
이 시스템 스택에는 함수가 호출될 때마다 활성화 레코드(activation record)가 만들어지며 여기에 함수로부터 복귀 후에 실행될 명령어의 주소인 프로그램 카운터(pc, program counter)값이 기록된다.
이 프로그램 카운터 값이 복귀 주소가 된다.
활성화 레코드에는 프로그램 카운터뿐만 아니라 함수 호출 시 매개 변수와 함수 안에서 선언된 지역 변수들이 함께 저장된다.
스택을 구현하는 방법에는 배열을 이용하는 방법과 연결 리스트를 이용하는 방법이 있다.
배열로 구현하는 방법은 간단한 반면에 스택의 크기가 고정되는 약점이 있다.
연결 리스트를 이용하는 방법은 구현이 약간 복잡한 반면, 스택의 크기를 필요에 따라 가변적으로 변경할 수 있다.
배열로 구현한 스택
앞에서의 추상 자료형으로 공부했던 스택을 배열을 이용하여 구현해보자.
스택에는 여러 가지 필요한 내용을 넣을 수 있으나 여기서는 간단하게 int타입의 정수가 저장되는 것으로 하자.
따라서 int 타입의 1차원 배열 stack[MAX_STACK_SIZE]가 필요하다.
이 배열을 이용하여 스택의 요소들을 저장하게 된다.
또한 스택에서 가장 최근에 입력되었던 자료를 가리키는 top 변수가 필요하다.
가장 먼저 들어온 요소는 stack[0]에, 가장 최근에 들어온 요소는 stack[top]에 저장된다.
top 변수는 스택에 아무런 데이터가 없으면 -1의 값을 갖는다.
0의 값을 가지면 안 되는 것을 이해해야 한다.
c언어의 배열에서 첫 번째 요소의 인덱스가 0이기 때문에 top의 값이 0이면 배열의 인덱스 0에 데이터가 있다는 것을 의미한다.
- is_empty 연산 : 스택이 비어 있는지를 검사하기 위하여 top을 -1과 비교한다. 만약에 top이 -1이면 TRUE가 반환될 것이다.
- is_full 연산 : 스택이 가득 차 있는지를 검사하기 위하여 top을 MAX_STACK_SIZE-1 와 비교하여 같으면 포화 상태로 판정한다. 만약 top이 MAX_STACK_SIZE-1 이면 더 이상의 삽입은 불가능하다.
- push 연산 : 스택에 새로운 요소를 삽입하기 전에 필요한 것은 스택이 가득 차지 않았나를 검사하는 것이다. 이것은 is_full()를 호출하여 검사하고 스택이 가득 차 있다면 오류 메세지가 출력되고 함수는 그냥 반환한다.
push()에서는 먼저 top의 값을 증가하는 것을 유의하라. top을 가리키는 위치는 마지막으로 삽입되었던 요소이므로 top을 증가시키지 않고 삽입하면 마지막 요소가 지워지게 된다.- pop 연산 : 스택에서 하나의 요소를 제거하는 연산으로 top이 가리키는 요소를 스택에서 꺼내어 외부로 건네주는 연산이다. 먼저 요소를 제거하기 전에 스택이 비어 있는지를 검사해야 한다.
스택의 공백 여부는 is_empty()를 호출하여 검사하고 스택이 비어 있으면 오류 메세지를 출력한다.
스택이 비어 있지 않으면 top이 가리키는 값을 반환하고 top을 하나 감소시킨다.
전역 변수로 구현하는 방법
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
typedef int 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, "스택 포화 에러\n");
return;
}
else {
stack[++top] = item;
}
}
element pop() {
if (is_empty()) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else {
return stack[top--];
}
}
element peek() {
if (is_empty()) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else {
return stack[top];
}
}
void main() {
push(1);
push(2);
push(3);
printf("%d\n", pop());
printf("%d\n", pop());
printf("%d\n", pop());
printf("%d\n", is_empty());
return 0;
}
그러나 이 방법은 만약 프로그램에서 하나 이상의 스택을 사용해야 할 때는 상당히 곤란해진다.
그리고 전역 변수를 사용하는 것은 프로그램을 복잡하게 만들어서 오류가 발생할 가능성을 높인다.
만약 스택에 저장되어야 하는 값이 정수나 문자가 아니고 더 복잡한 구조를 갖는 요소라면 어떻게 해야 할까?
이런 경우에는 스택의 요소를 정수가 아니라 구조체로 만들면 된다.
구조체 안에 필요한 모든 정보를 넣으면 된다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#define MAX_STACK_SIZE 100
#define MAX_STRING 100
typedef struct {
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, "스택 포화 에러\n");
return;
}
else {
stack[++top] = item;
}
}
element pop() {
if (is_empty()) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else {
return stack[top--];
}
}
element peek() {
if (is_empty()) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else {
return stack[top];
}
}
void main() {
element ie, oe;
strcpy(ie.name, "킹우현");
strcpy(ie.address, "동탄신도시");
ie.student_no = 201820734;
push(ie);
oe = pop();
printf("name: %s\n", oe.name);
printf("address: %s\n", oe.address);
printf("student number: %d\n", oe.student_no);
}
지금부터는 스택에 저장되는 요소의 타입은 항상 element라고 가정한다.
만약 정수 스택이 필요하면 element 타입을 정수로 정의하면 되고, 구조체가 필요하면 element 타입을 정의할 때 구조체로 정의하면 된다.
관련된 데이터를 함수의 매개 변수로 전달하는 방법
앞의 방법의 결점은 stack 배열과 top이 전역 변수로 선언되기 때문에 전체 프로그램에서 여러 개의 스택을 사용하기가 어렵다는 점이다.
최근의 C++이나 자바의 경우에는 이 문제를 객체 지향의 개념을 이용하여 우아하게 해결할 수 있다.
그러나 C에서도 다음과 같이 하면 이 문제를 어느 정도 완화할 수 있다.
즉, top과 stack 배열을 하나의 구조체로 결합시켜서 이 구조체의 포인터를 함수의 매개 변수로 전달한다.
다시말해서 StackType이라는 새로운 구조체 타입을 만들고 여기에 stack배열과 top을 넣는다.
그리고 이 구조체의 포인터를 각 함수의 매개 변수로 전달하는 것이다.
이렇게 하면 쉽게 여러 개의 스택을 만드는 것이 가능해진다.
즉, 필요할 때마다 StackType 타입의 구조체를 만들면 된다.
앞으로 모든 자료 구조는 이러한 방식으로 구현될 것이다.
이 방법에서는 StackType 구조체 안에 들어 있는 변수들을 초기화하기 위하여 init 함수가 필요하다.
여기서 주의할 것은 스택을 초기화하기 위하여 1차원 배열을 0으로 채울 필요는 없다.
배열에 어떤 값이 존재하더라도 top의 값만 -1로 하면 스택은 비어 있는 것으로 간주된다.
#include <stdio.h>
#define MAX_STACK_SIZE 100
typedef int element;
typedef struct {
element stack[MAX_STACK_SIZE];
int top;
}StackType;
void init(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));
}
void push(StackType* s, element item) {
if (is_full(s)) {
fprintf(stderr, "스택 포화 에러\n");
return;
}
else {
s->stack[++(s->top)] = item;
}
}
element pop(StackType* s) {
if (is_empty(s)) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else {
return s->stack[(s->top)--];
}
}
element peek(StackType* s) {
if (is_empty(s)) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else {
return s->stack[s->top];
}
}
void main() {
StackType s;
init(&s);
push(&s, 1);
push(&s, 2);
push(&s, 3);
printf("%d\n", pop(&s));
printf("%d\n", pop(&s));
printf("%d\n", pop(&s));
printf("%d\n", is_empty(&s));
}
위의 코드에서 약간 복잡해지는 요인은 구조체가 아니라 구조체의 포인터를 각 함수에 전달하여야 한다는 점이다.
각 함수에서는 구조체의 포인터를 이용하여 스택을 조작한다.
이것은 C언어에서의 함수 매개 변수 전달 방식이 기본적으로 값 전달 방식(call by value)이기 때문이다.
즉 구조체를 함수 매개 변수로 전달하였을 경우, 구조체의 원본이 전달되는 것이 아니라 구조체의 복사본이 함수에 전달된다.
따라서 함수 안에서는 복사본을 수정하여도 원본에는 영향을 주지 못한다.
그러나 원본에 대한 포인터를 전달하면 원본을 변경할 수 있다.
스택의 상태를 변경하지 않는 is_empty, is_full, peek 에서는 구조체 복사본을 함수에 전달할 수 있지만 구조체 복사에 따른 부담이 고려되어야 한다.
위 코드는 c언어 프로그램에서 여러 개의 스택을 만들 수 있다는 큰 장점이 있다.
따라서 이제부터는 이와 같은 방식을 이용하여 모든 추상 자료형을 구현하기로 한다.
