Stack

한 방향에서만 자료를 넣고 빼는 LIFO(last-in first-out, 후입선출) 형식의 자료구조로, 밑이 막힌 상자를 생각하면 쉽다. ( = 위에서만 넣고 뺄 수 있다!)

Stack 연산

앞서 stack을 LIFO 형식의 자료구조라고 설명했다. 따라서 stack의 주요 연산들도 한쪽 끝에서만 일어난다. (= 상자 위에서!)

주요 연산은 다음과 같은 것들이 있다.

push: stack에 item을 집어 넣음
pop: stack의 가장 위에 있는 item을 빼냄
top: stack의 가장 위에 있는 item을 가리킴(빼내지 않는다는 점에서 pop과 다름)
empty: stack이 비어있는지 알려줌 (비어 있으면 True)
size: stack의 크기를 알려줌

c++에서는 stack libray를 통해 stack을 쉽게 선언하고 사용할 수 있다. 하지만 이 글에서는 linked list를 이용하여 stack을 직접 구현 해볼 예정이다. 그래도 libary 사용법을 알고 있으면 매번 구현할 필요가 없으니, 아래 library 사용법을 참고해두면 좋을 것 같다.

#include <iostream>
#include <stack>
using namespace std;

int main(){
	stack<int> s; // s라는 이름을 가진 int형 stack 선언
    
    s.push(8); // 상자에 8을 집어 넣는 것이라고 생각! => 상자의 상태: (위) 8 (아래)
    s.push(22); // 상자의 상태: (위) 22 8 (아래)
    
    cout << s.top() << '\n'; // 22가 출력될 것임 (상자의 맨 위 item)
    cout << s.size() << '\n'; // 2가 출력될 것임. (8, 22 두 개의 item이 있으므로)
    
    if(s.empty()) cout << "stack is empty!\n"; //stack이 비어 있는지 확인 하는 연산 
    else cout << "stack size is " << s.size() << '\n'; // 비어 있지 않으므로 else문 실행

    s.pop(); // 22가 pop 됨 => 상자의 상태: (위) 8 (아래)
    cout << s.top() << '\n'; // 8이 출력
    s.pop(); // stack이 비어 있게 됨 
    
    if(s.empty()) cout << "stack is empty!\n"; // 이번에는 stack이 비어 있으므로 if문 실행
    else cout << "stack size is " << s.size() << '\n'; 
}

위 과정을 따라가다보면 stack을 모르던 사람도 금방 이해할 수 있으리라 생각한다. 위에서 주의할 점이 있는데, stack이 비어 있는 경우 pop연산을 하면 안된다! 즉, s.size()>0인 경우에만 pop연산을 허용하면 더 안전한 코드가 된다. 이건 직접 구현하면서 보도록 하겠다. 그럼 이제 직접 구현을 해보도록 하자!

Stack 구현

stack libary가 이미 존재하기는 하지만, 직점 스택을 구현하여 백준 10828번: 스택 문제를 풀어 보겠다! 스택은 array와 linked list를 이용하여 구현할 수 있다. 여기서는 linked list를 이용하여 구현보겠다.

1. 직접 구현한 풀이

linked list를 이용하여 직접 stack을 구현한 풀이다.

#include <iostream>
#include<stdlib.h>
using namespace std;

typedef struct node{
    int data;
    struct node *next;
} node;

typedef struct{
    int cnt;
    node *top;
} stack;

void push(stack *s, int num){
    node *n = (node*)malloc(sizeof(node));
    n->data = num;
    n->next = s->top;
    s->top = n;
    s->cnt++;
}

int pop(stack *s){
    if(s->cnt==0) return -1;
    int tmp = s->top->data;
    node *n = s->top;
    s->top = n->next;
    free(n);
    s->cnt--;
    return tmp;
}

int size(stack *s){
    return s->cnt;
}

int isempty(stack *s){
    if(s->cnt==0) return 1;
    return 0;
}

int top(stack *s){
    if(s->cnt==0) return -1;
    return s->top->data;
}

int main(){
    int n; cin>>n;
    string str; int num;
    stack s; s.cnt=0; s.top=NULL;
    while (n--){
        cin>>str;
        if(str=="push"){
            cin>>num; push(&s, num);
        }
        else if(str=="pop") cout << pop(&s) << '\n';
        else if(str=="size") cout << size(&s) << '\n';
        else if(str=="empty") cout << isempty(&s) << '\n';
        else if(str=="top") cout << top(&s) << '\n';
    }
}

2. 라이브러리를 이용한 풀이

이건 옛날에 풀어뒀던 라이브러리를 이용한 풀이다.

#include <iostream>
#include <stack>
using namespace std;

int main() {
    
   int n; cin >> n;
   stack<int> st;

   while (n--) {
      string s; cin >> s;
      if (s == "push") {
         int x; cin >> x;
         st.push(x);
      }
      else if (s == "top")
         cout << (st.empty() ? -1 : st.top()) << '\n';
      else if (s == "size")
         cout << st.size() << '\n';
      else if (s == "empty")
         cout << st.empty() << '\n';
      else {
         if (st.empty()) cout << -1 << '\n';
         else {
            cout << st.top() << '\n';
            st.pop();
         }
      }
   }
   return 0;
}