[자료구조] 스택(Stack) 이란? 스택은 어디서 쓰는걸까?

안녕하세요, IT디자이너입니다.

 

이번에는 컴퓨터의 자료구조 스택(Stack)에 관하여 포스팅하도록 하겠습니다. 

 

 

- 스택(Stack)이란?

스택은 말 그대로 스택처럼 쌓아올리는 형태의 자료구조를 뜻합니다. 

 

쌓아 올리는 스택(Stakc)은 가장 마지막에 입력된 요소가 가장 먼저 출력됩니다. 이러한 특성의 자료구조를

(Last In First Out) 구조라고 합니다.

 

- 스택(Stack)의 top이란?

스택은 기본적으로 현재 스택의 위치를 가리키는 top 의 값을 이용하여 스택을 쌓거나 값을 출력합니다.

또한 배열을 이용하여 구현할 수 있으며, top 초기화 값은 -1로 하여 0번째 인덱스 부터 가리킬 수 있도록 구현합니다.

 

 

- 스택(Stack)에서 사용하는 함수

• Push() : 스택에 값을 넣는 함수입니다.
• Pop() : 스택의 top 위치에 있는 요소를 출력하는 함수입니다. 
• Peek() : 푸쉬의 가장 마지막에 입력된 값 즉, 탑 위치의 값을 확인하는 함수입니다.
• isFull() : 스택이 꽉 찼는지 확인하는 함수입니다.
• isEmpty() : 스택이 현재 비어있는지 확인하는 함수입니다. 

 

스택의 기본구조

 

 

- 스택(Stack) 구현

※ 자료구조에서 사용하는 모든 함수의 반환형은 반드시 bool 탑으로 true or false만 반환하도록 하여야합니다.!!!

   함수 내에서의 출력하지 않도록 주의해주세요~!!

 

#include <iostream>
#include <Windows.h>

using namespace std;

#define MAX_STACK 10

int stack[MAX_STACK];

int top = -1;

bool Push(int val); // 스택에 값을 넣는 함수

bool Pop(int *val); // 스택에 값을 출력하는 함수

bool isFull(); // 스택이 꽉 찼는지 확인하는 함수

bool isEmpty(); // 스택이 비었는지 확인하는 함수

bool Peek(int *val); // 스택의 탑 위치를 확인하는 함수

int main(void){

	int sel; // 메뉴 입력

	int num; // 스택에 값 입력 또는 출력할 때 쓰는 int

	while (1) {
		
		cout << "--------스택--------"<< endl;
		cout << "1.Push "<< endl;
		cout << "2.Pop " << endl;
		cout << "3.Peek " << endl;
		cout << "4. 나가기"<< endl;
		cout << "번호 입력 : ";
		cin >> sel;

		cout << endl;
		switch (sel) {
		case 1:
			cout << "값을 입력하세요 : ";
			cin >> num;
			if (Push(num) == false)
				cout << "스택이 꽉 찼습니다." << endl;
			break;
		case 2:
			if (Pop(&num) == true) 
				cout << "Pop() 결과 : " << num << endl;
			else
				cout << "스택이 비어있습니다. " << endl;
			break;
		case 3:
			if(Peek(&num) == true)
				cout<<"Peek() 결과 : "<< num <<endl;
			else
				cout << "스택이 비어있습니다. " << endl;
			break;
		};

		cout << endl;
		if (sel == 4) {// 4번 입력 시 종료
			cout << "프로그램을 종료합니다." << endl;
			break;
		}
	}

}

bool Push(int val){

	if (isFull() == true) // 스택이 꽉 찼으면 true를 return
		return false;
	else {
		stack[++top] = val;
		return true;
	}

}

bool Pop(int *val) {
	if (isEmpty() == true) // 스택이 비었으면 true를 return
		return false;
	else {
		*val = stack[top--];
		return true;
	}
}

bool isFull() {
	if (top == MAX_STACK - 1) // top은 인덱스이기 때문에 MAX_STACK의 -1 값과 같으면 true를 return
		return true;
	else
		return false;
}

bool isEmpty() {
	if (top == -1) // top이 -1이면 return
		return true;
	else
		return false;
}

bool Peek(int *val) {

	if (isEmpty() == true) {
		return false;
	}
	else {
		*val = stack[top];
		return true;
	}
}

 

 

- 스택(Stack)의 사용처

스택의 특징과 스택 구현방법에 관하여 간단하게 알아보았습니다. 이번에는 스택이 과연 어디에서 쓰이는지 간단하게 알아보도록 하겠습니다.

 

• C/C++의 main() 함수안에서 사용되는 지역변수와 함수들은 모두 스택의 자료구조에 의하여 관리됩니다.
• 스택을 활용하면 "재귀함수"를 필요로하는 소스코드에 "재귀함수"를 사용하지 않고 구현할 수 있습니다.
• 웹 브라우저의  방문기록에서도 스택의 특징을 활용하여 "뒤로가기"를 구현할 수 있습니다.
• 프로그램의 실행취소((Undo)에서 활용됩니다.
• 후위표기 계산식에서 활용됩니다.

 

---

이렇게 간단하게 스택(Stack)이라는 자료구조에 관하여 포스팅을 하였습니다.

 

IT디자이너였습니다. 

 

감사합니다.