알고리즘 : 자료구조(1) 스택 (Stack) (C++로 구현)

스택 (Stack)

스택(stack)은 쌓아놓은 더미라는 의미 그대로, 책상에 쌓여있는 책을 생각하면 된다.

가장 큰 특징은 LIFO(Last In First Out-후입선출)이다. 제일 최근에 들어온 데이터가 가장 먼저 나가는 것이다. 편의점 아르바이트를 해보신 분들이 아는 선입선출과 반대되는 용어이다. 여기서 선입선출에 해당되는 자료구조는, 뒤에서 다룰 큐 (Queue)이다.

문서 편집기에서 되돌리기를 했을 때 바로 직전에 실행한 작업이 취소되는 것을 생각하면 된다.

 

push : 스택의 top에서 데이터 삽입
pop : 스택의 top에서 데이터 삭제
stack top : 스택에서 입출력이 이루어지는 부분
element : 스택에 저장되는 것
full stack : 포화 상태의 스택

스택의 기본 용어는 이렇게 된다.

 

class Stack {
private:
	int stack_size = 100;
	int top = -1;
	int* stack;
public:
	Stack();
	~Stack();
	void push(int element);
	void pop();
	void show_stack();
};

Stack::Stack() {
	stack = new int[stack_size];
}

Stack::~Stack() {
	delete[] stack;
}

c++을 이용해서 차근차근 구현해보도록 하겠다. 나는 stack의 크기를 100으로 설정해주었으나 입력받는 것으로 설정해도 괜찮다.

 

1. Push & Pop

void push(int x) {
	if (top >= n - 1) // 스택이 꽉 찼음
		cout << "Stack Over flow!\n";
	else
		stack[++top] = x;
}

void pop() {
	if (top <= -1) // pop할 요소가 없음
		cout << "Stack Underflow!\n";
	else
		cout << "The popped element is " << stack[top--] << "\n";
}

 

2. Show Stack

void Stack::show_stack() {
	if (top >= 0) {
		cout << "Stack elements :";
		for (int i = top; i >= 0; i--)
		{
			cout << stack[i] << " ";
		}
		cout << "\n";
	}
	else {
		cout << "Stack is empty\n";
	}
}

모든 요소를 보여주는 함수이다.

 

3. 최종 코드

int main() {
	Stack s;
	int ch=0, val;
	cout << "1) Push in stack\n";
	cout << "2) Pop from stack\n";
	cout << "3) Display stack\n";
	cout << "4) Exit\n";
	while (ch != 4) {
		cout << "Enter your choice: ";
		cin >> ch;
		switch (ch) {
		case 1: {
			cout << "Enter value to be pushed: ";
			cin >> val;
			s.push(val);
			break;
		}
		case 2: {
			s.pop();
			break;
		}
		case 3: {
			s.show_stack();
			break;
		}
		case 4: {
			cout << "Exit" << endl;
			break;
		}
		default: {
			cout << "Invalid Choice" << endl;
		}
		}
	}
	return 0;
}

간단하게 구현을 해보았다.

 

4. STL을 이용한  Stack 구현

#include <stack>
stack<int> stack;

c++ STL을 이용해서 Stack을 구현할 수도 있다.

 

stack.push(element); // 데이터 추가
stack.pop(); // 데이터 삭제
stack.top(); // 가장 위에 있는 데이터 반환
stack.size(); // 현재 사이즈 반환
stack.empty(); // 비어있는지 반환
swap(stack1 , stack2); // 스택1과 스택2의 내용 바꾸기

이와 같은 함수를 사용할 수 있다.

 

https://better-tomorrow.tistory.com/entry/c%EB%A1%9C-stack-%EA%B5%AC%ED%98%84STL-without-STL

stack 자료구조 설명 및 구현(c++)

참고한 티스토리이다!

 

활용

재귀 알고리즘

DFS 알고리즘