[자료구조] 스택( Stack )

Goal

Stack의 기본개념을 이해한다.
Stack의 구조를 확인한다.
Stack을 C/C++ 로 구현한다.

스택(Stack)의 개념

• 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료구조이다.

스택(Stack)의 연산

• push(Data) : Data 하나를 스택에 삽입한다.
• pop : 스택에 있는 Data 하나를 제거한다.
• size : 스택에 들어있는 정수의 개수를 출력한다.
• empty : 스택이 비어있으면 1, 아니면 0을 출력한다.
• top : 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

스택(Stack)의 구현

스택은 연결리스트로 구현할 수 있으며 LIFO(Last In First Out) 를 따른다.

스택(Stack)의 생성자/초기화/함수들

// <stack> 헤더 추가
#include <stack>

// 비어있는 int형 stack 생성
stack<int> s1;

s1.push(n)	// n을 스택에 넣는 연산

s1.pop()	// 스택에서 제일 위에 있는 정수를 제거.
			// 스택에 정수가 없는 경우 -1을 출력
			
s1.empty()	// 스택이 비어있으면 1, 아니면 0 출력

s1.size()	// 스택에 들어있는 정수의 개수 출력

s1.top()	// 스택에 제일 위에 있는 정수 출력

스택(Stack) 코드 구현 [ C++ / STL ]

#include <iostream>
#include <stack>
#include <string>

using namespace std;
using std::cout;
using std::endl;

int main() { 
	int num;
	cin >> num;

	stack<int> st;
	string str;

	for (int i = 0; i < num; i++) {
		cin >> str;
		if (str == "push") {
			int num;
			cin >> num;
			st.push(num);
		}
		else if (str == "pop") {
			if (!st.empty()) {
				cout << st.top() << endl;
				st.pop();
			}
			else cout << "-1" << endl;
		}
		else if (str == "size") {
			cout << st.size() << endl;
		}
		else if (str == "empty") {
			if (st.empty()) cout << "1" << endl;
			else cout << "0" << endl;
		}
		else if (str == "top") {
			if (st.empty()) cout << "-1" << endl;
			else cout << st.top() << endl;
		}
	}
}