스택이란?
✅ 스택이란
- 삽입과 삭제가 한쪽 끝, top에서만 이루어지는 유한 순서 리스트
- 후입선출(LIFO) : 가장 최근에 들어온 data가 먼저 나간다.
- 모든 연산에 대한 시간 복잡도는 O(1)
스택의 모든 시간 복잡도가 O(1)인 이유는?
- 삽입을 하거나 삭제를 할 때는 맨 위에 있는 top의 data를 삽입하거나 삭제하기 때문에 시간복잡도는 늘 O(1)이다.
✅ 스택의 구조
- 스택 상단 : top
- 스택 하단 : 불필요
- 삽입(push) / 삭제(pop)
스택을 적용한 문제풀이
✅백준 10828. 스택
https://www.acmicpc.net/problem/10828
문제
정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 다섯 가지이다.
- push X: 정수 X를 스택에 넣는 연산이다.
- pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 스택에 들어있는 정수의 개수를 출력한다.
- empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
- top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
소스코드 ("더보기"누르면 소스코드 보임)
① 직접 구현
- 조건에서 첫째 줄에 주어지는 명령의 수가 1 ≦ N ≦ 10,000 이기 때문에 Stack 배열의 최대 사이즈를 10,000으로 했다. 예를 들어, 10개의 명령을 받는다면 최대로 10개를 push 할 수 있기 때문. (10개 이하일 수도 있음. 명령이 pop인 경우는 공간이 필요하지 않기 때문)
- 명령은 문제의 조건에 맞게 설정하였다. 문제의 조건만 맞추면 그렇게 어렵지는 않았다.
- 클래스로 코드를 작성하였기 때문에 객체를 꼭 생성해야 함을 주의
- push 와 pop을 할 때, 전위/후위 증감은 중요!
push의 경우, push는 top을 하나 증가시키고 바로 data를 넣어야 하기 때문에 전위증가
pop의 경우, 삭제할 data를 반환하고 삭제해야 하기 때문에 후위감소를 해야 한다.
#include <iostream>
#include <string>
using namespace std;
const int MAX_STACK = 10000; //조건
class Arraystack {
private:
int top;
int data[MAX_STACK];
public:
//생성자
Arraystack() {
top = -1;
}
bool isEmpty() {
return top == -1;
}
void Empty() {
if (isEmpty())
cout << 1 << endl;
else
cout << 0 << endl;
}
void push(int x) {
data[++top] = x;
}
void pop() {
if (isEmpty()) {
cout << top << endl;
}
else
cout << data[top--] << endl;
}
void getTop() {
if (isEmpty()) {
cout << -1 << endl;
}
else
cout << data[top] << endl;
}
void size() {
cout << (top + 1) << endl;
}
};
int main() {
//정수 입력받기
int x;
cin >> x;
Arraystack a;
for (int i = 0; i < x; i++) {
string x;
cin >> x;
if (x == "push") {
int num;
cin >> num;
a.push(num);
}
if (x == "pop") {
a.pop();
}
if (x == "top") {
a.getTop();
}
if (x == "size") {
a.size();
}
if (x == "empty") {
a.Empty();
}
}
return 0;
}
② STL의 stack 이용
- 스택 헤더 파일 작성하기
헤더파일 작성 후, stack<data type> 이름; 으로 stack을 선언한다.
#include <stack>
stack<int> stack;- 코드가 ①번 보다 훨씬 더 간결해졌다. 코드의 길이가 짧아져서 메모리나 코드를 실행하는데 걸리는 시간이 짧게 걸릴 줄 알았는데 그건 아니였다.
- STL을 이용하였기 때문에 클래스 없이 사용할 수 있다.
#include <iostream>
#include <stack>
#include <string>
using namespace std;
stack<int>S;
int main() {
//명령어 개수 입력받기
int x;
cin >> x;
//명령
for (int i = 0; i < x; i++) {
string ins;
cin >> ins;
if (ins == "push") {
//push의 data 삽입
int x;
cin >> x;
S.push(x);
}
if (ins == "pop") {
if (S.empty())
cout << -1 << endl;
else {
cout << S.top() << endl;
S.pop();
}
}
if (ins == "size") {
cout << S.size() << endl;
}
if (ins == "empty") {
if (S.empty())
cout << 1 << endl;
else
cout << 0 << endl;
}
if (ins == "top") {
if (S.empty())
cout << -1 << endl;
else
cout << S.top() << endl;
}
}
return 0;
}
✅백준 10773. 제로
https://www.acmicpc.net/problem/10773
문제
나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.
재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.
재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.
재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!
입력
첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)
이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.
정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.
출력
재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다.
소스코드
#include <iostream>
using namespace std;
const int STACK_MAX = 100000;
class ArrayStack {
private:
int top;
int data[STACK_MAX];
public:
ArrayStack() {
top = -1;
}
bool empty() {
return top == -1;
}
void pop() {
top = top - 1;
}
void push(int x) {
top = top + 1;
data[top] = x;
}
int getData() {
return data[top];
}
};
int main() {
//정수 K 입력받기
int num;
cin >> num;
ArrayStack a; //객체 생성
//숫자입력
for (int i = 0; i < num; i++) {
int x;
cin >> x;
if (x == 0)
a.pop();
else
a.push(x);
}
//전체 합
int sum = 0;
while (!a.empty()) {
sum += a.getData();
a.pop();
}
cout << sum;
return 0;
}- 입력받는 정수가 0일 때만 pop을 하는 것이므로 pop만 고려하면 된다.
- getData() 함수를 작성해서 top에 있는 data를 return 하도록 함.
'Data Structure' 카테고리의 다른 글
| [Data Structure] 큐(Queue) (0) | 2022.07.10 |
|---|
