[자료구조] 3. 스택(Stack)

스택

스택은 LIFO(Last in, first out)의 후입선출 구조를 가지고 있는 자료구조입니다. 다시 말해서, 마치 책을 쌓아놓는 것처럼 가장 마지막에 넣은 데이터를 가장 먼저 빼낼 수 있는 구조입니다.

활용

스택은 정말 다양한 곳에서 사용되는데, 예를 들어 컴퓨터의 메모리 영역에서도 스택이 활용됩니다. 재귀 함수를 사용하여 함수 내에서 다른 함수를 계속 호출할 때도 호출한 함수들이 스택에 차례로 쌓이며 작동하며, 운영 체제에서 되돌리기(Ctrl + Z)를 사용하는 것도 이전 작업을 스택에 쌓아놓고 되돌리는 원리입니다.

이뿐만 아니라 스택은 다른 자료구조의 구현을 위해서도 사용됩니다.

ADT

int getSize()
bool isEmpty()

스택의 핵심은 삽입의 push, 추출하는 pop 그리고 원소를 추출하지는 않고 가장 위의 원소를 확인할 수 있는 top이 있습니다.

// typename T
void push(T& element)
T& pop()
T& top() // 또는 peek()

구현

스택은 배열이나 연결 리스트로 쉽게 구현할 수 있습니다. 이때의 시간 복잡도는 삽입, 삭제, 조회 모두 O(1) 시간에 가능합니다. 아래는 C++에서 연결 리스트로 구현한 스택의 예시입니다.

struct Node {
    int data;
    Node *next;
};

class LinkedListStack {
  private:
    Node *topNode;
    int size;

  public:
    LinkedListStack() {
        topNode = nullptr;
        size = 0;
    }
    bool isEmpty() { return (size == 0); }
    int getSize() { return size; }
    void push(int data) {
        Node *newnode = new Node;
        newnode->data = data;
        newnode->next = topNode;
        topNode = newnode;
        size++;
    }
    int pop() {
        if (isEmpty())
            return -1;
        Node *tempnode = topNode;
        topNode = tempnode->next;
        int ret = tempnode->data;
        delete tempnode;
        size--;
        return ret;
    }
    int getTop() {
        if (isEmpty())
            return -1;
        return topNode->data;
    }
};

효율

스택에서 각 작업의 시간복잡도는 O(1)이고, N개 원소 저장시에 공간복잡도는 O(N)입니다.

+활용: 괄호 짝 맞춤 문제

알고리즘에서 스택 자료구조를 활용한 대표적인 문제 중 하나가 괄호 짝 맞춤 문제입니다. 이 문제는 여러 개의 소괄호 (), 중괄호 {}, 대괄호 []로 이루어진 문자열에서 각각의 괄호의 짝이 맞는지 확인하는 문제입니다. 이를 스택을 사용하여 풀 수 있습니다.

여는 괄호 '({[' 를 만나면 해당 괄호를 스택에 push 하고, 닫는 괄호 ')}]'를 만나면 스택의 가장 위에 있는 괄호와 짝이 맞는지 확인하는 방식으로 문제를 해결할 수 있습니다. 만약 짝이 맞다면 스택에서 해당 여는 괄호를 pop 하고 계속 진행하며, 짝이 맞지 않는 경우나 스택이 비어있지 않은데 닫는 괄호가 나온 경우는 괄호 짝이 맞지 않는 것으로 판단할 수 있습니다.

이런 방식으로 괄호 짝 맞춤 문제를 풀면, 스택의 특성을 활용하여 효율적으로 괄호의 짝을 확인할 수 있습니다. 이는 스택이 자료의 삽입과 삭제가 상수 시간 O(1)에 이루어지는 특성을 활용한 예시로서 자주 활용되는 유형 중 하나입니다.

+활용: 수식 계산 문제

스택을 활용하면 수식을 계산할 수 있습니다. 예를들어 2-7*4라는 수식을 순서대로 계산한다면 -가 *보다 먼저 계산되어 연산자 우선순위를 지키지 않는 틀린 연산이 됩니다. 이때 스택을 이용하면 연산자의 우선순위를 지키며 문제를 해결할 수 있습니다.

 

우선 연산자 저장용 스택 operatorStack과 숫자 저장용 스택 valueStack을 생성합니다.

이후 수식을 앞에서부터 훑어나가며 숫자가 있으면 valueStack에 연산자가 있으면 operatorStack에 push 해줍니다. 이때 연산자를 만났을 때 만약 해당 연산자가 operatorStack.top()에 있는 연산자보다 우선순위가 높거나 같다면 다음 계산 알고리즘을 시행합니다.

연산자의 우선순위가 높다는 것은 해당 연산을 먼저 해야한다는 의미입니다. 즉, *가 +보다 연산자의 우선순위가 높습니다.

계산 알고리즘: operatorStack에서 연산자를 pop해준다. 이를 op라고 한다. 그리고 숫자를 2번 pop 해주는데, 이를 순서대로 각각 v1, v2라고 한다. 이후 v2 op v1을 연산한 뒤 다시 valueStack에 push 해준다.

 

모든 수식을 훑을 때까지 이를 진행한 뒤 수식이 끝나면 계산 알고리즘을 operatorStack이 빌 때까지 시행하면 됩니다. 마지막까지 진행하면 valueStack에 하나의 값이 남게 되는데, 이것이 수식을 계산한 결과입니다.