05. 스택, 큐, 덱 - Stack

01. 스택 정의, 값 넣기/빼기

젠가를 떠올려봅시다. 통에서 젠가 블럭을 꺼낼때, 하나씩 꺼내려면 당연히 위에서 하나씩 꺼내야 할 것입니다. 만약 실수로 아래쪽에 종이 한 장을 넣어놔서 다시 꺼내려고 한다면, 통을 엎어버리지 않는 이상 위에 있는 모든 블럭을 다 꺼내야 할 것입니다.

우리는 젠가처럼 데이터를 넣는 곳과 빠지는 곳의 위치가 같은 자료구조를 스택이라고 부릅니다. 즉, 젠가와 동일하게 맨 아래에 있는 데이터를 꺼내기 위해서는 그 위의 데이터들을 모두 꺼내야 할 것입니다. 우리는 이런 구조를 후입선출 구조 (LIFO; Last In First Out) 라고 부릅니다.

영어 단어 Stack은 "쌓아올리다" 라는 의미를 갖고 있습니다. 스택 자료구조 또한 데이터가 들어가는 곳과 나가는 곳이 같다보니 탑을 쌓는 것과 비슷한 모양을 띄게 될 것입니다.

 

stack은 크게 5가지 함수 사용이 가능합니다.

1. push(x)
2. size()
3. empty()
4. top()
5. pop()

1. push(x) : x를 stack의 맨 위에 올려 놓습니다.

2. size() : stack 위에 쌓인 블럭의 개수를 반환합니다.

3. empty() : stack 위가 비어있다면 true, 비어있지 않다면 false를 반환합니다.

4. top() : stack의 맨 위에 있는 숫자 값을 반환합니다. 단, stack에서 그 블럭을 제거하지는 않습니다.

5. pop() : stack의 맨 위에 있는 숫자 값을 반환합니다. 단, 동시에 stack에서 그 블럭을 제거합니다.

이처럼 젠가에서 블럭을 넣고 뺀다고 가정한다면, 당연히 넣고 빼는 작업은 다른 블록들에게 영향을 주지 않습니다. 즉 스택 자료구조 또한 삽입과 삭제 연산의 시간복잡도는 O(1)라고 볼 수 있을 것입니다.

 

< 스택의 응용 >

 

 스택을 활용하면 여러 문제들을 해결할 수 있습니다. 대표적인 예시를 확인해볼까요?

괄호로 이루어진 문자열이 이루어져 있다고 가정합시다. 당연하겠지만, 일반적인 괄호는 여는 괄호 뒤에 닫는 괄호가 나와야 할 것입니다. 그런식으로 괄호가 배치되어 있는 경우, 우리는 이것을 올바른 괄호 문자열이라고 부르겠습니다.

 

예를 들어 (())((()())) 같은 문자열은 올바른 괄호 문자열이며, ())(는 올바르지 않은 괄호 문자열 입니다.

문자열의 길이가 짧다면 모를까, 길어진다면 어떤 문자열이 올바른 괄호 문자열인지 판단하기 어려울 것입니다. 이것을 판별하기 위한 코드를 작성하는 과정에서 스택이 사용될 수 있습니다.

 

방법은 간단합니다. 만약 여는 괄호가 온다면 그것을 스택에 넣고, 닫는 괄호가 온다면 스택에 있는 여는 괄호를 빼면 됩니다. 물론 닫는 괄호가 왔는데 스택에 아무것도 없거나, 모든 글자를 다 처리하였음에도 스택에 괄호가 남아있다면 올바른 괄호 문자열이 아니겠죠?

 

이런식으로, 스택은 쌍을 이루고 있는 것들이 올바르게 배치되어 있는지 확인할 때 유용하게 사용할 수 있습니다.

코드로는 다음과 같이 구현해볼 수 있습니다.

function solution(str)
  set s = empty stack
  for i = 0 ... i < str.size  // 주어진 문자열을 순회합니다.
    if str[i] == '('          // 열린 괄호에 대해서는
      s.push('(')             // stack에 열린 괄호를 넣어줍니다.
    else
      if s.empty() == true    // 닫힌괄호가 나온 상황에서, stack이 비어있다면,
        return false          // 올바른 괄호 문자열이 아닙니다.
      s.pop()                 // 가장 위에 있는 값을 비워줍니다.

  if s.empty() == false       // 전부 순회했는데도 불구하고 stack이 비어있지 않다면
    return false              // 올바른 괄호 문자열이 아닙니다.
  return true                 // 전부 통과했다면 올바른 괄호 문자열 입니다.

사실 이런 예시 말고도, 컴퓨터에서는 스택을 자주 사용하고 있습니다. 더 자세한 내용은 뒤에서 알아보겠습니다.

 

 

< 괄호 문자열 >

괄호 문자열이란 두 개의 괄호 인 ‘(' 와 ')’로만 이루어진 문자열인데, 이 중 올바르게 구성된 문자열을 올바른 괄호 문자열이라고 합니다.

올바르게 구성된 괄호 문자열은 열린 괄호가 있다면 그 뒤에 대응하는 닫힌 괄호가 있는 구조인데,

올바른 괄호 문자열      : (), (()), (()()), (()())((()))
올바르지 않은 괄호 문자열 : ), ()), (())(), (()((())())

다음과 같은 예시가 있습니다.

괄호 문자열이 주어질 때, 해당 문자열이 올바른지 아닌지 판단할 수 있는 코드를 작성해봅시다. 

>> 답 : 위의 코드

 

< 배열과 스택의 차이 >

앞에서, 배열에서 값을 삽입/삭제하는데에는 O(N) 의 시간복잡도가 소요된다고 이야기했습니다. 그러면서 덧붙였던 말을 기억하시나요?

그렇다면 어떻게 해야 이런 이동을 최소화 할 수 있을까요? 배열의 크기가 무한하다는 가정하에, 값 맨 뒤에 새로운 값을 삽입하면 됩니다. 이런 경우엔 다른 값들의 이동이 전혀 존재하지 않기 때문에 O(1) 의 시간복잡도를 보일 것입니다.

 

즉, 맨 뒤에서 값을 넣고, 뺀다면 시간복잡도가 O(1)이 나온다는 말이었습니다. 자세히 바라보면 삽입과 삭제 연산이 동일한 곳에서 진행되므로, 결국 스택과 동일한 구조가 됩니다!

즉, 배열에서 삽입과 삭제 연산이 발생하는 장소를 맨 뒤로만 제한한다면, 우리는 배열을 스택처럼 사용할 수 있을 것입니다.

삽입에 해당하는 함수 push(E)와 삭제에 해당하는 함수 pop()는 다음과 같이 구현해볼 수 있습니다.
단, 불가능한 상황에서는 throw exception()을 수행해야 하며, 배열에서 사용 가능한 index 범위는 0에서 maxsize - 1 사이라고 가정합니다.

function push(arr, E)
  if arr.size == maxsize          // 배열에 이미 원소들이 가득 채워져 있다면,
    throw exception()             // 에러 메세지를 던져줍니다.
  arr.append(E)                   // 정상적인 상황이라면, E를 
                                  // 마지막 위치에 추가해줍니다.

function pop(arr) 
  if arr.size == 0                // 배열에 아무런 원소도 없다면
    throw exception()             // 에러 메세지를 던져줍니다.
  set last = arr[arr.size - 1]    // 정상적인 상황이라면, 마지막 값을 변수에 저장해두고
  delete arr[arr.size - 1]        // 맨 끝에 있는 값을 실제로 제거한 뒤
  return last                    // 마지막에 있었던 값을 반환해줍니다.

 배열을 스택처럼 사용한다면, 일반적인 스택과 달리 중간 데이터를 확인할 수 있다는 엄청난 장점이 생깁니다. 그렇지만 배열을 생성할 때 정의한 길이보다 스택에 들어가는 값이 더 많다면 문제가 생길 수 있다는 단점이 생깁니다.

그렇다면, 배열을 스택처럼 사용하기 위해 push(E), pop()을 구현해 봅시다.

 단, 불가능한 상황에서는 throw exception()을 수행해야 하며, 배열에서 사용 가능한 index 범위는 0이상 maxsize - 1 이하라고 가정합니다.
또한 pop 함수는 마지막 값을 제거함과 동시에 그 값을 반환해줘야하는 함수임에 유의합니다.

 

 

< 재귀와 콜 스택 >

우리는 앞에서 재귀함수에 대해서 배웠습니다. 분명 재귀적으로 호출한 함수는 실행이 되고, 이후에 종료가 되면 그 함수를 수행한 지점으로 되돌아간다고 배웠는데, 실제로는 어떤 식으로 작동할까요?

컴퓨터는 함수가 실행되면, 당연히 함수가 실행되는 지점을 기록해놓아야 합니다. 그래야 함수가 종료되고 난 후 원래 지점으로 돌아갈 수 있겠죠. 당연히 재귀함수가 된다면 저장해야 할 지점이 한두개가 아니기 때문에, 기록하기 어려울 것입니다.

자, 생각해봅시다. 재귀함수 5개가 실행되었다고 가정해봅시다. 마지막 함수가 종료되면, 어디로 돌아가야 할까요? 4번째 함수? 아니면 맨 처음 함수? 당연히 4번째 함수가 되어야 할 것입니다. 즉, 함수가 종료되고 돌아가야 할 지점은 마지막으로 실행 중이었던 함수가 될 것입니다.

조금 어렵지만, 천천히 고민해본다면, 함수 중간 지점을 저장하는 자료구조는 스택이 되어야 할 것입니다. 그래야 맨 마지막에 저장했던 복귀 지점을 맨 먼저 실행할 테니까요! 이런 식으로 함수 실행과정을 저장하기 위해 사용하는 스택을 우리는 콜 스택이라고 부릅니다.

2개의 함수를 호출에 더해야 하는 경우에는 콜 스택이 어떻게 바뀔까요? 동시에 2개의 함수가 들어가는 것이 아니라, 다음과 같이 순차적으로 첫 번째 함수 먼저 들어가서 다 계산을 한 다음 두 번째 함수가 콜 스택에 들어가게 됩니다. 단, 다음 경우에서는 recur(n - 1)이 recur(n - 2)보다 먼저 호출된다고 가정하고 살펴봅시다.

8fb21eda-fd34-43cd-a3a9-297955ba7b3e.mp4

0.40MB

 

< 피보나치 집중탐구 >

재귀를 활용하여 피보나치 수를 구하는 코드는 다음과 같습니다.

function fibbo(x)
    if x <= 1
        return 1
    else
        return fibbo(x - 2) + fibbo(x - 1)

여러분들은 회사에 개발자로 채용되어 프로그램 실행 과정에 대해 연구하고 있습니다. 이번에 여러분들의 목표는 위에서 정의한 fibbo 함수를 실행했을 때, 콜 스택에 함수가 어떻게 쌓이는지 분석하는 것입니다.

만약 여러분들이 fibbo(6)을 실행했다고 가정하면, 시스템적으로 fibbo(1)이 처음 호출되는 순간 콜 스택에는 fibbo(1)을 포함하여 총 몇 개의 함수가 들어있을지 생각해봅시다. 단, fibbo(x - 2)와 fibbo(x - 1) 함수 중 fibbo(x - 2) 함수가 먼저 호출된다고 가정해도 좋습니다.

 

< 스택 STL >

C++에서는 stack이라는 STL을 이용할 수 있습니다. stack을 사용하기 위해서는 #include <stack> 헤더와, stack<T> name; 형태의 선언이 필요합니다. T는 타입으로, 스택 안에 들어갈 원소의 타입을 적어줘야 합니다. 또, stack은 원래 std::stack으로 쓰여야 하므로 using namespace std;를 미리 적어 stack 만으로도 이용이 가능하도록 하는 것이 좋습니다.

 

정수를 관리할 stack은 다음과 같이 선언해 볼 수 있습니다.

#include <iostream>
#include <stack>

using namespace std;

int main() {
    stack<int> s;
    return 0;
}

stack을 이용할 때 자주 사용되는 것은 다음 5가지 입니다.

1. push(E) : 맨 위에 데이터 E를 추가합니다.
2. size() : 현재 stack에 들어있는 데이터의 수를 반환합니다.
3. empty() : 현재 stack이 비어있다면 true, 아니라면 false를 반환합니다.
4. top() : stack의 가장 위에 있는 데이터를 반환합니다.
5. pop() : stack의 가장 위에 있는 데이터를 뺍니다. C++에서의 stack은 pop() 호출시 삭제만 할 뿐, 해당 값을 반환하지 않습니다. 이는 C++의 철학상, 하나의 함수는 하나의 역할만 해야한다는 점과 안전성 측면에서 이렇게 설계되어져 있습니다. 꼭 유의하시기를 바랍니다.

따라서 다음과 같이 코드를 작성해볼 수 있습니다.

#include <iostream>
#include <stack>

using namespace std;

int main() {
    stack<int> s;              // 정수를 관리할 stack을 선언합니다. => 빈 스택
    s.push(2); 
    s.push(5);
    s.push(9);
    
    cout << s.top() << endl;   // 가장 나중에 들어온 원소를 출력합니다. => 9
    s.pop();                   // 가장 나중에 들어온 원소를 제거합니다.
    cout << s.size() << endl;  // 원소의 개수를 출력합니다 => 2
    while(!s.empty()){         // 가장 나중에 들어간 원소부터 순서대로 출력합니다.
        cout << s.top() << endl; // 순서대로 5 2 출력됩니다.
        s.pop();                 // 가장 위에 있는 원소를 뺍니다.
    }

    return 0;
}

 

< 문자열 같은걸 끼얹나? >

문자열을 입력 받아 스택에서 일련의 처리를 받아 출력하는 다음과 같은 코드가 있습니다.

function solution(str)
  set s = empty stack
  for i = 0 ... i < str.size
    s.push(str[i])
  while s.empty() == false
    print(s.pop())

만약 solution(“codetree”) 를 실행하게 된다면, 출력 값은 무엇이 될까요?

 

< 배열 vs 스택 >

- 배열은 스택처럼 사용 가능

- 스택은 내부 상태를 건드리지 않으면 특정 값이 스택에 있는지 확인할 수 없지만, 배열은 가능하다.

- 스택의 pop 연산을 배열로 구현하기 위해선 배열의 맨 뒤 인덱스의 값을 제거하면 된다. 

< 스택의 개념 >

< 증가하는 부분 수열 >

전체 수열 중 일부를 골라 부분 수열을 만들었는데, 만약 그 부분 수열이 오름차순으로 증가하는 수열이라면 우리는 이 수열을 증가하는 부분 수열 (Increasing Subsequence) 라고 부릅니다. 예를 들어, {10, 30, 20, 50, 60, 15} 라는 수열이 있다면, {10, 30, 50, 60}도 증가하는 부분 수열이고, {20, 50, 60}도 증가하는 부분 수열이라고 할 수 있습니다. 그 중에서도 우리는 첫 번째 원소를 시작으로 순서대로 보면서 마지막으로 골라진 원소보다 더 큰 원소가 나타나면 바로 골라주는 식으로 증가 부분 수열을 만들어보려고 합니다. {10, 30, 20, 50, 60, 15}가 주어졌다면 원소 10을 시작으로 하여 순서대로 보다보면 30이 골라지고, 그 다음에는 증가하기 위해 50이 골라지고 끝으로 60이 골라지게 되어 {10, 30, 50, 60} 이 됩니다. 코드를 잘 읽고, 증가하는 부분 수열의 값을 순서대로 출력하는 알고리즘을 완성해보세요.

function solution(arr)
  set s = empty stack
  for i = 0 ... i < arr.size
    set val = arr[i]
    if s.empty() == (1) true  or val > (2) s.top() 
      (3) s.push (val) 
      print(val)

 

< 괄호 문자열의 적합성 판단 >

괄호 문자열은 두 개의 괄호 기호인 ' ( ' 와 ' ) ' 만으로 구성되어 있는 문자열 입니다. 괄호 문자열은 다음과 같이 2가지로 분류할 수 있습니다.

1. 올바른 괄호 문자열 : 괄호를 열고 닫음이 분명한 문자열을 말합니다.
2. 올바르지 못한 괄호 문자열 : 괄호를 열고 닫음이 분명하지 못한문자열을 말합니다

입력으로 주어진 괄호 문자열이 올바른지, 그렇지 못한지를 판단하여 결과를 출력하는 프로그램을 작성하여 보세요.

입력 형식

첫 번째 줄에는 하나의 괄호 문자열이 한 줄에 공백없이 주어집니다.

• 2 ≤ 괄호 문자열의 길이 ≤ 50

출력 형식

입력 괄호 문자열이 올바른 괄호 문자열이면 “Yes”, 아니면 “No”을 출력합니다.

 

******************* 해설 ******************

**C++14
#include <iostream>
#include <stack>
#include <string>

using namespace std;

// 변수 선언
string str;
stack<char> s;  

int main() {
    // 입력:
    cin >> str;

    for(int i = 0; i < (int) str.size(); i++) {
        if(str[i] == '(')
            s.push('(');
        else {
            if(s.empty()) {
                cout << "No";
                return 0;
            }
            s.pop();
        }
    }

    if(s.empty())
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

 

**파이썬3
import sys

class Stack:
    def __init__(self):          # 빈 스택 하나를 생성합니다.
        self.items = []
                
    def push(self, item):        # 스택에 데이터를 추가합니다.
        self.items.append(item)
                
    def empty(self):             # 스택이 비어있으면 True를 반환합니다.
        return not self.items
                
    def size(self):              # 스택에 있는 데이터 수를 반환합니다.
        return len(self.items)
        
    def pop(self):               # 스택의 가장 위에 있는 데이터를 반환하고 제거합니다.
        if self.empty():
            raise Exception("Stack is empty")
            
        return self.items.pop()
                
    def top(self):               # 스택의 가장 위에 있는 데이터를 제거하지 않고 반환합니다.
        if self.empty():
            raise Exception("Stack is empty")
                        
        return self.items[-1]


# 변수 선언 및 입력:
string = input()
s = Stack()

for char in string:
    if char == '(':
        s.push('(')
    else:
        if s.empty():
            print("No")
            sys.exit(0)

        s.pop()

if s.empty():
    print("Yes")
else:
    print("No")

 

< 낡은 컴퓨터 >

낡은 컴퓨터를 구해서 코드를 돌려봤는데, 재귀함수를 잘 처리하지 못했습니다.

여러분들이 내부를 확인해 본 결과, 콜 스택에 함수가 5개 이상 들어가면 즉시 프로그램을 종료하는 것을 발견하였습니다.

function solution(x)
    if x == 0
        print("Hello")
        return
    for i = 0 ... i < x
        solution(i)

만약 이런 코드를 만들어서 solution(10)을 실행시키면, 프로그램이 강제 종료 되기 전 "Hello"는 몇 번이나 출력 될 지 생각해봅시다.

 

>> 

solution(0) 이 실행되는 경우 Hello 가 출력되므로 solution(0) 의 호출 횟수를 세어봅니다.

 

< 스택 체험 >

function solution()
    set s = empty stack
    s.push(10)
    s.push(15)
    s.pop()
    s.push(20)
    s.pop()
    s.push(12)

    set result = s.size()
    result += s.pop()
    result += s.pop()
    if s.empty() == true
        result *= 2
    
    return result

다음 코드를 실행했을 때, 반환되는 결과값은 무엇일까요?

>> 48