[자료구조] - 스택(Stack)의 구조와 구현

1. 스택(Stack)이란?

스택(stack)이란 단어의 사전적인 뜻은, "쌓아놓은 더미"이다. 

쌓아놓은 접시들을 생각하면 이해가 쉬울 것이다.

새로운 접시를 놓을 때는 맨 위에 놓고, 더미에서 접시를 꺼낼 때는 맨 위에 있는 접시를 꺼낸다.

 

후입선출 (LIFO : Last - In - First - Out)

스택의 중요한 특징이다. 앞서 말한 접시 더미의 예시처럼, 스택에서는 가장 마지막에 들어온 데이터가 가장 먼저 나간다는 뜻이다. 다시 말해, 스택에서의 입출력은 맨 위에서만 일어난다. (들어올때도 맨 위, 나갈때도 맨 위) 이러한 특징 때문에 스택의 중간에서는 데이터를 삽입하거나 삭제할 수 없다. 

 

2. 스택 구현을 위한 기본 함수

스택은 1차원 배열을 이용하여 간단한 방법으로 구현이 가능하다. 단 1차원 배열을 이용하면 스택의 크기가 고정된다는 단점이 있다. (스택의 크기를 가변적으로 구현하려면 연결리스트를 이용해야 한다.)

 

 

스택 구현을 위해 정의해야 할 함수들을 알아보자.

스택의 최대 크기를 MAX라고 하고, 스택의 맨 위에 있는 자료를 가리키는 top 변수를 설정한다. 여기서 top 변수는 배열의 인덱스 값과 같다고 생각하면 된다. 즉, 스택이 비어있을 때는 -1, 스택에 1개의 자료만 있을때는 0, 스택이 꽉 차있을 때는 (MAX-1) 의 값을 가진다.

 

 

 

 

 

is_empty 함수

스택이 비어있는지 검사하는 함수이다. 스택이 비어있으면 (= top의 값이 -1이면) TRUE(1), 아니면 FALSE(0)를 반환한다.

int is_empty()
     if (top == -1) return 1;
     else return 0;

 

 

is_full 함수

스택이 꽉 차있는지 검사하는 함수이다. 스택이 꽉 차있으면 (=top 값이 MAX-1이면) TRUE(1), 아니면 FALSE(0) 을 반환한다.

int is_full()
     if (top == MAX-1) return 1;
     else return 0;

 

 

push 함수

스택에 데이터를 삽입한다. 우선 is_full 함수를 이용하여 먼저 스택이 현재 꽉 차있는 상태인지 점검한 후 스택에 데이터를 삽입한다. 스택에서 데이터의 삽입은 항상 맨 위에서만 일어나므로, top 변수를 1 증가시켜준 후 데이터를 삽입한다.

void push (k)
     if (is_full() == 1)
          cout << "Overflow";
     else
          top++;
          stack[top] = k;

 

 

pop 함수

스택에서 데이터를 삭제한다. is_empty 함수를 이용하여 먼저 스택이 현재 비어있는 상태인지 점검한 후 스택의 맨 위에 있는 데이터를 삭제한다. 스택에서 데이터의 삭제는 맨 위에서만 일어나므로, 현재 top이 가리키는 위치의 데이터를 리턴 후 삭제, top을 1 감소시킨다. 

int pop ()
     if (is_empty() == 1)
          cout << "Empty!";
     else
          x = stack[top];
          top--;
          return x;

 

 

peek 함수

스택의 요소를 리턴하는 함수이다. pop 연산과 비슷하지만, pop은 맨 위 데이터를 리턴 후 삭제까지 하고, peek은 삭제 없이 데이터를 조회만 한다는 차이점이 있다. 

int peek ()
     if (is_empty() == 1)
          cout << "Empty!";
     else
          return stack[top];

 

 

 

3. 스택의 구현

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

#define MAX 100
int stack[MAX];
int top = -1;

//스택이 비어있는지 검사
int is_Empty(){
	if (top == -1)
		return 1;
	else
		return 0;
}

//스택이 꽉 차있는지 검사
int is_full() {
	if (top == (MAX-1)) //배열이므로 최대 크기는 (지정한 크기 - 1)
		return 1;
	else
		return 0;
}

//스택에 데이터 삽입
void push(int k) {
	if (is_full() == 1){
		cout << "Overflow";
        exit(1); //리턴값 없이 함수를 강제 종료
	}
	else {
		top++;
		stack[top] = k;
	}
}

//스택의 맨 위 데이터 반환 후 삭제
int pop() {
	if (is_Empty() == 1) {
		cout << "Empty!";
		exit(1); //리턴값 없이 함수를 강제 종료
	}
	else {
		int x = stack[top];
		top--;
		return x;
	}
}

//스택의 맨 위 데이터 출력
int peek() {
	if (is_Empty() == 1) {
		cout << "Empty!";
		exit(1); //리턴값 없이 함수를 강제 종료
	}
	else
		return stack[top];
}

int main() {
	cout << "Is Empty? (Yes: 1 / No : 0) => " << is_Empty() << "\n";
	push(1);	// 1 삽입
	push(2);	// 2 삽입
	push(3);	// 3 삽입
	cout << pop() << "\n";	// 3 반환 후 삭제
	cout << peek() << "\n";	// 2 반환
	cout << pop() << "\n";	// 2 삭제
	cout << "Is Empty? (Yes: 1 / No : 0) => " << is_Empty() << "\n";
	return 0;
}

C++ 함수로 구현한 스택이다. C언어로 구현하려면 cout 을 통해서 출력하는 부분만 printf로 바꿔주면 된다. 

stack[MAX]와 top 변수는 전역변수로 설정해주어야 다른 함수에서 자유롭게 사용이 가능하다. 

나는 스택의 데이터 자료형을 정수형(int)으로 설정하고 구현해 보았는데, float, double, char, string, 구조체 등 자료형을 변경하여 다양하게 활용할 수도 있다.