[자료구조] 스택(Stack)

스택(stack) : 후입선출(LIFO:Last-In First-Out)의 방식(가장 최근에 들어온 데이터가 가장 먼저 나간다)을 이용한다.
 
스택에서 입출력이 이루어지는 부분을 스택 상단(stack top)이라 하고, 반대쪽인 바닥부분을 스택 하단(stack bottom)이라고 한다.
스택에 저장되는 것을 요소(element) 또는 항목이라고 한다.
스택에 요소가 하나도 없는 경우를 공백(empty) 상태라 하고 꽉 차서 더 이상 요소를 넣을 수 없는 상태를 포화(full) 상태라 한다.

---

배열을 이용한 스택의 구현

1차원 배열 stack[ ]

스택의 크기 : 배열의 크기
스택에 저장된 원소의 순서 : 배열 원소의 인덱스
인덱스 0번 : 스택의 첫번째 원소
인덱스 n-1번 : 스택의 n번째 원소
변수 top: 가장 최근에 입력되었던 자료를 가리키는 변수, 즉 스택에 저장된 마지막 원소에 대한 인덱스
공백상태 : top = -1 (초기값)
포화상태 : top = n-1

stack[0]… stack[top] : 먼저 들어온 순으로 저장

---

Stack_empty() 연산

Stack_empty()  
if top = -1 	
then return TRUE 	
else return FALSE

 

Stack_full() 연산

Stack_full()  
if top = MAX_STACK_SIZE - 1 	
then return TRUE 	
else return FALSE

 

init() 연산

init()  
top = -1;

 

size() 연산

size()  
return top + 1

 

push() 연산

push(x)   
if Stack_full(S) // 스택이 포화 상태면 overflow를 반환한다.       
then error "overflow"       
else top←top+1 // top를 1 증가 시키고 그 자리에 값을 집어 넣는다.           
data[top]←x

 

pop() 연산

pop()  
if Stack_empty() // 스택이 공백 상태면 underflow를 반환한다.     
then error "underflow"     
else e ← data[top] // top의 값을 추출하고 top를 1 감소시킨다.          
top ← top-1          
return e

---

구현

#include <iostream>
#define MAX_STACK_SIZE 100 // 배열의 크기
using namespace std;
typedef int Element; // Element 배열의 타입은 int형으로 정의한다.

Element Data[MAX_STACK_SIZE]; // 스택 배열
int top; // 스택의 top

void init_stack() { top = -1; } // 스택을 초기화한다.
int stack_empty() { return top == -1; } // 스택이 공백 상태면 참을 반환한다.
int stack_full() { return top == MAX_STACK_SIZE - 1; } // 스택이 포화 상태면 참을 반환한다.
int size() { return top + 1; } // 스택에 들어가 있는 원소의 개수를 반환한다.

void push(Element e) {
	if (stack_full())
		exit(1);
	Data[++top] = e;
}

Element pop() {
	if (stack_empty())
		exit(1);
	return Data[top--];
}

Element peek() {
	if (stack_empty())
		exit(1);
	return Data[top];
}

int main() {
	init_stack(); // 스택 초기화 한다.

	for (int i = 5; i < 10; i++) // 스택에 원소 5부터 9까지 5개를 넣는다.
		push(i);

	cout << size() << endl; // 스택의 원소가 5개가 차있는 모습을 볼 수 있다.

	pop();

	cout << size() << endl; // pop() 연산을 통해서 원소가 하나가 나간 것을 알 수 있다.

	return 0;
}