Stack(스택)

스택의 정의

스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다.

그 접근 방법은 언제나 목록의 끝(top)에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다. 

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)로 되어 있다. 자료를 넣는 것을 '밀어 넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸시한 자료부터 나오게 된다.

ex) 쌓아올린 접시, 웹 브라우저의 뒤로 가기 기능, 수식의 괄호 검사

스택의 기본적인 구동 원리를 설명하는 그림이다

(자료 출처 - 위키백과)

---

Stack Library(스택 라이브러리)

스택을 구현할 수 있는 방법에는 여러가지가 있다. 배열을 선언하여 직접 스택을 만드는 방법이 있고, 스택 라이브러리를 호출하여 이미 구현된 스택과 그 멤버 함수를 활용하는 방법이 있다. 

스택 라이브러리를 사용하고자 할 때에는 코드의 초반에 Header(헤더)파일을 선언해야 한다. 헤더 파일은 아래와 같이 선언한다.

#include <stack>

스택 헤더를 선언하고 스택 라이브러리를 쓰기 위해서는 해당 언어가 C++ 이어야 한다. C 언어는 스택 라이브러리가 포함된 STL(표준 템플릿 라이브러리)을 사용하는 것이 불가하므로, 반드시 C++을 사용하자.

스택 헤더를 선언하였다면, 해당 소스 파일에서는 스택 변수를 선언하고 사용할 수 있다. 스택을 포함한 STL 자료구조는 일반적인 변수 선언 방법과 조금 다르다. 스택을 선언할 때에는 아래의 코드처럼 선언한다.

stack <요소들의 자료형 (ex. int, char, double, struct, etc)> 변수명;

-----------------예 시--------------------

stack<int> st;
stack<int> st[100];
stack<char> st;
stack<(앞에서 typedef 된 구조체)str> st;

스택을 선언하였다면 이제 스택을 사용해보자! 스택에서 사용되는 멤버함수는 5가지로 설명할 수 있다.

명렁	코드
스택에 데이터를 삽입한다.	st.push(데이터)
스택에서 top 데이터를 삭제한다.	st.pop()
스택의 top 데이터를 읽어온다.	st.top()
스택의 사이즈(삽입된 데이터 개수)를 반환한다.	st.size()
스택이 비어있는지를 반환한다.	st.empty()   [비어있으면 = 1, 아니면 = 0]

---

스택 연습하기

스택을 사용하는 방법을 익혔으니 실제 코드에서 스택을 사용하는 코드를 작성해보자! 아래의 문제를 스택을 통하여 해결해보자!

문제

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

명령은 총 다섯 가지이다.

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

입력

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

입력 예시

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

출력 예시

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

 

(문제 출처 - 백준 온라인(10828번 스택))