스택
문제
정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 다섯 가지이다.
push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
풀이과정
스택은 배열을 사용하는 순차 자료구조나 포인터를 사용하는 연결 자료구조 방식을 이용해 구현할 수 있다.
배열 을 통해 스택을 구현할 경우 배열 크기를 미리 할당해놓기 때문에 스택의 크기 변경이 어려우므로 메모리 사용의 효율성이 떨어진다.
연결 리스트 를 통해 스택을 구현할 경우 스택의 크기 변경이 자유롭다는 장점이 있으므로 이 포스트에서는 스택을 연결 리스트 를 통해 구현하였다.
| 클래스 | 설명 |
|---|---|
StackElement |
스택의 자료를 가지며 다음 원소의 주소를 가진다. |
MyStack |
push, pop 등 LIFO 구조가 적용된 스택이다. |
Console |
사용자의 입·출력을 담당한다. |
코드
#include <iostream>
using namespace std;
class StackElement {
public:
int data;
StackElement* next;
StackElement() {
data = 0;
next = NULL;
}
};
class MyStack {
StackElement* mtop;
public:
MyStack() { mtop = NULL; }
void push(int x);
int pop();
int size();
bool empty();
int top();
};
void MyStack::push(int x) {
if (empty()) {
StackElement* temp = new StackElement();
temp->data = x;
temp->next = NULL;
mtop = temp;
}
else {
StackElement* temp = new StackElement();
temp->data = x;
temp->next = mtop;
mtop = temp;
}
}
int MyStack::pop() {
if (empty()) {
return -1;
}
StackElement* temp = mtop;
int ret = temp->data;
mtop = mtop->next;
delete temp;
return ret;
}
int MyStack::size() {
int cnt = 0;
StackElement* temp = mtop;
while (temp) {
cnt++;
temp = temp->next;
}
return cnt;
}
bool MyStack::empty() {
if (mtop == NULL) {
return true;
}
return false;
}
int MyStack::top() {
if (empty()) {
return -1;
}
return mtop->data;
}
class Console {
MyStack stack;
string cmd;
int x;
public:
void run() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> cmd;
if (cmd.compare("push") == 0) {
cin >> x;
stack.push(x);
}
else if (cmd.compare("pop") == 0) {
cout << stack.pop() << endl;
}
else if (cmd.compare("size") == 0) {
cout << stack.size() << endl;
}
else if (cmd.compare("empty") == 0) {
if (stack.empty()) cout << 1 << endl;
else cout << 0 << endl;
}
else if (cmd.compare("top") == 0) {
cout << stack.top() << endl;
}
else {
cout << "command is not valid" << endl;
}
}
}
};
int main() {
Console console;
console.run();
return 0;
}
결과
