[자료구조] 스택(Stack)개념, 구현

스택(Stack)이란?

톱(Top)이라고 하는 한 쪽 끝에서 모든 삽입과 삭제가 일어나는 순서 리스트이다.

스택에서는 가장 마지막으로 삽입된 원소가 가장 먼저 삭제되는 LIFO(Last-In-First-Out)의 성질을 가진다.

예를 들어, 원소 A, B, C ,D 를 순서대로 스택에 삽입했다고 하면, 다음과 같은 상태가 된다

스택 초기화

여기서, 스택의 원소를 삭제해보자. 제일 마지막에 삽입된 원소는 Top에 위치한 "D" 이기 때문에, D가 삭제된다

원소 삭제 이후의 스택

원소 D는 삭제되고, C가 top 원소가 되었다.

이 상태에서 다시 원소를 삽입하면 다음과 같은 상태가 된다.

원소 추가 이후의 스택

 

스택(Stack)의 구현

위에서 알아본 스택을 c++로 구현해보았다. 배열을 이용해서 진행하였다.

stack.hpp

#ifndef stack_hpp
#define stack_hpp

template <typename T>
class Stack
{
public:
    Stack(int stackLength = 10);
    // 크기가 stackLength인 stack 초기화
    bool isEmpty() const;
    // stack의 원소 수가 0이면 True, 아니면 false 반환
    T& top() const;
    // stack의 top element를 반환
    void push(const T& element);
    // stack의 top에 원소 삽입
    void pop();
    // stack의 top에서 원소 제거
    void printStack() const;
    // stack의 원소들 출력
    
private:
    T* stack; // stack의 원소들이 담겨있는 배열
    int topIndex; // stack에서 top의 위치
    int length; // stack의 크기
    
};

#endif /* stack_hpp */

stack.cpp

#include "stack.hpp"
#include <iostream>
using namespace std;

template <typename T>
Stack<T>::Stack(int stackLength) : length(stackLength)
{
    if(length < 1)
        throw "Stack의 길이는 1 이상이어야 합니다";
    stack = new T[length];
    topIndex = -1;
}

template <typename T>
bool Stack<T>::isEmpty() const
{
    return topIndex == -1;
}

template <typename T>
T& Stack<T>::top() const
{
    if(isEmpty())
        throw "Stack이 비어있습니다";
    return stack[topIndex];
}

template <typename T>
void Stack<T>::push(const T &element)
{
    if (topIndex == length-1)
    {
        T* newStack = new T[length+1];
        for(int i = 0; i < length; ++i)
            newStack[i] = stack[i];
        delete[] stack;
        stack = newStack;
        length += 1;
    }
    stack[++topIndex] = element;
}

template <typename T>
void Stack<T>::pop()
{
    if(isEmpty())
        throw "Stack이 비어있습니다";
    stack[topIndex--].~T();
}


template <typename T>
void Stack<T>::printStack() const
{
    for(int i = topIndex; i>=0; --i)
        cout << stack[i] << endl;
}

이렇게 구현된 스택을 바탕으로 원소 입출력을 진행해보았다.

main.cpp

#include <iostream>
#include "stack.hpp"
#include "stack.cpp"

using namespace std;

int main(void)
{
    Stack<int> myStack(5);

    // 스택에 원소 삽입
    myStack.push(2);
    myStack.push(3);
    myStack.push(4);
    myStack.push(6);
    myStack.push(7);
    
    myStack.push(9); // 초기에 선언했던 길이 5보다 초과해도 문제없이 작동
    myStack.printStack(); // 스택 원소들 출력
    cout << "top : " << myStack.top() << endl; // 스택의 top 원소 출력
    cout << "after pop" << endl;
    myStack.pop();
    myStack.printStack(); // 스택 원소들 출력
    cout << "top : " << myStack.top() << endl; // 스택의 top 원소 출력
    
    
    return 0;
}