[자료구조] Python으로 구현하는 자료구조 (2) Stack & Queue

이번에는 스택과 큐에 관련된 내용을 정리하였다.

출처 : 프로그래머스 어서와! 자료구조와 알고리즘은 처음이지?

이번 장에서는, 스택의 응용인 연산자 관련 내용은 별도로 알고리즘 파트로 정리하고 스택과 큐의 구현부터 정리한다.

Stack이란?

Stack은 바닥이 막혀있는 항아리 형 구조라고 생각하면 편하다. 즉, 마지막에 들어온 것이 가장 먼저 빠져 나오는 구조이다. (Last in, First out) 형태의 구조이다.

Stack에서 사용할 수 있는 연산들은 다음과 같다.

1. Stack의 길이를 반환하는 연산 : size
2. Stack이 비어있는지 확인하는 연산 : isEmpty
3. Stack에 원소를 넣는 연산 : push
4. Stack에 원소를 제거하는 연산 : pop (물론 비어있으면 Underflow 처리를 하긴 해야한다.)
5. Stack의 최상단의 원소를 확인하는 연산 : peek

pop과 peek의 가장 큰 차이는, pop은 최상단의 원소를 없애기까지 하고, peek은 확인만 한다는 것이다.

이 Stack을 리스트로도 구현이 가능하고, (1)장에서 본, doubly linked list를 통해 구현할 수 있다.
Stack은 List로도 충분히 사용 가능하므로, List를 사용한 Stack의 구현을 확인해보자.

class ArrayStack:

	def __init__(self):
		self.data = []

	def size(self):
		return len(self.data)

	def isEmpty(self):
		return self.size() == 0

	def push(self, item):
		self.data.append(item)

	def pop(self):
		return self.data.pop()

	def peek(self):
		return self.data[-1]

 

Queue란?

Stack와 Queue는 비슷해보이나 결정적 차이가 존재하는데, 어떤 원소가 제거되느냐에 달려있다. Queue의 경우는 먼저 들어온 원소가 먼저 제거되는 형태인 (First in, First Out) 구조이다.

Queue에는 다양한 종류가 존재하는데

- Queue

- Circular Queue (원형 큐)

- Priority Queue (우선순위 큐)

크게 3가지를 예시로 들 수 있다.

 

필요 연산

각 큐별로 어떤 차이점이 있는지, 구현의 예시를 보기 전에, 어떤 연산이 필요한지 확인해보고자 한다.

1. Queue의 길이를 반환하는 연산 : size
2. Queue가 비어있는지 확인하는 연산 : isEmpty
3. Queue에 원소를 넣는 연산 : enqueue
4. Queue에 원소를 제거하는 연산 : dequeue (물론 비어있으면 Underflow 처리를 하긴 해야한다.)
5. Queue의 최초 원소를 확인하는 연산 : peek

명칭만 바뀌어있지, 사용하는 연산은 동일하다.

 

Queue

큐도 스택처럼 리스트로 구현하고 싶으나, 리스트의 경우 아쉬운 점이 몇가지 존재한다.
큐 내에 최대 몇개의 원소가 들어올지 어떻게 아는가? 또한 원소가 삭제되면 index를 다시 조정해야 하는데 이는 너무 번거롭기도 하고 자원 낭비이다. 따라서 Queue의 경우는  Doubly Linked List로 구현하는 것이 현명하다.

class LinkedListQueue:

    def __init__(self):
        self.data = DoublyLinkedList()
    
    def size(self):
        return self.data.nodeCount

    def isEmpty(self):
        return self.data.nodeCount == 0

    def enqueue(self, item):
        node = Node(item)
        self.data.insertAt(self.size()+1, node)

    def dequeue(self):
        return self.data.popAt(1)

    def peek(self):
        return self.data.head.next.data

 

Circular Queue

환형 큐의 경우는 리스트의 전체 크기를 제한하고, 순환 형태로 자원을 관리하게 된다. 이 경우, Queue를 별도로 재정의해야 하는데, 순환 형태로 돌기 위해서는 시작점, 끝점이 필요하다. 입력을 받은 포인터를 rear, 출력 전 지점을 가리키는 포인터를 front라 정의하자.

구현에서는, 우선적으로 선형 리스트를 활용해야 할 것이다. 전체 크기가 제한되어 있으므로, 큐가 모두 차있는지를 판단하는 연산이 추가로 필요하다. 이를 바탕으로 먼저 Circular Queue부터 재정의하자.

class CircularQueue:

    def __init__(self, n):
        self.maxCount = n
        self.data = [None] * n
        self.count = 0
        self.front = -1
        self.rear = -1

front 와 rear의 초기값은 -1이다. 입력이 시작되면 rear가 전진하면 될 것이고, 제거가 시작되면 front가 전진하면 초기 설정에 편리하기에 초기값은 -1로 설정한다. 이를 바탕으로 구현한 연산은 다음과 같다.

def size(self):
    return self.count

def isEmpty(self):
    return self.count == 0

def isFull(self):
    return self.count == self.maxCount

def enqueue(self, x):
    if self.isFull():
        raise IndexError('Queue full')
    self.rear = (self.rear + 1) % self.maxCount

    self.data[self.rear] = x
    self.count += 1

def dequeue(self):
    if self.isEmpty():
        raise IndexError('Queue empty')
    self.front = (self.front + 1) % self.maxCount

    x = self.data[self.front]

    self.count -= 1
    return x

def peek(self):
    if self.isEmpty():
        raise IndexError('Queue empty')
    return self.data[(self.front + 1) % self.maxCount]

Remark> self.isEmpty()대신에, self.rear == self.front를 써도 무방해 보이나 리스트가 전부 차 있는 경우와 비어있는 경우를 구분할수가 없음에 주의하자.

 

Priority Queue

해당 Queue의 구현은 트리로 하는 것이 더 간편하다고 하여, 트리를 배운 후에 구현을 배우면 실제 예시로 보기로 하고, 개념만 확인한다.

Priority Queue의 경우는 dequeue 조건에 우선순위를 부여하는 것이다. dequeue마다 우선순위를 판별하면 전체 queue를 항상 검토해야 하므로, Enqueue 시점에서부터 우선순위대로 queue를 정리하는 방법을 사용한다.