[자료구조] 스택, 큐, 덱

[자료구조] 스택, 큐, 덱

 

들어가며.

스택, 큐, 덱은 알고리즘이라기 보다는 data를 관리하는 구조라고 할 수 있다. 스택, 큐, 덱을 활용한 알고리즘이 BFS, DFS 등등이 되는 것이다.

 

비유를 하자면, 우리가 운동할 때 힘(input)을 들여 수축과 이완(자료구조)을 통해 어떤 자세(알고리즘)를 반복 수행해서 근육을 얻고 지방을 태우는(Output) 과정을 수행하는 것에 비유를 할 수 있겠다. 

 

운동은 굽히고 펴는 것부터 시작한다. 이처럼 기본적인 것이 자료구조이며, 이를 잘 알고 이에 대한 특성을 잘 활용할 때 좋은 알고리즘을 통해 뛰어난 프로그램을 만들 수 있는 것이다.

 

 

 

1. 기본적인 개념

배열(Array)  vs  리스트(list)

가장 기본이 되는 순차적(sequential) 자료 구조이다. 모든 자료구조에서 가장 기본이 되는 내용이다.

index로 임의의 원소에 접근할 수 있는 공통점을 가지고 있다.

또한 읽기, 쓰기, 삽입, 삭제 등의 연산이 가능하다. 

 

 

 

* 배열과 리스트의 차이

 

파이썬으로 알고리즘을 연습하고 있다면, 배열이 리스트가 아닌가 하는 생각을 할 수 있다. java를 약간 맛보기로만 배우고 python으로 알고리즘을 공부하고 있는 나도 그러했다. 그렇지만, 컴퓨터에서 두 자료구조를 어떻게 대하는 지를 보면 많이 다르다는 것을 느낄 수 있다.

 

배열 :

- 메모리에 순차적으로 저장되어 있는 어떤 원소를 주소를 통해 읽고 쓰는 것

- 용량이 자동조절 되지 않는다.

리스트 :

- 메모리에 산개해있는 특정 원소를 가르키는 주소를 저장하는 곳

- 용량이 자동조절 된다.

 

A_list = [1, 2, 3, 4] 를 하면, 자료구조를 배우기 이전에 나는 그냥 컴퓨터 어딘가에 자료를 저장할 수 있는 공간이 생기는데, 코드 처럼 대괄호로 묶여있는 방이 있고 그곳에 숫자가 하나씩 저장된다고 생각했다. 그렇지만, 배열이든 리스트든, 숫자 자체가 저장되어 있는 것이 아니라 주소값이 저장되어 있다는 사실을 새로 알았다.

 

배열은 데이터를 저장하고 있는 공간의 주소값을 index로 활용하여 읽고, 쓰고, 삽입, 삭제하는 기능을 가지고 있다. 반면, 리스트는 한 공간안에 데이터가 저장되어 있는 것이 아니라, 마치 작대기 게임으로 호감을 표시하는 것처럼 그 숫자를 가리키는 주소값을 저장하고 있다. index로 그 원소를 호출하면, list 안의 주소값이 가리키는 숫자를 반환하는 차이점이 있는 것이다. 

 

이 주소값을 활용하기 때문에 A_list[0]과 같은 읽고 쓰기하는 것들이 '상수 시간'에 처리가 가능하다. list 전부를 읽어서 그것에 맞는 것을 찾아오는 것이 아니라, 주소값과 인덱스가 매치되어 그 부분을 바로 읽어오기 때문이다. 

 

용량 조절 부분에서도 차이가 있는데, 메모리 할당변수를 주어야 하는 배열(데이터를 저장하는 공간의 크기)을 할당해야 하기 때문에 쉽게 변경할 수 없는 것이고, list의 경우에는 데이터 자체가 저장되는 공간이 아니기 때문에 자유롭게 조절이 가능한 것이다.

 

 

2. 스택, 큐, 덱

배열, 리스트를 활용한 것이 바로 스택이다. 배열과 리스트를 활용해서 선입선출만 가능한 자료, 후입선출이 가능한 자료 구조를 만들 수 있는 것이다. 스택, 큐는 제한적인 접근(삽입과 삭제 등)만 허용한다. 

 

각각의 자료구조는 특별한 규칙들이 있다. 아래에서 살펴보겠다.

 

 

(1) 스택 자료구조

먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다. 입구와 출구가 동일한 형태의 리스트를 생각하면 되겠다.

박스 쌓기 예시가 좋은 예이다. 인터넷에서는 뒤로가기 버튼, 실행 취소의 로직에 사용됨.

 

파이썬에서는 리스트로 스택을 구현할 수 있다.

class Stack:
    def __init__(self):   # 객체 생성
        self.items = []   # 데이터 저장을 위한 리스트 준비
    
    def push(self, val):
        self.items.append(val)
    
    def pop(self):
        try:
            return self.items.pop() # pop할 아이템이 없으면
        except IndexError: # indexerror 발생
            print("stack empty")
    
    def top(self):
        try:
            return self.items[-1]
        except IndexError:
            print("stack empty")

    def __len__(self):
        return len(self.items)

S = Stack()  ## 클래스 이름으로 S를 인스턴스화 함
## init이 자동으로 생성함수로 불러와짐
# items라는 곳에 데이터를 저장할 것.

이러한 코드로 스택을 구현해볼 수 있다.

list 클래스의 append() 메소드를 활용해서 push를 구현한다.

 

 

 

스택 자료구조는 다음과 같은 알고리즘을 푸는 데 기본이 된다.

 

2022.04.25 - [프로그래밍/Baekjoon Online Judge(BOJ)] - [백준] 9012 괄호 python 알고리즘 문제

[백준] 9012 괄호 python 알고리즘 문제

 

 

 

++ 스택을 쌓아서 거꾸로 출력하고 싶다면?

: [::-1] => 최상단의 원소부터 출력할 수 있게함

 

 

 

 

(2) 큐 자료구조

 

 

 

먼저 들어온 데이터가 먼저 나가는 형식(선입선출)이다. 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 할 수 있다.

정말 많이 볼 수 있는데, 명절 티켓팅 때의 대기열과 같은 것을 생각하면 쉽겠다.

 

파이썬으로 큐를 구현할 수 있다.

Class Queue:
    def __init__(self):
        self.items = [] # 빈 리스트
        self.front_index = 0
    
    def enqueue(self, val):
        self.items.append(val)
    
    def dequeue(self):
        if self.front_index == len(self.items):
            print('Q is empty')
        else:
            x = self.items[front_index]
            self.front_index += 1
            return x

리스트 왼쪽을 출구로 쓰는 방법이다. dequeue 메소드는 front_index를 하나씩 올려가는 것을 통해 리스트 안에 원소는 있지만, 처음의 인덱스를 그 다음 원소로 해서 없는 것처럼 만들어버리는 것이다. 이렇게 큐를 구현할 수 있다.

 

큐를 사용하는 예는 다음과 같다.

 

2022.04.24 - [프로그래밍/Baekjoon Online Judge(BOJ)] - [백준] 11866 요세푸스 문제 0 python 알고리즘 문제

[백준] 11866 요세푸스 문제 0 python 알고리즘 문제

 

그렇지만, 파이썬을 통해 문제를 풀거나 하면, 더 강력한 라이브러리가 있다.

from collections import deque 라이브러리가 그것인데, 이는 후술할 덱의 성질을 그대로 가지고 있다.

 

 

(3) 덱

앞으로도 들어오고 나가는 것도 가능하다.

queue = deque()를 하여 queue를 인스턴스로 만들면,

 

파이썬으로는 deque 클래스만 들여와서 써보기만 했기 때문에 코드는 따로 없다.

 

queue.append(x) / queue.popleft() 등을 할 수 있다.

오른쪽에서도 쌓고, 왼쪽에서도 쌓으며, 오른쪽으로 나갈 수도 있고, 왼쪽으로도 나갈 수 있다.

 

데이터들을 앞뒤로 자유롭게 관리할 수 있어서 용이하다.

코딩테스트에서는 큐 문제도 시간복잡도를 고려하여 deque를 사용하는 것이 리스트 사용하는 것보다 더 효율적이라고 할 수 있다.