자료구조 큐, 스택, 덱 (Queue, Stack, Deque)

Queue, Stack, Deque(=Double-ended Queue)

  큐, 스택, 덱은 배열, 리스트와 함께 선형 자료구조에 속하는 자료구조들이다. 사실 큐, 스택, 덱의 모든 기능은 리스트(이하 '리스트'라는 단어는 모두 Linked List를 뜻함)만 사용해서도 시간복잡도 마저 동일하게 동작할 수 있다. 즉, 어찌보면 스택, 큐, 덱은 리스트에 포함되는 자료구조라고 볼 수 있다.

 

  그럼에도 큐, 스택, 덱은 분명 리스트와는 별개의 자료구조로 정의되어 사용되고 있다. 이건 일종의 컨셉, 규칙에 해당한다고 생각한다.

멀티툴 (이미지 출처 : victorinox.com)

  술먹고 있는데 상대방이 갑자기 병따개를 준다. 병따달라는 의도를 바로 파악할 수 있다. 술먹다가 이번엔 상대방이 멀티툴을 갑자기 준다. 물론 멀티툴엔 병따개가 있다. 하지만 난 멀티툴을 받고 '..? 뭐? 어쩌라고?' 라고 생각할 수 밖에 없다. 큐, 스택, 덱은 리스트의 기능 중 일부만을 제한적으로 사용하도록 만들어 예상치 못한 에러가 나지 않도록 동작을 제한하고, 코드의 가독성을 높혀 유지보수가 쉽도록 해준다고 생각한다. 일종의 제한적인 규칙을 만들어 둔 것이라 보면 된다. Simple is best!

 

  물론 리스트는 리스트, 스택은 스택, 큐는 큐라고 할 수도 있다. 하지만 이미 아는 것부터 연관관계를 맺어나가면 뭔가를 이해하기 좋다.

 

PS. 사실 큐, 덱은 doubly linked list로만 구현이 가능하다. 일반적으로 사용되는 언어들에서 구현해둔 리스트는 doubly linked list여서 그냥 위와 같이 말했다. 그리고 리스트 뿐 아니라 배열로도 당연히 동일하게 동작하게 구현할 수 있다. 다만 비효율적이다.

 

 

큐 (Queue)

큐는 FIFO(First in First out; 선입 선출)의 특징을 가지는 자료구조이다. 먼저 들어간 데이터가 먼저 나온다.

  그림으로는 위와 같이 좌우가 뚫려있는 파이프와 같이 표현된다. 좌측으로 넣고, 우측으로 뺀다(한쪽 방향으로 넣고, 다른쪽으로 뺀다). 그럼 넣는 순서는 노랑->보라->파랑이 될 것 이고, 빼는 순서도 마찬가지로 노랑->보라->파랑이 된다.

큐는 이게 끝이다. 아주 간단한 컨셉을 가진 자료구조이다.

 

  이게 끝이면 그럼 중간 자료는 어떻게 볼까? 데이터 수정은 어떻게 할까? enqueue로 방금전에 넣은걸 다시 확인하고 싶은데 어떻게 할까? 전부 못한다. 큐의 컨셉은 이런걸 전부 못하는거다. 단순히 한쪽에서 넣고, 한쪽에서 뺄수만 있도록 제한해둔 것이다.

 

  일반적으로 큐는 아래의 함수만 있으면 된다. (함수명은 사실 명확히 정의된건 없는걸로 알고있다. 이하 스택, 덱도 마찬가지다. 실제로 언어마다 정해둔 함수명이 좀 다르다.). 모든 함수의 시간복잡도는 O(1)이어야 한다.

 

1. enqueue (자바의 경우 add) : 한쪽 방향으로 데이터를 넣는다.

2. dequeue (자바의 경우 poll) : 다른쪽 방향으로 데이터를 뺀다. (여기서 dequeue는 덱(deque)과 다르다. deque는 double-ended queue를 줄인거고, dequeue는 de-(접두어) + queue이다.)

3. peek : dequeue로 빠질 데이터를, 큐에서 제거하진 않고 데이터만 확인한다.

4. isEmpty : 큐가 비었는지

5. size : 큐에 들어있는 데이터 갯수

 

그럼 리스트의 동작 중 어떤걸 제한하면 큐가 될지 직접 만들어보자! 자바에서 LinkedList를 사용해 Queue를 구현해봤다.

import java.util.LinkedList;

public class MyQueue<T> {
    LinkedList<T> list;

    public MyQueue() {
        list = new LinkedList<>();
    }

    public void enqueue(T data) {
        list.addFirst(data);
    }

    public T dequeue() {
        return list.pollLast();
    }

    public T peek() {
        return list.peekLast();
    }
    
    public boolean isEmpty() {
        return list.isEmpty();
    }
    
    public int size() {
        return list.size();
    }
}

  이게 끝이다. 뭐 할게 없다. 리스트에 있는 함수 중 일부만 사용하면 되며, 동작 잘 한다.

자바의 경우 'Queue<Integer> q = new LinkedList<>();' 와 같이 선언해서 사용 가능하다.

파이썬은 따로 큐를 제공하지 않는다. 애초에 파이썬은 배열도 없는 판국에 뭐..(심지어 리스트는 linked list가 아님) 파이썬에서 list는일반적으로 Vector(ArrayList)의 형식으로 동작하므로 dequeue에서 시간복잡도가 너무 높아 비효율적이다. 파이썬은 큐도 이후 설명할 deque(덱)를 사용해야 한다.

C++은 STL에 만들어놨다.

C는 일단 LinkedList부터 기본적으로 제공되지 않으므로 전부 직접 짜야한다.

C로 짜본 Queue : https://github.com/NaHwaSa/C_LanguagePractice/tree/main/queue%20(data%20structure)

 

  그럼 어떨 때 쓸까? 현업에서 쓸만한 예시로는 대표적으로 스케쥴링에 쓰인다. 먼저 들어온 작업을 먼저 처리하도록 하는 것이다.

 

 

스택 (Stack)

스택은 LIFO(Last in First out; 후입 선출)의 특징을 가지는 자료구조이다. 나중에 들어간 데이터가 먼저 나온다.

  그림으로는 위와 같이 표현된다. 상자에 뚜껑 열고 딱 맞는 책을 차곡차곡 쌓는다고 생각하면 이해하기 쉽다. 마지막에 넣은 책이 가장 위에 있으니 가장 먼저 꺼내야 그 아래 책을 꺼낼 수 있다.

 

  큐와 마찬가지로, 중간의 데이터를 볼 수도 없고 수정할수도 없는게 스택의 컨셉이다. (추가로, 스택에서 가장 위에 있는 데이터는 'top'이라고 불린다.)

큐에 필요한 함수는 다음과 같다. 마찬가지로 모든 함수의 시간복잡도는 O(1)이어야 한다.

 

1. push : 스택에 데이터를 넣는다.

2. pop : 스택에서 데이터를 뺀다.

3. peek : 스택에서 데이터를 빼진 않고, 가장 위에 있는 데이터만 확인한다.

4. isEmpty

5. size

 

  마찬가지로 리스트로 쉽게 구현 가능하다. 자바에서 LinkedList로 짜본 스택은 다음과 같다.

import java.util.LinkedList;

public class MyStack<T> {
    LinkedList<T> list;

    public MyStack() {
        list = new LinkedList<>();
    }

    public void push(T data) {
        list.addFirst(data);
    }

    public T pop() {
        return list.pollFirst();
    }

    public T peek() {
        return list.peekFirst();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

    public int size() {
        return list.size();
    }
}

 

자바의 경우 'Stack<Integer> stk = new Stack<>();' 와 같이 선언해서 사용 가능하다.

파이썬은 따로 만들어둔건 없다. 그냥 일반적인 list를 사용해야 한다. (stack = [])

C++은 STL에 만들어놨다.

C는 이번에도 전부 직접 짜야한다.

C로 짜본 Stack : https://github.com/NaHwaSa/C_LanguagePractice/tree/main/stack%20(data%20structure)

 

  어떨 때 쓸까? 현업에서 쓸만한 예시로는 ctrl+z 로 현재 작업중인걸 되돌리는 기능을 들 수 있다. 작업을 하나씩 진행하고 (push), ctrl+z를 누를 때 마다 가장 마지막에 작업한게 하나씩 취소되어야 한다.(pop)

 

  tmi로 그럼 ctrl+y 등으로 방금 취소한걸 다시 되돌리는건 어떻게 할까? 작업중인 스택을 스택1이라 하고 스택2 하나 더 두자. ctrl+z로 스택1에서 pop한걸 스택2에 push하면 된다( 스택2.push(스택1.pop()) ). 그럼 ctrl+y는 스택2에서 다시 pop해서 스택1에 push하면 되며, 작업을 다시 진행하면 이제 ctrl+y는 불가하므로 스택2는 안에 들어있는 데이터와 함께 지워버리면 된다. 이걸 그럼 리스트로 구현해보자. 대강 생각해봐도 복잡하거니와, 그 코드를 처음 본 사람이 설명 없이 로직을 쉽게 이해할 수 있을까?

 

 

덱 (Deque = Double-ended Queue)

  데크라고도 불리는데, 보통 덱이라고 많이 부른다. Double-ended Queue라는 의미로, 양쪽으로 넣고 뺄 수 있는 큐다. 당연히 양쪽으로 넣고 뺄 수 있는 스택으로도 쓸 수 있고, 한쪽은 스택 한쪽은 큐로 써도 된다. 좀 더 유연한 스택, 큐 이다. 하지만 리스트와 다르게 중간의 데이터를 건드릴 수 없고, 양끝단만 건드릴 수 있다. (물론 스택이나 큐나 덱이나 개발자로써 보자면 건드릴려면 어떻게든 건드릴 수 있다. 하지만 해당 자료구조의 컨셉과 룰에 어긋난다. 그렇게 해야한다면 애초에 해당 자료구조를 쓰기에 적합한 설계가 아닌거니깐 그냥 리스트나 배열 쓰자.)

  그림으로 표현하면 큐와 동일하다. 다만 양옆에서 넣고 빼고 할 수 있다.

필요한 함수는 아래와 같다. 마찬가지로 모든 함수의 시간복잡도는 O(1)이어야 한다.

 

1. addFirst : 덱의 한쪽에 데이터 추가

2. pollFirst : 덱의 한쪽에서 데이터 빼기

3. peekFirst : 덱의 한쪽에서 데이터를 빼진 않고 확인만 하기

 

4. addLast : 덱의 다른쪽에 데이터 추가

5. pollLast : 덱의 다른쪽에서 데이터 빼기

6. peekLast : 덱의 다른쪽에서 데이터를 빼진 않고 확인만 하기

 

7. isEmpty

8. size

 

1~3 사용 : 스택1

4~6 사용 : 스택2

1,5,6 사용 : 큐1

4,2,3 사용 : 큐2

 

마찬가지로 리스트로 쉽게 구현 가능하다. 자바에서 LinkedList로 구현한 덱은 다음과 같다.

import java.util.LinkedList;

public class MyDeque<T> {
    LinkedList<T> list;

    public MyDeque() {
        list = new LinkedList<>();
    }

    public void addFirst(T data)    { list.addFirst(data); }
    public T pollFirst()            { return list.pollFirst(); }
    public T peekFirst()            { return list.peekFirst(); }

    public void addLast(T data)     { list.addLast(data); }
    public T pollLast()             { return list.pollLast(); }
    public T peekLast()             { return list.peekLast(); }
    
    public boolean isEmpty()        { return list.isEmpty(); }
    public int size()               { return list.size(); }
}

 

자바의 경우 'Deque<Integer> dq = new LinkedList<>();' 와 같이 선언해서 사용 가능하다.

파이썬은 이번엔 드디어 만들어뒀다. 'from collections import deque' 처럼 import 해서 사용 가능하다.

C++은 STL에 만들어놨다.

C는 이번에도 전부 직접 짜야한다. 이건 안짰다. 함수 많아서 귀찮..

 

  스택, 큐에 비해 좀 더 다양하게 응용해서 사용할 수 있다. 현업에서 쓸만한 예시로는 위 스택의 예시를 이어서 보겠다. 일반적으로 ctrl+z에는 횟수제한이 있다. 무한정 되돌려진다면 메모리가 남아나질 않게되니깐. 근데 아까 스택의 예시에서 갯수를 제한할 수 있을까? 없다. 위로만 넣었다 뺄 수 있으니까 갯수가 설정해둔 갯수를 넘어가도 최근에 한 작업만 제거할 수 있다.

 

  이 때 덱을 사용한다면 addFirst와 pollFirst로 스택처럼 사용하다가, size()를 확인해서 일정 수치가 넘어가면 pollLast로 빼는 식으로 갯수를 제한할 수 있게 된다.