[자료구조] Stack & Queue

 Stack & Queue는 프로그래밍을 할 때 절대로 빼놓을 수 없는 알고리즘이다.

 마치 수학의 정석에도 닳고 닳게 보던 집합 챕터같은 느낌이랄까.

 은연중에 우리는 많은 코딩방식을 Stack과 Queue를 통해 하고있으며, 본 포스팅에선 이를 정리하려하는데...

 

 ...사실, Stack & Queue는 내가 2018년에 블로그 포스팅을 통해 정리를 한 번 했었다.

 티스토리 블로그가 아닌 Github 블로그에 말이다. 링크를 걸어놓은 Github 레파지토리는, Git이 뭔지도 몰랐던 신입사원시절에 '일단 Github가입부터' 했던 시절의 계정이며 지금은 활용되지않아 사장된 계정이다(저때도 기술 블로그와 에세이 블로그를 따로 만들고 디자인 어떻게 할 지 고민하다가 대략 만들어놓고 흐지부지 된 곳이다)

 

 이후에, 브런치도 갔다가 네이버도 갔다가...결국 글 쓰는 에디터가 티스토리가 가장 나와 맞는 것 같아서 여기에 안착했는데, 그러다보니 곳곳에 뿌려놓은 것들이 좀 있는 편이다(내가 숨겨놓고 잊은 내 보물찾기를 하는 기분이랄까)

 

 그래서 하기에 설명된 Stack & Queue에 대한 내용은, 2018년에 서술된 Github 블로그의 내용을 그대로 가져왔다.

 

---

 알고리즘을 이야기 할 때, 혹은 공부하려 할 때 가장 먼저 접하는 이론은 아마 십중팔구는 Stack과 Queue 를 보게 될 것이다. 대학생때 배웠던 자료구조-알고리즘 수업도 1장은 인트로, 2장이 Array, 3장이 Stack & Queue 였었다(아, 적고보니 Array 부터 포스팅 해야하는 건가, 싶은 생각이 드는데...이건 다음에 해야겠다. 이렇게 컨텐츠 적립하는 거지 뭐)

 

 그래서 첫 알고리즘 카테고리 포스팅으로 Stack 과 Queue를 생각했는데, 사실 이게 설명하기가 좀 애매한 구석이 있다.  그 애매한 게 뭐냐하면 너무 잘 알고 익숙한 것이라, 어떻게 설명을 해야 할 지 난감한게 문제다.

 

 어떻게 걷고 뛰는 건지에 대한 방법론을, 서른 둘이 된 지금의 시점에서 누군가에게 설명하라고 한다면..음..그냥 다리를 움직이면 걷고 뛰어요..라는 생각이 맨 처음에 드는 거랑 같은 느낌이랄까.

 

 그러니 일단, 정의부터 내려보자.

---

Stack

 한 단어로 정의하자면, LIFO다. Last In, First Out.

 마지막에 들어온 놈이, 가장 먼저 나간다.

 즉 입구와 출구가 하나다. 땅으로 깊게 파 놓은 구덩이를 생각해보자.

 

 그 구덩이에 데이터(변수든 Array든, 객체든 뭐든 여튼 하드웨어 적으로 메모리를 잡아먹는 무엇)를 집어넣고 그 위로 또 데이터를 집어넣는다. 그러고 나중에 데이터를 다시 꺼내려면, 옆으로 땅굴이라도 뚫지 않는 이상 가장 먼저 넣은 데이터를 우선적으로 꺼낼 수가 없다. 그 상태에서 꺼낼 수 있는 데이터는 가장 위에 보이는 데이터이다.

Stack 이라는 모바일 게임

 위 이미지는 Stack 이라는 안드로이드 게임인데, 실제 플레이를 해보면 계속해서 육면체 박스가 위로 쌓이기만 한다. 타이밍을 맞춰서 쌓고 가장 높은 위치까지 쌓는 것을 다투는 게임인데, 정말 이름을 따라서 쌓고, 또 쌓기만 한다(안타깝게도 꺼내진 않는다)

 

 이처럼 Stack은 쌓고, 쌓은 걸 빼는 자료구조라고 생각하면 된다.
 또한 범용적으로 쓰이는 용어가 있는데 데이터를 Stack에 넣는 것을 ‘밀어 넣는다’라는 의미로 push. Stack에 쌓인 데이터를 빼는 행위를 ‘꺼내다’라는 의미로 pop 이라고 부른다.

 

 실제로 Stack을 코드로써 구현한 대부분의 API들은 push와 pop이라는 이름의 메서드를 만들어서 Stack에 데이터를 쌓고 데이터를 꺼내는데 활용되도록 가이드하고 있다.

 

 실제 현업에서는 굳이 Stack을 코드로 한땀한땀 작성해서 사용하지는 않는다.

 대학생, 혹은 자료구조를 처음 공부하는 입장에서는 직접 구현해보는 것이 도움이 되겠지만, 이미 C++이나 Java등의 언어에서 기본 적인 자료구조는 클래스 형태로 제공을 하고 있기 때문이다. 거기에 위에서 말한 push, pop 이외에도 size, empty등 Stack을 활용함에 있어서 부가적으로 필요한 정보들을 리턴해주는 메서드들도 제공해주고 있기 때문에 우리는 잘 만들어진 아이들을 잘 사용해주면 된다.

 

 두 언어에 대한 짧은 사용 예시를 아래에 함께 하니 참고하기 바란다.

C++의 경우 #include<stack>

#include<iostream>
#include<stack> 

int main(){
  stack<int> stack;

  stack.push(4);
  stack.push(5);
  stack.push(1);

  cout << stack.size() << endl; // 3
  cout << stack.top() << endl; // 1

  stack.pop();
  cout << stack.size() << endl; // 2
  cout << stack.top() << endl; // 5

}

Java의 경우 import java.util.Stack;

import java.util.Stack;

public class StackExample {
  public static void main(String[] args){
    Stack<Integer> stack = new Stack();

    stack.push(4);
    stack.push(5);
    stack.push(1);

    System.out.println(stack.size()); // 3
    System.out.println(stack.peek()); // 1

    System.out.println(stack.size()); // 3
    System.out.println(stack.pop());  // 1

    System.out.println(stack.size()); // 2
    System.out.println(stack.peek()); // 5

  }
}

 

---

Queue

 와..Stack에 대한 글이 생각보다 길어졌다.

 사실 이렇게 길게 적을 거라곤 생각 안 했는데, 예시 코드와 함께 쓰다보니 좀 길어진 거 같다.

 그럼 이제 Stack 과 늘 함께 설명되는 Queue에 대해 포스팅을 해보겠다.

 

 Stack과 Queue는 둘다 선형 알고리즘이다(물론 Queue의 경우 환형도 있긴하지만)

 

 여기서 말하는 ‘선형’이란.

 데이터를 저장하고 활용하는 방식이 ‘선’을 그은 것과 같은 형태를 띈다고 해서 선형 알고리즘이라고 불리운다. 앞에서 설명한 Stack을 생각해보자. 입구와 출구가 하나인 구덩이를 예시로 들었었다. 그 구덩이도 잘 보면 세로로 세워진 선과 같은 형태이다.

 

 그럼 Queue는 Stack과 무엇이 다를까?

 

 Queue는 FIFO다. First In First Out.

 먼저 들어온 데이터가 먼저 나간다.

 

 즉, 데이터가 들어오는 입구와 출구가 별개다.

 다만, 별개라고 해서 내가 사용하고자 하는 데이터가 중간쯤 들어왔는데 얘부터 먼저 쏙 빼서 사용할 수는 없다. 먼저 들어온 데이터가, 먼저 나가야 하는 것이 Queue의 원칙이자 정의이다.

2014년 영국에서 본 대기열 안내문구

 이 사진은 2014년에 영국 여행을 하며 본 안내문이다.

 당시 관광지에 들어가기 위한 대기줄에 서 있었고 이 안내문을 보고는 단박에 Queue에 대한 깨달음을 얻을 수 있었다늘 코드와 이론으로만 보던 내용을 이렇게 실생활에서 보게 되다니, 신기할 따름이었다(그러고 본능과 같이 눌러버린 카메라 셔터...이제보니 참 공돌이다웠다) 

 

사실상 영어단어로써의 Queue는 이와 같이 무언가를 하기 위해 일렬로 늘어선 사람들로 이루어진 줄을 의미하기도 하는데, 실제로 이렇게 대기줄로 형성된 사람들은 가장 먼저 선 사람이 입장하고 다음 사람이 순번을 이어받게 된다. First In, First Out 의 형태인 것이다.

 

 이와 동일한 예제로 내가 대학생 시절 받았던 Queue관련 과제는 은행의 업무처리 시스템을 개발하는 것이었다. 말해놓고보니 되게 거창한 과제 같은데, 실제 돈을 송금하고 인출하고 하는 은행 시스템을 생각한다면 오산이다. 과제 설명을 조금 하자면 은행원이 3명이 있을 때 각 은행원 별로 능력의 역차가 있어서 하나의 일에 대해 A는 3분, B는 5분, C는 1분이 걸려 일을 처리한다고 가정한다. 거기에 손님들이 9시부터 1분에 한 명씩 입장할 때에 은행에 업무가 종료되는 가장 빠른 시각은 언제인가, 를 구하는 과제였다.

 전형적인 대기열(Queue)문제였는데, 정확치는 않지만 해결하는데 이틀 정도 걸렸던 것 같다

 (이틀 내내 했다는게 아니라..학교가고 밥 먹고 잠자고 놀고 할 거 다 하고…)

 

 물론, Queue 또한 Stack 처럼 잘 작성 된 API들이 존재하므로 특별한 경우가 아니라면, 필요시 가져다 잘 사용해주면 된다. 가장 대표적인 C++과 Java의 예시를 아래에 작성하니 참고바란다.

 

C++의 경우 #include<queue>

#inlcude<iostream>
#include<queue>
using namespace std;

int main(){
  queue<int> q;

  q.push(4);
  q.push(5);
  q.push(1);

  cout << q.size() << endl; // 3
  cout << q.front() << endl; // 4
  cout << q.back() << endl; // 1

  q.pop();
  cout << stack.size() << endl; // 2
  cout << q.front() << endl; // 5
  cout << q.back() << endl; // 1

}

Java의 경우 import java.util.Queue;

import java.util.LinkedList;
import java.util.Queue;

public class StackExample {
  public static void main(String[] args){
    Queue<Integer> q = new LinkedList<Integer>();

    q.offer(4);
    q.offer(5);
    q.offer(1);

    System.out.println(q.size()); // 3
    System.out.println(q.peek()); // 4

    System.out.println(q.size()); // 3
    System.out.println(q.poll());  // 4

    System.out.println(q.size()); // 2
    System.out.println(q.peek()); // 5

  }
}