Stack(스택)

Stack(스택)

데이터를 한 쪽 끝에서만 넣고 뺄수 있는 LIFO(Last In First Out) 형식의 자료 구조(FILO이라고도 할 수 있다.)

Stack 연산

스택 자료구조에는 LIFO(Last In First Out) 혹은 FILO(First In Last Out)를 따르게 되며, 가장 마지막에 들어간 데이터를 가장 먼저 제거하는 구조가 된다. 

 

해당 구조를 만족하기 위해 여러 연산이 필요하다.

1. Push(Data) : 데이터 하나를 스택의 가장 윗 부분에 추가하는 연산
2. Pop() : 마지막에 추가된 데이터를 제거하는 연산
3. Top() : 스택의 제일 위에 있는 데이터로 마지막에 추가된 데이터를 찾는 연산
4. isEmpty() : 스택 자료구조에 데이터가 있는지 여부를 확인하는 연산

기본적인 스택의 연산은 이정도이고 추가로 size()와 같은 연산을 추가로 사용할 수 있다.

Stack 구현

스택이 구현하는 것에는 배열과 리스트로 구현할 수가 있다.

다만 배열의 특성상 배열은 데이터의 사이즈가 정해져 있고 만약 이러한 제약을 극복하고 싶다면 resizing을 통해 배열의 사이즈를 늘려주거나 스택을 리스트로 구현해야한다.

 

배열과 리스트로 구현함에 따라 특징이 다르기 때문에 상황에 따른 효율성을 따져서 적용이 필요하다.

예를 들어 총 데이터의 크기를 예측할 수 있을 때는 배열형이 좀더 접근에 용이 할 수 있으며, 예측이 어려울 경우 re-sizing에 대한 비용을 아낄수 있는 리스트형 스택이 더 용이할 수 있다.

Array Stack

배열형 스택은 우선 접근속도가 빠르다. 다만, 배열의 사이즈를 늘려주거나 줄이는 re-sizing이 필요할 때 효율성이 떨어지게 된다.

이유는 re-sizing된 배열에 기존 데이터들을 복사해 주어야 하기 때문이다.(배열의 크기를 잘못 예측하면 빈번하게 re-sizing이 발생하거나 너무 크게 예측할경우에는 메모리를 많이 차지하게 된다.)

#include <iostream>
#define stack_size 100
using namespace std;
 
struct stack {
    int top = -1;
    int arr[stack_size];
    void push(int data) {
        if (top == stack_size-1) {
            printf("stack is full\n");
            return;
        }
        arr[++top] = data;
    }
    int pop() {
        if (empty()) {
            printf("stack is empty\n");
            return -1;
        }
        return arr[top--];
    }
    int peek() {
        if (empty()) {
            printf("stack is empty\n");
            return -1;
        }
        return arr[top];
    }
    bool empty() {
        return top <= -1;
    }
};

int main() {
    stack st;
    //현재 스택은 비워져있는 상태
    cout << "is stack empty? " << st.empty() << endl;
    cout << st.pop() << endl;
    cout << st.peek() << endl;
   
    for (int i = 0; i < stack_size-1; i++)
        st.push(i + 1);
    //for 루프가 돌면 스택은 1개만 저장 가능한 상태
    cout << endl;
    cout << "after for loop"<<endl;
    
    st.push(15);
    st.push(120);        //스택은 전부 채워져 있는 상태 stack is full 출력
        
    st.pop();            //스택에서 한 개가 비워짐, 1개 채울 수 있는 상태
 
    st.push(120);
 
    cout<<endl;  
    while(!st.empty())    //스택이 비워지면 while루프 종료
        cout << st.pop() << endl;
    
    return 0;
}

Linked List Stack

스택을 Linked List로 구현시 해당 장점을 가져올 수 있다. 우선 데이터의 사이즈에 대한 걱정은 없다. 그리고 링크드 리스트를 구현하는 방식에 따라서 tail를 top으로 사용해도 되고 root를 top으로 사용해도 된다. 다만 stack의 구조에 맞춰서 정의를 하면 문제가 없다.

#include <iostream>
#define INF 987654321
 
using namespace std;
 
struct node {
    int data;
    struct node *next;
};
 
struct stack {
    node *top;
        int len;
        stack(){
                top = NULL;
                len = 0;
        }
        int size() {
        return len;
    }
    int isEmpty() {
        //return top == NULL;
                return len==0;
    }
 
    void push(int data) {
         
        node *newNode = (node*)malloc(sizeof(node));
        newNode->data = data;
        newNode->next = top;
        top = newNode;
                len++;
    }
 
    int pop() {
        int ret;
        if (isEmpty()) return INF;
        node *here = top;
        ret = here->data;
        top = here->next;
        free(here);
                len--;
        return ret;
    }
 
    int peek() {
        if (isEmpty()) return INF;
        node *here = top;
        return here->data;
    }
};
 
stack st = { NULL };
 
int main() {
     
    cout << st.peek() << endl;
    for (int i = 1; i <= 3; i++) 
        st.push(i);
     
    cout << st.pop() << endl;
    cout << st.pop() << endl;
    for (int i = 4; i <= 6; i++)
        st.push(i);
 
    while (!st.isEmpty())
        cout << st.pop() << endl;
 
}

---

[자료구조] 그림으로 쉽게 보는 배열 스택(Stack)과 구현

 

[자료구조] 스택(Stack)이란 - Heee's Development Blog