스택 (Stack)

스택이란?

스택

스택은 후입선출(LIFO, Last In First Out)의 자료구조로, 데이터를 쌓아 올리는 방식으로 저장한다. 스택에 값을 넣는 행위를 Push, 값을 꺼내는 행위를 Pop이라고 한다.

이미지 처럼 9라는 값을 넣고(Push) 다시 꺼내어(Pop)도 9가 나오게 된다. 이 자료구조는 컴퓨터의 메모리 구조에서 함수 호출과 복귀 주소를 저장하는데 사용된다.

프로세스가 메모리에 올라가서 함수의 호출을 받으면, 함수의 호출 정보를 스택에 저장하고 함수가 종료되면 스택에서 꺼내어 복귀 주소로 사용한다. 스택은 배열이나 연결 리스트로 구현할 수 있다.

스택의 필수기능 구현

peek(): 스택의 맨 위에 있는 데이터를 반환한다. 말그대로 훔쳐보는 것이기 때문에 데이터를 꺼내지 않는다.

method peek(): Item is
    return stack[top]

push(item): 스택의 맨 위에 데이터를 추가한다.

method push(Item item) is
    if stack is full then
        throw StackOverflowException
    top = top + 1 //마지막으로 들어간 요소의 인덱스를 증가시킨다.
    stack[top] = item //새로운 요소의 값을 넣는다.

pop(): 스택의 맨 위에 있는 데이터를 꺼내어 반환한다.

method pop(): Item is
    if stack is empty then
        throw StackUnderflowException
    Item item = stack[top] //맨 위에 있는 요소를 꺼낸다.
    top = top - 1 //맨 위에 있는 요소를 꺼냈으므로 인덱스를 감소시킨다.
    return item

스택의 구현

이 예제에서는 배열과, 연결 리스트로 스택을 구현한다.

template <typename T>
class Stack {
    public:
        // 가상 소멸자
        virtual ~Stack() = default;
        virtual void push(const T& item) = 0;
        virtual T pop() = 0;
        virtual T peek() = 0;
        virtual bool is_empty() = 0;
        virtual int size() = 0;
};

두 가지 방식 모두 구현하기 위해, 상위 클래스를 만들어 공통된 메서드를 정의한다.

#include <iostream>
#include "Stack.h"
using namespace std;

template <typename T>
class ArrayStack final : public Stack<T> {
private:
    T* arr;
    int top;
    int cap;
public:
    explicit ArrayStack(const int cap): top(-1), cap(cap) {
        arr = new T[cap];
    }

    ~ArrayStack() override {
        delete[] arr;
    }

    void push(const T& item) override {
        if (top == cap -1) {
            throw overflow_error("Stack is full");
        }
        arr[++top] = item;
    }

    T pop() override {
        if (is_empty()) {
            throw underflow_error("Stack is empty");
        }

        return arr[top--];
    }

    T peek() override {
        if (is_empty()) {
            throw underflow_error("Stack is empty");
        }

        return arr[top];
    }

    bool is_empty() override {
        return top == -1;
    }

    int size() override {
        return top + 1;
    }

    friend ostream& operator<<(ostream& os, const ArrayStack<T>& stack) {
        os << "Stack: [";
        for (int i = stack.top; i >= 0; i--) {
            os << stack.arr[i];
            if (0 < i) os << ",";
        }
        os << "]";
        return os;
    }
};

#include "Stack.h"
#include <iostream>
using namespace std;


template <typename T>
class LinkedListStack : public Stack<T> {
private:

    //연결 리스트를 위한 Node 구조체
    struct Node {
        T data;
        Node* next;

        explicit Node(const T& value) : data(value), next(nullptr) {}
    };

    Node* top;
    int cap;

public:
    explicit LinkedListStack(int capacity) : cap(capacity), top(nullptr) {}
    ~LinkedListStack() override {
        while (top != nullptr) {
            Node* temp = top;
            top = top->next;
            delete temp;
        }
    }
    void push(const T &item) override {
        Node* newNode = new Node(item);
        newNode->next = top;
        top = newNode;
        cap++;
    }

    T pop() override {
        if (is_empty()) {
            throw underflow_error("Stack is empty");;
        }
        Node* temp = top;
        T popped = temp->data;
        top = top->next;
        delete temp;
        cap--;

        return popped;
    }

    T peek() override {
        if (is_empty()) {
            throw underflow_error("Stack is empty");;
        }
        return top->data;
    }

    bool is_empty() override {
        return top == nullptr;
    }

    int size() override {
        return top == nullptr ? 0 : cap;
    }

    friend ostream& operator<<(ostream& os, const LinkedListStack<T>& stack) {
        os << "Stack: [";
        Node* current = stack.top;
        while (current != nullptr) {
            os << current->data;
            if (current->next != nullptr) {
                os << ", ";
            }
            current = current->next;
        }
        os << "]";
        return os;
    }
};

스택의 사용

LinkedListStack<int> stack(100);
stack.push(10);
stack.push(20);

cout << stack << endl;

const int popped = stack.pop();
cout << "popped: " << popped << endl;
cout << stack << endl;

stack.push(75);
cout << "pushed: " << 75 << endl;
cout << stack << endl;