티스토리 뷰
1. 스택
- 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조.
- 마지막으로 넣은 것이 가장 먼저 나오기 때문에 Last In First Out(LIFO) 라고도 한다.
- push : 스택에 자료를 넣는 연산
- pop : 스택에서 자료를 빼는 연산
- top : 스택의 가장 위에 있는 자료를 보는 연산
- empty : 스택이 비어있는지 아닌지를 알아보는 연산
- size : 스택에 저장되어있는 자료의 개수를 알아보는 연산
- 스택은 C++의 경우에는 STL의 stack 이용
- 스택을 구현할 경우 배열 이용
2. 소스
①C++(STL)
- stack<int> Stack;
#include <cstdio>
#include <stack>
#include <string>
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
stack<int> Stack;
string s;
int push_su;
while(n--)
{
cin >> s;
if(s == "push")
{
cin >> push_su;
Stack.push(push_su);
}
else if(s == "pop")
{
if(!Stack.empty())
{
cout << Stack.top() << endl;
Stack.pop();
}
else{
cout << "-1" << endl;
}
}
else if(s == "size")
{
cout << Stack.size() << endl;
}
else if(s == "empty")
{
if(!Stack.empty())
{
cout << "0" << endl;
}
else
{
cout << "1" << endl;
}
}
else if(s == "top")
{
if(!Stack.empty())
{
cout << Stack.top() << endl;
}
else
{
cout << "-1" << endl;
}
}
}
return 0;
}
②C++(구현)
#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
struct Stack{
int data[10010];
int len;
Stack()
{
len = 0;
}
void push(int su)
{
data[len] = su;
len += 1;
}
void pop()
{
data[len-1] = 0;
len -= 1;
}
int top()
{
return data[len-1];
}
int size()
{
return len;
}
int empty()
{
if(len <= 0) return 1;
else return 0;
}
};
int main()
{
int n, push_su;
string cmd;
struct Stack s;
scanf("%d", &n);
while(n--)
{
cin >> cmd;
if(cmd == "push")
{
cin >> push_su;
s.push(push_su);
}
else if(cmd == "pop")
{
if(s.empty() != 1)
{
cout << s.top() << endl;
s.pop();
}
else cout << -1 << endl;
}
else if(cmd == "size")
{
cout << s.size() << endl;
}
else if(cmd == "empty")
{
cout << s.empty() << endl;
}
else if(cmd == "top")
{
if(s.empty() != 1)
{
cout << s.top() << endl;
}
else cout << -1 << endl;
}
}
return 0;
}
③C(구현)
-strcmp(문자열1, 문자열2) : 문자열 비교 결과 반환 (string.h 헤더파일 선언)
-1 : ASCII 코드 기준으로 문자열2가 클 때
0 : ASCII 코드 기준으로 두 문자열이 같을 때
1 : ASCII 코드 기준으로 문자열1이 클 때
#include <stdio.h>
#include <string.h>
struct Stack{
int data[100];
int len;
Stack()
{
len = 0;
}
void push(int su)
{
data[len] = su;
len += 1;
}
void pop()
{
data[len] = 0;
len -= 1;
}
int size()
{
return len;
}
int top()
{
return data[len-1];
}
int empty()
{
if(len <= 0) return 1;
else return 0;
}
};
int main()
{
int n;
scanf("%d", &n);
struct Stack stack;
char s[10];
int push_su;
while(n--)
{
scanf("%s", s);
if(strcmp(s,"push") == 0)
{
scanf("%d", &push_su);
stack.push(push_su);
}
else if(strcmp(s,"pop") == 0)
{
if(!stack.empty())
{
printf("%d\n", stack.top());
stack.pop();
}
else{
printf("%d\n", -1);
}
}
else if(strcmp(s,"size") ==0)
{
printf("%d\n", stack.size());
}
else if(strcmp(s,"empty") == 0)
{
if(!stack.empty())
{
printf("%d\n", 0);
}
else
{
printf("%d\n", 1);
}
}
else if(strcmp(s,"top") == 0)
{
if(!stack.empty())
{
printf("%d\n", stack.top());
}
else
{
printf("%d\n", -1);
}
}
}
return 0;
}
④C(구현)
//스택 구현하기(Stack)
#include <stdio.h>
// 0 1 2 3 4 5 6 7
//data 7 8 9 1 2 3
struct Stack{
int data[100];
int len = 0;
int capacity = 0;
void create(int y){
capacity = y;
}
void push(int y){
//capacity = 4
// 0 1 2 3 4 5
//d 1 8 3 2
if(len >= capacity){
printf("Stack overflow!\n");
}
else
{
data[len++] = y;
}
}
void pop(){
//capacity = 5
// 0 1 2 3 4 5
//d 8 3 5 2
if(len <= 0)
{
printf("Stack underflow!\n");
}
else
{
data[len-1] = 0;
len--;
}
}
int top(){
// 스택의 가장 위에 있는 원소를 반환.
// 단, 스택에 아무것도 없다면 -1을 반환.
if(len <= 0)
{
return -1;
}
else
{
return data[len-1];
}
}
int size(){
//스택 안에 들어있는 원소의 개수를 반환.
return len;
}
};
int main()
{
Stack s1;
s1.create(5);
s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4);
s1.push(5);
s1.push(6); //overflow
s1.push(7); //overflow
printf("%d\n", s1.top());
s1.pop();
printf("%d\n", s1.top());
s1.push(6);
s1.push(7); //overflow
printf("%d\n", s1.top());
s1.pop();
s1.pop();
s1.pop();
s1.pop();
s1.pop();
s1.pop();//underflow!
printf("%d\n", s1.size());
return 0;
}