지난 시간에는 C++에서 제공하는 기능인 STL을 알아보았습니다.
이번 시간에는 후입선출형태의 자료구조인 스택을 알아보겠습니다.
1) 정의
마지막에 들어간 데이터가 가장 먼저 나오는 형태의 자료구조입니다.
LIFO(Last In First Out)라고도 부릅니다.
처음부터 정의만 살펴보면 이해가 힘들 수 있습니다.
문제 하나를 풀어보면서, 스택을 알아보겠습니다.
10828번 문제
다음 5가지 쿼리를 수행하는 문제입니다.
push X: 정수 X를 스택에 넣는다.
pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 스택이 비어있다면 -1를 출력한다.
size: 스택에 있는 정수의 개수를 출력한다.
empty: 스택이 비어있는지 확인한다.
top: 스택에서 가장 위에 있는 정수를 출력한다. 스택이 비어있다면 -1를 출력한다.
문제에서 요구하는 쿼리이자, 스택의 기본적인 연산입니다.
(0) 스택의 요소
스택을 사용하기 위해서는, 보통은 다음 두 가지 변수를 선언합니다.
- stack[]: 데이터를 저장할 곳입니다.
- top: 스택의 맨 위를 가리키는 변수입니다. 초기값은 -1입니다.
만약 스택에 하나의 데이터가 들어온다면, top은 0이 됩니다.
0은 스택의 맨 위 데이터가 저장되어있는 인덱스이기 때문입니다.
top이 -1인 경우, 스택은 비어있다는 뜻입니다.
문제에서 요구하는 함수인 top과 이름이 같기에,
이번에 한해 스택의 변수인 top을 t로 표기하겠습니다.
(1) push
다음과 같이 구현할 수 있습니다.
// 스택의 맨 위를 가리키는 변수를 올린 후, 값 저장
void push(int x) {
stack[++t] = x;
}증감 연산자로 먼저 t를 1 증가한 후,
그 인덱스의 배열에 x를 할당했습니다.
원래는 스택이 지정된 크기를 벗어났을 때 예외 처리를 해야 하지만,
이 문제에서는 그것을 신경 쓰지 않아도 되기에 생략했습니다.
(2) pop
다음과 같이 구현할 수 있습니다.
int pop() {
// 스택이 비어있는 경우
if (t == -1)
return -1;
// 반환 후 스택 사이즈 줄이기
return stack[t--];
}t가 -1이라면, 스택이 비어있는 경우이기에 -1를 반환합니다.
그것이 아니라면, 스택의 맨 위를 반환한 후,
t를 1 감소시킴으로써 데이터를 없앱니다.
(3) size
다음과 같이 구현할 수 있습니다.
int size() {
// size = t + 1
return t + 1;
}배열의 인덱스는 0 부터 시작하기에, +1로 크기를 맞춰줍니다.
(4) empty
다음과 같이 구현할 수 있습니다.
int empty() {
// t = -1이면, 비어있는 스택
return t == -1 ? 1 : 0;
}비어있으면 1, 아니면 0을 반환하면 됩니다.
(5) top
다음과 같이 구현할 수 있습니다.
int top() {
// 스택이 비어있는 경우
if (t == -1)
return -1;
// 스택을 줄이지 않고 반환
return stack[t];
}문자 두 개를 제외하면
pop과 완전히 같습니다.
(6) 정답 코드
여러분은 스택의 기본적인 연산을 모두 이해하였습니다.
다음은 이 문제의 올바른 코드입니다.
// made by biggrace681
#include <iostream>
using namespace std;
int stack[10000]{}, t = -1;
// 스택의 맨 위를 가리키는 변수를 올린 후, 값 저장
void push(int x) {
stack[++t] = x;
}
int pop() {
// 스택이 비어있는 경우
if (t == -1)
return -1;
// 반환 후 스택 줄이기
return stack[t--];
}
int size() {
// size = t + 1
return t + 1;
}
int empty() {
// t = -1이면, 비어있는 스택
return t == -1 ? 1 : 0;
}
int top() {
// 스택이 비어있는 경우
if (t == -1)
return -1;
// 스택을 줄이지 않고 반환
return stack[t];
}
int main() {
int n; cin >> n;
while (n--) {
string query; cin >> query;
if (query == "push") {
int x;cin >> x;
push(x);
}
if (query == "pop")
cout << pop() << '\n';
if (query == "size")
cout << size() << '\n';
if (query == "empty")
cout << empty() << '\n';
if (query == "top")
cout << top() << '\n';
}
}축하드립니다! 여러분은 스택을 사용할 수 있게 되었습니다.
과제
클릭 시, 백준의 그룹으로 이동합니다.
모든 과제의 제출기한은 과제 게시 후 2주입니다.
모든 과제의 제출기한은 과제 게시 후 2주입니다.
중요하니까 두 번 적었습니다.
제출기한을 모르고있다가
과제를 까먹고 제출하지 않는 일이 없기 바랍니다......
이번 시간에는 LIFO(Last In First Out)형태의 스택을 알아보았습니다.
다음 시간에는 FIFO(First In First Out)형태의 큐를 알아보겠습니다.
