[Algorithm] 스택 (Stack)

[Algorithm] 스택 (Stack)

 

 

스택(Stack)

 

-정의: 한쪽 끝에서만 원소를 넣거나 뺄수 있는 자료 구조(FIFO-First In Last Out).

 

스택(Stack)

 

 

-연산

1) push(item) : 스택의 가장 위에 원소(item)를 추가

2) pop() : 스택의 가장 위에 있는 원소를 제거

3) isempty() : 스택이 비었으면 참(true)을 반환. 아니면 거짓(false).

4) top() : 스택의 가장 위에 있는 원소를 반환

 

 

-특징

1) FIFO-First In Last Out : 가장 최근에 push된 원소가 가장 먼저 pop된다.

2) 활용 : 수식의 괄호 쌍, 전위/중위/후위/표기법, DFS, Flood Fill, 문자열 뒤집기, 재귀 알고리즘, 웹 브라우저 방문기록, 실행 취소 등

3) Restricted Structure : 특정 위치에서만 원소를 넣고 뺄수 있는 자료구조

 

 

-시간복잡도

1) 원소 추가: O(1)

2) 원소 제거: O(1)

3) 원소 확인: O(1)

 

 

-C++로 스택(Stack) 구현

 

1) STL stack 사용

 

2) 배열로 구현 ( 백준 10828번 스택 )

 

• push X: 정수 X를 스택에 넣는 연산이다.
• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 스택에 들어있는 정수의 개수를 출력한다.
• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

 

입력: 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력: 출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

 

 

내 코드

 

#include <iostream> 
#include <string>

using namespace std;

int stack[100000];
int pointer = 0;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	//배열로 스택 구현
	int n = 0;
	cin >> n;

	while (n--) {
		string input;
		cin >> input;

		if (input == "push") {
			int tmp = 0;
			cin >> tmp;
			stack[pointer++] = tmp;
		}
		else if (input == "pop") {
			if (pointer != 0) {
				cout << stack[--pointer] << endl;
			}
			else cout << -1 << endl;
		}
		else if (input == "size") {
			cout << pointer << endl;
		}
		else if (input == "empty") {
			if (pointer != 0) cout << 0 << endl;
			else cout << 1 << endl;
		}
		else if (input == "top") {
			if(pointer != 0)
				cout << stack[pointer - 1] << endl;
			else cout << -1 << endl;
		}
	}

	return 0;
}

 

 

3) Linked List로 구현

 

 

 

 

 

 

 

 

 

참고

 

https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html

https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

https://blog.encrypted.gg/727?category=773649