파이썬 자료구조와 알고리즘 - 추상 데이터 타입 (스택, 큐, 데크)

CH7 추상 데이터 타입

추상 데이터 타입(ADT)는 어떠한 자료구조의 클래스에 대한 수학적 모델을 가리킨다

자료구조는 배열 기반의 연속 방식, 포인터 기반의 연결 방식으로 크게 나누어진다. 파이썬에서 연속적으로 할당된 자료구조는 문자열, 리스트, 튜플, 딕셔너리 등이 있다.

스택

• 스택은 배열의 끝에서만 데이터에 접근할 수 있는 선형 자료구조이다.

• 배열 인덱스 접근이 제한되어야 한다.

• LIFO(후입선출) 구조이다.

• 스택은 깊이 우선 탐색(DFS)에서 유용하게 사용된다.

스택의 동작

• 가장 중요한 동작으로는 push 와 pop 이 있다. 각각의 동작은 데이터 삽입, 데이터 추출에 해당한다.

스택 구현

파이썬에서는 list 자료형으로 구현할 수 있다.

class Stack:
    def __init__(self):
        self.items = []
    
    # 데이터 삽입
    def push(self, value):
        self.items.append(value)
    
    # 데이터 추출
    def pop(self):
        if self.items:
            value = self.items[-1]
            del(self.items[-1])
            return value
        else:
            print('Stack is empty!')
    
    # 스택의 top을 알려준다
    def top(self):
        if self.items:
            return self.items[-1]
        else:
            print('Stack is empty!')
    
    # 스택의 size를 알려준다
    def size(self):
        return len(self.items)
    
    def __repr__(self):
        return repr(self.items)

값과 pointer를 가지고 있는 Node class를 생성해서, 연결 리스트처럼 구현할 수도 있다.

class Node:
    # node는 value와 자기 자신의 바로 아래 있는 Node를 가리키는 pointer로 구성된다
    def __init__(self, value=None, pointer=None):
        self.value = value
        self.pointer = pointer
        
class Stack:
    def __init__(self):
        self.head = None
    
    # Node를 만들고, head에 추가한 다음 Node의 pointer에 추가하기 전 head에 있던 Node를 연결시켜 준다
    def push(self, value):
        self.head = Node(value, self.head)
    
    def pop(self):
        if self.head:
            value = self.head.value
            self.head = self.head.pointer
            return value
        else:
            print("Stack is empty!")
    
    # 연결되어 있는 Node를 탐색하면서 pointer가 None인 마지막 Node까지 출력
    def printStack(self):
        top = self.head
        if top is None:
            print("Stack is empty!")
        while top:
            print(top.value, end=' ')
            top = top.pointer

큐

• 큐는 항목이 들어온 순서대로 접근 가능하다. 즉, FIFO(선입선출) 구조이다.

큐의 동작

• 큐의 동작은 크게 enqueue와 dequeue 가 있다. 각각 맨 뒤쪽에 데이터 삽입, 맨 앞의 데이터 추출 을 수행하는 동작이다.

큐 구현

• 파이썬 list 자료형과 insert() 메서드를 이용하여 구현할 수 있다

class Queue:
    def __init__(self):
        self.items = []
    
    # 데이터 추가, 리스트의 맨 앞쪽에 추가한다
    def enqueue(self, value):
        self.items.insert(0, value)
    
    # 데이터 추출, 처음에 들어온 데이터부터 추출
    def dequeue(self):
        if self.items:
            value = self.items[-1]
            del(self.items[-1])
            return value
        else:
            print("queue is empty!!")
            
    def size(self):
        return len(self.items)
            
    def __repr__(self):
        return repr(self.items)

• 리스트의 insert() 메서드는 O(n)의 시간 복잡도를 가진다. 참조

2개의 리스트를 사용하면 더 효율적인 큐 구현이 가능하다.

class Queue:
    def __init__(self):
        self.in_items = []
        self.out_items = []
    
    def _transfer(self):
        while self.in_items:
            self.out_items.append(self.in_items.pop())
    
    def enqueue(self, value):
        self.in_items.append(value)
    
    def dequeue(self):
        if not self.out_items:
            self._transfer()
        if self.out_items:
            return self.out_items.pop()
        else:
            print("queue in empty!")
            
    def __repr__(self):
        if not self.out_items:
            self._transfer()
        if self.out_items:
            return repr(self.out_items)
        else:
            print("queue in empty!")

• 스택에서 구현한 것 처럼 Node class 를 구현하여 구현할 수도 있다. 스택과 다른 점은 head와 tail 두가지를 추가해 리스트의 시작과 끝을 가리키게 하면 구현할 수 있다.

데크

• 데크는 큐와 스택의 혼합형이라고 할 수 있다. 양쪽 끝에서 데이터의 추가, 삭제가 가능해야 한다.
• 구현은 위의 Queue 구현에서 enqueue_back, dequeue_front 만 추가하면 구현할 수 있다.

파이썬 Deque 모듈

• 파이썬의 collections 패키지에는 구현되어 있는 deque 모듈이 있다. 이것을 사용하면 더 효율적으로 사용할 수 있다.