스택(stack)
1 스택이란?
-스택이란 데이터를 일시적으로 저장하기 위해 사용하는 자료구조이다.
-한 쪽 끝에서만 자료를 넣고, 뺼 수 있다.
-가장 마지막에 넣은 자료가 가장 먼저 빠진다.(FILO(First In Last Out)/LIFO(Last In First Out))
-데이터를 넣는 작입을 push, 빼는 작업을 pop이라 한다.
-쉽게 생각했을 때 한쪽이 막힌 원통이라고 생각할 수 있다.
2 스택의 연산
스택은 LIFO(Last In First Out) 형태를 따르기 때문에 가장 최근에 추가한 데이터가 가장 먼저 제거된다.
-push(item): item 하나를 스택의 가장 윗부분에 넣는다.
-pop(): 스택에서 가장 위에 있는 데이터를 제거한다.
출처 https://monsieursongsong.tistory.com/4
-top(): 가장 마지막에 들어온(스택에서 가장 위에 있는) 데이터를 확인한다.
-size(): 스택에 몇개의 자료가 들어가 있는지 확인한다.
-empty(): 스택이 비어있는지, 아닌지 확인하다.(이 때 비어있으면 1을 반환, 비어있지 않으면 0을 반환)
3 스택의 구현
스택을 기본적으로 구현하는데는 여러가지 방법이 존재한다.
그 중 가장 기본적인 구현 방법은 배열(array)을 이용하여 구현하는 방법이다.
위에 첨부된 사진을 보면 알겠지만 스택을 기울이면 배열과 비슷한 형태가 된다. 이를 이용하여 배열을 스택으로 만들 것이다.
구현할 때 필요한 것: 배열(+최대크기), top변수(밑에 코드에서는 top함수가 있으므로 idx라는 이름의 변수로 사용), 각종 함수
아래 코드는 배열을 이용하여 스택을 구현한 이다.
#include <stdio.h>
#include <string.h>
int idx = 0; //앞에서 말한 top변수
int stack[10002]; //배열의 크기는 스택의 최대 용량만큼 잡아줘야한다.
void push(int n) {
stack[idx++] = n;
return;
}
void pop() {
if (idx != 0)
printf("%d\n", stack[--idx]);
else
printf("-1\n");
return;
}
void top() {
if (idx != 0)
printf("%d\n", stack[idx - 1]);
else
printf("-1\n");
}
void empty() {
if (idx == 0)
printf("1\n");
else
printf("0\n");
}
int main() {
int N, data;
char order[8];
scanf("%d", &N);
while (N--) {
scanf("%s", order);
if (strcmp(order, "push") == 0) {
scanf("%d", &data);
push(data);
}
else if (strcmp(order, "pop") == 0) {
pop();
}
else if (strcmp(order, "size") == 0)
printf("%d\n", idx);
else if (strcmp(order, "top") == 0)
top();
else if (strcmp(order, "empty") == 0)
empty();
}
}
p.s. pop()함수에서 data를 뺄 때 굳이 배열에서 data를 제거할 필요가 없다. 그냥 idx만 줄여주면 인식을 하지 않는다.
4 스택 활용(c++/stl사용)
c++에서는 stack을 일일히 구현하지 않아도 된다. stdio처럼 이미 라이브러리로 구현되어있기 때문이다.
헤더파일은 #include <stack>코드를 추가하면된다.
이 때 c++헤더를 사용하기 위해서는 한 줄을 더 추가해주어야 하는데 이는 밑에 전체 코드에서 설명하도록 하겠다.
또한 stack을 만드려면 int형 변수, char형 변수를 선언하는 것처럼 stack이라는 변수를 하나 선언해주어야한다.
방법은 간단하다. stack<원하는 자료형> 원하는 변수이름;위와 같은 형태로 사용하면 되는데
하나의 예시를 들자면 stack안에 int형 자료만 들어갈 경우, stack변수 이름을 s로 지정하고 싶을 때 stack<int> s;이런 방식으로 사용하면 된다.
마지막으로 stack헤더에 있는 push, pop등의 함수를 사용하려면 “stack변수이름.원하는 함수”의 형태로 사용하면 된다.
아래 코드는 c++에 미리 구현되어있는 stack라이브러리(stl) 사용해 스택을 구현한 것이다.
#include<stdio.h>
#include<string.h>
#include<stack>
using namespace std; //이 부분이 c++헤더를 사용할 때 꼭 추가해주어야하는 줄이다
stack<int> s;
int main() {
int N, data;
char order[8];
scanf("%d", &N);
while (N--) {
scanf("%s", order);
if (strcmp(order, "push") == 0) {
scanf("%d", &data);
s.push(data);
}
else if (strcmp(order, "pop") == 0) {
if(s.empty())
printf("-1\n");
else{
printf("%d\n", s.top());
s.pop();
}
}
else if (strcmp(order, "size") == 0)
printf("%d\n", s.size());
else if (strcmp(order, "top") == 0){
if(s.empty())
printf("-1\n");
else{
printf("%d\n", s.top());
}
}
else if (strcmp(order, "empty") == 0)
printf("%d\n", s.empty());
}
return 0;
}