Stack (스택)

Python에는 array 개념이 없어지고 list만 남아있으므로 C++기반으로 알아보자. (이후 자료구조도 동일)

C++의 개념을 충분히 알고 있다는 가정하에 설명하므로 모르는 부분은 나의 블로그 페이지나(내가 정리를 해놓았다면?) 구글링을 해보자.

 

 

Stack

어원은 쌓다라는 의미로 이 의미와 비슷하게 쓰인다.

LIFO (Last-in First-out) 의 방식으로 작동한다.

Necessary Components

• push() : 데이터 저장
• pop() : 데이터 추출, 저장공간에서도 삭제
• top : 현재 데이터 사이즈 크기, 가장 위에 있는 데이터 위치

Addition operations

• peek() : 가장 위에 있는 데이터 확인
• empty() : stack이 비어있는지 확인
• full() : stack이 가득 차있는지 확인
• size() : 현재 stack이 차있는 크기

---

Implementation

• top 으로 가장 최근에 입력받은 변수 위치 표시
• 들어온 순서대로 저장 후 꺼낼때는 가장 늦게 들어온 순서대로 추출
• 비어있을 경우 top = -1, 가득찼을 경우 top = MAX_SIZE-1
• 기본 top = -1 인 이유 : 배열으로 stack 선언시 index가 0부터 시작하는데 이를 맞추어 주기 위함

//배열 기반 stack 구현

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

class ArrayStack{
private:
	// 배열 최대 크기 20
    const static int MAX_SIZE = 20;
    // top
    int top;
    // 배열 선언
    int data[MAX_SIZE];
public:
    ArrayStack(){
    	// top 위치 초기화
        top = -1;
    }
    ~ArrayStack(){}
    bool empty(){return top == -1;}
    bool full(){return top == MAX_SIZE-1;}
    int size(){return top + 1;}
    
    void push(int e){
        if(full()){
            throw "Stack is full";
            data[++top] = e;
        }
    }
    int pop(){
        if(empty()){
            throw "Stack is empty";
            return data[top--];
        }
    }
    int peek(){
        if(empty()){
            throw "Stack is empty";
            return data[top];
        }
    }
    void display(){
        cout<<"# of items: "<<size()<<endl;
        for(int i=0; i<=top; i++){
            cout<<"["<<data[i]<<"]"<<endl;
        }
    }

};

Time Complexity

• push() : O(1)
• pop() : O(1)

Pros & Cons

pros : straightforward

cons : space limitation

 

Solutions

1. STL vector(dynamic array) 이용하여 구현
2. Linked list 이용 (LinkedStack)

---

LinkedStack

//linux linked list code 참조
#include <iostream>

using namespace std;

class Item{
private:
    int id;
public:
    Item(int id){this->id = id;}
    int get_id(){return id;}
};
class Node{
private:
    Item item;
    Node* link;
public:
    Node(const Item &item):item(item){this->link = nullptr;}
    Node* get_link(){return this->link;}
    void set_link(Node* p){this->link = p;}
    Item get_item(){return item;}
};
class LinkedStack{
private:
    Node* top;
public:
    LinkedStack(){this->top = nullptr;}
    bool empty(){return this->top == nullptr;}
    void push(const Item &item){
        if(this->empty()){
            this->top = new Node(item);
        }
        else{
            Node* p = new Node(item);
            p->set_link(this->top);
            this->top = p;
        }
    }
    Item pop(){
        if(this->empty()){
            throw 'stack is empty';
        }
        else{
            Node* p = this->top;
            this->top = this->top->get_link();
            Item item =p->get_item();
            if(p != nullptr) delete p;
            return item;
        }
    }
    ~LinkedStack(){
        while(!this->empty()){
            //to free Node data in heap
            this->pop();
        }
    }
    void display(){
        for(Node* p = top; p != nullptr; p = p->get_link()){
            cout << p->get_item().get_id() << endl;
        }
    }
};

Time Complexity

• push() : O(1)
• pop() : O(1)

Pros & Cons

pros : 가변길이로 stack 크기에 제한이 없다

cons : 데이터 하나를 생성하는데 Node class크기만큼 메모리를 더 사용한다

 

만약 사용할 데이터 크기가 고정적이라면 "ArrayStack"을 활용하는게 더 효율적이다.

하지만 데이터의 크기가 가변적이라면 "LinkedStack"이 더 효율적 이다.