백준 10828 스택 C++

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

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

입력

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

출력

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

예제 입력 1

14
push 1
push 2
top
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
top

예제 출력 1

2
2
0
2
1
-1
0
1
-1
0
3

예제 입력 2

7
pop
top
push 123
top
pop
top
pop

예제 출력 2

-1
-1
123
123
-1
-1

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: djm03178

알고리즘 분류

• 자료 구조
• 스택

 

풀이

스택의 정의

후입선출(Last In First Out—LIFO) 특성을 가지는 자료구조이다.

메모리에 새로 들어오는 데이터의 위치가 메모리 말단(일명 '탑 포인터(Top Pointer)')이고, 써먹기 위해 내보내는 데이터 역시 메모리 말단을 거친다.

스택의 입력연산은 푸시(Push), 출력연산은 팝(Pop)이라고 부른다. 

 

스택의 구현

스택은 후입선출(Last In First Out) 개념이다. 선입선출(First in First Out)인 큐와 비교된다.

배열이나 연결리스트로 구현할 수 있다. 

이 문제에서는 배열로 구현했다.

 

배열을 이용해서 구현할 때를 예로 들어보자.

처음으로 스택을 위한 배열을 하나 잡아 놓고, index 값을 0으로 잡는다. 

index가 0이면 스택이 비어 있는 것(empty)이다.

스택에 뭔가를 집어넣을 때(push)는 index의 자리에 집어넣고 index를 하나 올리면 된다.

index가 초기 배열 크기 이상이면 스택이 꽉 찬 것이다.

스택에서 뭔가를 뺄 때(pop)는 index에 있던 값을 돌려주고 index를 하나 뺀다.

#include <iostream>
#include <string>
using namespace std;

class stack {
	int top;

public:
	int arr[10001];
	stack(){
		top = -1;
	}

	void push(int n) {

		if (top < 10000) {
			arr[++top] = n;
		}
		
	}

	int pop() {
		if (top == -1)
			return -1;
		else
			return arr[top--];
	}

	int size() {
		return (top + 1);
	}

	int empty() {
		if (top == -1) 
			return 1;
		else 
			return 0;
	}

	int Top() {
		if (top == -1)
			return -1;
		else
			return arr[top];
	}
};
int main() {
	int n;
	string str;
	stack s;
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		cin >> str;
		
		if (str == "push") {
			int m;
			cin >> m;
			s.push(m);
		}
		else if (str == "pop") {
			cout << s.pop() << endl;
		}
		else if (str == "size") {
			cout << s.size() << endl;
		}
		else if (str == "empty") {
			cout << s.empty() << endl;
		}
		else if (str == "top") {
			cout << s.Top() << endl;
		}
		
	}
	return 0;
}