문제
정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 다섯 가지이다.
push X: 정수 X를 스택에 넣는 연산이다.pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.size: 스택에 들어있는 정수의 개수를 출력한다.empty: 스택이 비어있으면 1, 아니면 0을 출력한다.top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
풀이
stack 은 총 3가지 방법으로 풀 수 있습니다.
첫번째, STL 사용
두번째, 배열 사용
세번째, 연결 리스트 사용
자세한 내용은 👉 [알고리즘] Stack과 Queue 여기 포스팅을 참고해주세요.
소스코드
첫번째, STL 사용
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
stack<int> s;
int n; // 명령의 수
cin >> n;
string command; // 명령어
int x; // 스택에 넣을 수
for(int i=0;i<n;i++) {
cin >> command;
if (command == "push") {
// 정수 X 를 스택에 넣음
cin >> x;
s.push(x);
} else if (command == "size") {
// 스택에 들어있는 정수의 개수를 출력
cout << s.size() << endl;
} else if (command == "empty") {
// 스택이 비어있는지 확인
cout << s.empty() << endl;
} else if (s.empty()) {
// pop, top 인 경우 스택이 비어 있으면 -1 을 출력해야 함
cout << "-1" << endl;
} else if (command == "pop") {
// top 에 있는 값을 출력해주고 pop 해줌
cout << s.top() << endl;
s.pop();
} else if (command == "top") {
// top 에 있는 값 출력
cout << s.top() << endl;
}
}
return 0;
}두번째, 배열 사용
#include <iostream>
#include <string>
using namespace std;
struct stack {
int top = 0;
int a[10000];
void push(int x) {
a[top++] = x;
}
int size() {
return top;
}
int empty() {
return top == 0;
}
int t() {
return a[top-1];
}
int pop() {
return a[top--];
}
};
int main() {
stack s;
int n; // 명령의 수
cin >> n;
string command; // 명령어
int x; // 스택에 넣을 수
for(int i=0;i<n;i++) {
cin >> command;
if (command == "push") {
// 정수 X 를 스택에 넣음
cin >> x;
s.push(x);
} else if (command == "size") {
// 스택에 들어있는 정수의 개수를 출력
cout << s.size() << endl;
} else if (command == "empty") {
// 스택이 비어있는지 확인
cout << s.empty() << endl;
} else if (s.empty()) {
// pop, top 인 경우 스택이 비어 있으면 -1 을 출력해야 함
cout << "-1" << endl;
} else if (command == "pop") {
// top 에 있는 값을 출력해주고 pop 해줌
cout << s.t() << endl;
s.pop();
} else if (command == "top") {
// top 에 있는 값 출력
cout << s.t() << endl;
}
}
return 0;
}세번째, 연결 리스트 사용
#include <iostream>
#include <string>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* top;
int count;
void push(int x) {
Node* n = new Node();
n -> data = x;
n -> next = top;
top = n;
count ++;
}
int size() {
return count;
}
int empty() {
return top == NULL;
}
int t() {
return top -> data;
}
void pop() {
count--;
top = top -> next;
}
int main() {
int n; // 명령의 수
cin >> n;
string command; // 명령어
int x; // 스택에 넣을 수
for(int i=0;i<n;i++) {
cin >> command;
if (command == "push") {
// 정수 X 를 스택에 넣음
cin >> x;
push(x);
} else if (command == "size") {
// 스택에 들어있는 정수의 개수를 출력
cout << size() << endl;
} else if (command == "empty") {
// 스택이 비어있는지 확인
cout << empty() << endl;
} else if (empty()) {
// pop, top 인 경우 스택이 비어 있으면 -1 을 출력해야 함
cout << "-1" << endl;
} else if (command == "pop") {
// top 에 있는 값을 출력해주고 pop 해줌
cout << t() << endl;
pop();
} else if (command == "top") {
// top 에 있는 값 출력
cout << t() << endl;
}
}
return 0;
}정답
