자료구조 핵심 원리 - 스택과 큐

 

1.1  스택

스택(stack)은 접시 쌓기를 떠올리면 됩니다. 데이터가 들어오면 차곡차곡 쌓이고 나갈 때는 맨 위에 있는 데이터부터 나갑니다. 즉, 맨 마지막에 들어온 데이터가 맨 처음 나가게 되지요. 이를 LIFO(Last In First Out)라고 합니다.

 

 

 

스택의 ADT를 정의한 후 어떻게 객체를 표현하고 연산을 구현할지 고민해 보겠습니다.

 

Stack
- Object
: LIFO 객체

- Operation
1. empty( ) -> Boolean: 스택이 비어 있으면 TRUE, 아니면 FALSE 반환
2. push(data): data를 스택의 맨 위에 삽입
3. pop( ) -> element: 스택의 맨 위에 있는 데이터를 삭제하며 반환
4. peek( ) -> element: 스택의 맨 위에 있는 데이터를 반환만 함

 

 

1.1.1  스택 구현 : 동적 배열을 이용하여 구현하기

파이썬의 자료 구조에는 스택이라는 모듈이 따로 없습니다. 파이썬에서 스택은 리스트를 이용해서 간단하게 사용할 수 있는데 ADT의 push() 대신 리스트의 append()를, ADT의 pop() 대신 리스트의 매개변수 없이 사용하는 pop()을 사용하면 됩니다. push와 pop이 모두 O(1)이므로 매우 합리적입니다. 하지만 아무런 추상화 없이 리스트를 스택으로 사용한다면 가독성은 매우 떨어질 것입니다.

문제를 해결하고자 스택의 내부 표현은 동적 배열로 하고 연산 구현은 리스트의 함수를 래핑(wrapping)하는 방법으로 추상화해 보겠습니다. 

 

# stack.py

class Stack:
    def __init__(self):
        self.container = list()
        
    def empty(self):
        if not self.container:
            return TRUE
        else:
            return FALSE
        
    def push(self, data):
        self.container.append(data)
        
    def pop(self):
        if self.empty():
            return None
        return self.container.pop()
    
    def peek(self):
        if self.empty():
            return None
        return self.container[-1]

 

위의 Stack 클래스 생성자를 보면 self.container = list()를 사용하여 실제 데이터를 담을 객체로 동적 배열을 생성하고 있습니다. 스택 사용 예는 다음과 같습니다. 

 

# stack.py

s = Stack()

s.push(1)
s.push(2)
s.push(3)
s.push(4)

while not s.empty():
    print(s.pop(), end=' ')

 

코드를 실행하면 4 3 2 1이 출력됩니다.

 

 

1.2  큐

큐(queue)는 줄 서기를 떠올리면 됩니다. 줄을 먼저 선 사람이 먼저 입장하게 됩니다. 즉, FIFO (First In First Out)입니다.

 

 

 

위의 그림을 보면 큐의 첫 데이터는 front가 가리키고 있으며, 마지막 데이터는 rear가 가리키고 있습니다. ADT를 기술하고 구현해 보겠습니다.

 

Queue

- Object
: FIFO 객체

- Operation
1. is_empty( ) -> Boolean: 큐가 비어 있으면 TRUE, 아니면 FALSE 반환
2. is_full( ) -> Boolean: 큐가 가득 찼으면 TRUE, 아니면 FALSE 반환
3. enqueue(data): 큐의 맨 뒤에 데이터 삽입
4. dequeue( ) -> element: 큐의 맨 처음 데이터를 삭제하면서 반환
5. peek( ) -> element: 큐의 맨 처음 데이터를 삭제하지 않고 반환만 함

 

 

1.2.1  큐 구현 1 : 동적 배열을 단순하게 사용해서 구현하기

 

# queue.py

class Queue:
    def __init__(self):
        self.container = list()
        
        def empty(self):
            if not self.container:
                return True
            else:
                return False
            
        def enqueue(self, data):
            return self.container.append(data)
        
        def dequeue(self):
            return self.container.pop(0)
        
        def peek(self):
            return self.container[0]

 

파이썬의 동적 배열인 리스트를 이용해서 큐를 구현했습니다. 그런데 문제점이 하나 눈에 띄는군요. 스택에서 push와 pop 연산은 동적 배열의 맨 마지막에서 일어나므로 빅오가 O(1)이었습니다. 반면, 큐에서 enqueue 연산은 rear에 데이터를 추가하므로 스택과 같은 O(1)이지만, dequeue 연산은 동적 배열의 첫 번째 데이터를 삭제한 후 이후 모든 데이터를 한 번씩 옮겨야 하므로 O(n)이 됩니다. 그렇다면 동적 배열의 장점을 충분히 살린 큐는 만들 수 없을까요?

 

 

1.2.2  큐 구현 2 : 원형 큐로 구현하기

원형 큐(circular queue)란 선형으로 이어져 있는 동적 배열을 마지 원형처럼 사용하는 방법입니다.

 

 

dequeue의 문제점은 연산마다 모든 데이터를 한 번씩 이동시킨다는 데에 있었습니다. 즉, 데이터를 모두 이동시키는 것이 아니라 front를 뒤로 한 번만 이동시키면 됩니다. 그럼 이전에 front가 가리키던 데이터는 삭제된 것과 같습니다. 하지만 이 해결책에도 문제점이 하나 있습니다.

 

매번 dequeue 연산을 할 때마다 동적 배열의 앞부분이 하나씩 비게 되고 enqueue 연산은 계속되어 rear가 동적 배열의 맨 마지막에 도달했을 때는 앞부분에 데이터를 저장할 충분한 공간이 있음에도 큐가 가득 찼다고 판단하게 되는 것입니다. 이 문제점은 선형적인 동적 배열을 원형으로 이어 붙이면 해결할 수 있습니다.

 

논리적으로 이렇게 구성하면 rear가 동적 배열의 맨 마지막에 도달했을 때는 동적 배열의 맨 처음을 가리키게 하여 빈 공간에 데이터를 추가하면 되는 것이지요. 원형 큐를 구현하는 한 가지 팁은 원형 큐가 비어 있을 때와 가득 찼을 때를 구분하기 위해 rear를 실제 데이터의 마지막 다음을 가리키게 하는 것입니다.

 

# circular_queue.py

class CQueue:
    MAXSIZE=10
    def __init__(self):
        self.container=[None for _ in range(CQueue.MAXSIZE)]
        self.front=0
        self.rear=0

    def is_empty(self):
        if self.front==self.rear:
            return True
        return False

    def is_full(self):
        next=self.__step_forward(self.rear)
        if next==self.front:
            return True
        return False

    def enqueue(self, data):
        if self.is_full():
            raise Exception("The queue is full")
        self.container[self.rear]=data
        self.rear=self.__step_forward(self.rear)

    def dequeue(self):
        if self.is_empty():
            raise Exception("The queue is empty")
        ret=self.container[self.front]
        self.front=self.__step_forward(self.front)
        return ret

    def peek(self):
        if self.is_empty():
            raise Exception("The queue is empty")
        return self.container[self.front]

    def __step_forward(self, x):
        x+=1
        if x >= CQueue.MAXSIZE:
            x=0
        return x

if __name__ =="__main__":
    cq=CQueue()

    for i in range(8):
        cq.enqueue(i)

    for i in range(5):
        print(cq.dequeue(), end="  ")

    for i in range(8, 14):
        cq.enqueue(i)

    while not cq.is_empty():
        print(cq.dequeue(), end="  ") 

    print()
    for i in range(10):
        print(cq.container[i], end="  ")

 

 

1.3  deque : 스택으로도 큐로도 사용할 수 있는 덱

스택, 큐와 비슷한 자료 구조로 덱이 있습니다. 덱(deque)은 double-ended queue의 약어입니다. 스택은 top이 있는 방향으로만 데이터를 입력하고 출력할 수 있습니다. 큐는 front가 있는 방향으로는 데이터를 출력하고, rear가 있는 방향으로는 데이터를 입력하지요. 한 방향에서 하나의 입출력 연산 중 오직 하나만 가능합니다. 이에 비해 덱은 front와 rear에서 입출력이 모두 가능합니다. 즉, front에서도 데이터 입출력이 가능하고 rear에서도 데이터 입출력이 가능합니다.  ADT를 작성하겠습니다.

 

Deque
- Operation
1. is_empty( ) -> Boolean : 덱이 비어 있으면 TRUE, 아니면 FALSE 반환
2. is_full( ) -> Boolean : 덱이 가득 찼으면 TRUE, 아니면 FALSE 반환
3. insertFront(data) : 덱의 맨 앞에 데이터 삽입
4. insertRear(data) : 덱의 맨 뒤에 데이터 삽입
5. popFront( ) -> element : 덱의 맨 처음 데이터를 삭제하면서 반환
6. popRear( ) -> element : 덱의 맨 마지막 데이터를 삭제하면서 반환
7. peekFront( ) -> element : 덱의 맨 처음 데이터를 삭제하지 않고 반환만 함
8. peekRear( ) -> element : 덱의 맨 마지막 데이터를 삭제하지 않고 반환만 함

 

덱은 어떻게 구현할 수 있을까요? 먼저 원형 큐를 구현할 때 사용한 배열을 원형으로 만드는 방법을 고려해 볼 수 있습니다. 그리고 연결 리스트를 배울 때 알아본 이중 연결 리스트도 떠올릴 수 있겠군요. 결론부터 말하면 두 방법 모두 덱을 구현하는 데 사용할 수 있습니다. 현업에서는 파이썬에서 직접 구현안 deque를 이용합니다. 문서에 나와있는 빅오만 보고도 내부 구현을 유추할 수 있습니다.

 

# deque.py

from collections import deque

print("*" * 20 + "STACK" + "*" * 20)

stack = deque()
for i in range(1, 6):
    stack.append(i)
    print(stack)
    
for i in range(5):
    print(stack.pop())
    

print("*" * 20 + "STACK" + "*" * 20)
queue = deque()
for i in range(1,6):
    queue.append(i)
    print(queue)
    
for i in range(5):
    print(queue.popleft())

 

deque을 임포트합니다. 덱의 메서드 이름을 보면 adt와는 조금 다르지만 충분히 유추할 수 있습니다. 먼저 rear에 데이터를 입력할 때는 append()를 호출합니다. rear에서 데이터를 출력할 때는 pop()을 호출합니다. front에 데이터를 입력할 때는 appendleft()를 호출하고, front에서 데이터를 출력할 때는 popleft()를 호출합니다. 리스트와 사용법이 비슷하기 때문에 쉽게 쓸 수 있습니다.

 

파이썬의 덱은 어떻게 구현되어 있는지 유추해 봅시다. 파이썬 공식 문서를 확인하면 deque 파트에 다음 문장이 있습니다.

“Indexed access is O(1) at both ends but slows to O(n) in the middle.”

“인덱스로 양 끝에 접근할 때는 빅오가 O(1)이지만 중간에 있는 데이터에 접근하려면 조금 느려서 빅오가 O(n)이다.”라고 쓰여 있습니다. 동적 배열의 인덱싱은 빅오가 O(1)이고, 연결 리스트에서 데이터에 접근할 때는 모든 노드를 순회해야 하므로 빅오가 O(n)인 것을 이미 알고 있지요. 이 문장으로 파이썬의 덱은 이중 연결 리스트를 이용하여 구현했음을 유추할 수 있습니다. 실제로 소스 코드를 직접 확인하지 않아도 스택 오버플로나 다른 문서를 보면 파이썬의 덱이 이중 연결 리스트를 이용해서 구현했다는 것을 확인할 수 있습니다.

 

(출처 : 파이썬으로 배우는 자료 구조 핵심 원리)