Queue(큐) 와 Stack(스택) using Python

Queue (큐)

큐는 항목을 FIFO(선입 선출)하는 순서로 저장하는 자료구조 입니다.

• 예를 들어 음료수 선입 선출이나 마트에서의 대기열을 생각하시면 됩니다.

해당 이미지를 보게되면 Data6을 Push할 때는 맨뒤로 들어가거 Data1을 Pop할 때는 바로 처음에서 꺼내게 된다

이걸 deque라고 합니다.

- deque란?

• double-ended queue의 줄임말
• 큐에서 양방향으로 데이터를 처리한다는 의미
• double은 자료구조에서 양방향을 의미

from collections import deque
queue = deque(["Eric", "John", "Michael"])
queue.append("Terry")           
queue.append("Graham")

print('queue:', queue)
print('queue.popleft():',queue.popleft())
print('queue.popleft():',queue.popleft())
print('queue:', queue)

# queue: deque(['Eric', 'John', 'Michael', 'Terry', 'Graham'])
# queue.popleft(): Eric
# queue.popleft(): John
# queue: deque(['Michael', 'Terry', 'Graham'])

 

위의 코드는 파이썬으로 리스트 메소드를 활용해 Queue를 만든 것이다.

 

Queue의 Time and Space Complexity (시간, 공간 복작도)

• Enqueue (대기열에 넣기)
  • Data를 Queue에 추가하면 O(1) 시간이 걸린다.
• Dequeue (대기열에서 빼기)
  • Data를 Queue에서 빼면 O(1) 시간이 걸린다.

이제 파이썬을 활용해 Queue를 구현해보겠습니다.

 

# 연결리스트를 이용한 큐 구현
class LinkedListNode:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    # 대기열에서 넣기(큐에 값을 집어넣는 함수)
    def enqueue(self, item):
        new_node = LinkedListNode(item)
        # 큐가 비어있는지 체크
        if self.rear is None:
            self.front = new_node
            self.rear = new_node
        else:
            # 새로운 노드를 rear 다음에 삽입
            self.rear.next = new_node
            # 새로운 노드를 rear 재할당
            self.rear = new_node
        return new_node.data

    # 대기열에서 빼기(큐에서 값을 빼내는 함수)
    def dequeue(self):
        # 큐가 비어있는지 체크
        if self.front is not None:
            # front값을 old front에 삽입
            old_front = self.front
            # old front 다음 값을 front값에 삽입
            self.front = old_front.next

        # 큐가 비어있는지 체크
        if self.front is None:
            # rear를 None으로 지정한다.
            self.rear = None

        return old_front.data
    
    # 연결리스트의 노드출력을 위한 기능
    def ord_desc(self):
        node = self.front
        while node:
            print(node.data)
            node = node.next

위 코드를 보게 되면 연결리스트를 활용해서 Queue를 구현하고 있다.

• 연결리스트는 파이썬에 없는 자료구조로, 사용하려면 직접 클래스로 구현하여 사용하여야 한다. 연결리스트를 구현하고 이해하기 위해서는 해당 자료구조를 많이 사용해 보아야 합니다.
• 그렇기 때문에 연결리스트를 기반으로 큐와 스택 자료구조를 구현하는 연습을 해봄으로써 연결리스트를 좀 더 잘 이해하는 것을 목표로 합니다.

다시 코드로 들어가면 

• enqueue에서는 새로운 노드의 저장공간(변수)를 만들어주고, 그 저장공간에 노드를 넣어주는 개념이다.
• dequeue는 삭제할 노드를 위해 저장공간(변수)를 만들어주고, 그 저장공간에 삭제노드를 넣어주는 개념이다.

q = Queue()
q.enqueue(1)
q.enqueue(2)
q.ord_desc()

# 1
# 2

동작 방식을 간단하게 살펴보면

1. q = Queue()로 빈 Queue를 만들어준다.

 

2-1. q.enqueue(1) 을 통해 new_node = LinkedListNode(item) : item=1을 새로운 값으로 가지는 노드가 만들어진다.

 

2-2. 큐가 비어있는 상태이므로 enqueue 함수의 if 절이 수행된다.

self.rear와 self.front가 new_node를 가리킴으로써 노드가 큐 안으로 들어간다.

 

3-1. q.enqueue(2) 을 통해 new_node = LinkedListNode(item) : item=2를 값으로 가지는 노드가 만들어진다.

 

3-2. 큐가 비어있지 않으므로 enqueue 함수의 else절이 수행된다.

self.rear.next = new_node : 기존 노드에 새 노드를 연결해준다. 이때 새로운 노드는 아직 큐에 들어가지 않은 상태이다.

 

최종적으로 self.rear = new_node : self.rear가 새로운 노드를 가리킴으로써 새로운 노드도 큐에 들어오게 된다.

반대로 Queue에 들어가 있는 데이터를 빼기 위해서는

q.dequeue()
q.ord_desc()

# 2

 

 

위 코드를 적게 되면 data1이 먼저 빠지고 data2 만 남게된다.

 

Stack (스택)

Stack은 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조이다.

Stack은 가장 최근에 Stack에 추가한 Data가 가장 먼저 제거될 Data 이다.

 

List를 활용해서 Stack를 구성하면 다음 코드로 구성할 수 있다.

# 리스트 메소드를 사용해서 스택만들어보기
stack = [3, 4, 5]
stack.append(6)
stack.append(7)
print(stack)

stack.pop()
print(stack)

stack.pop()
print(stack)

stack.pop()
print(stack)

# [3, 4, 5, 6, 7]
# [3, 4, 5, 6]
# [3, 4, 5]
# [3, 4]

이번에는 Queue에서 Class를 활용해서 구성한 것처럼 Stack도 동일하게 구현 할 수 있다.

다만 Stack의 경우에는 Queue와 동작은 유사하시면, 입출력의 순서는 반대이다.

 

class LinkedListNode:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        # 신규 노드 생성
        new_node = LinkedListNode(data)
        # 최상단의 노드를 신규 노드 다음 노드로 삽입
        new_node.next = self.top
        # 신규 노드를 최상단에 삽입
        self.top = new_node
        return new_node.data

    def pop(self):
        # 스택이 비어있는지 확인
        if self.top is not None:
            # 최상단의 노드를 삭제할 노드로 삽입
            popped_node = self.top
            # 삭제할 노드 다음 노드를 최상단의 노드로 삽입
            self.top = popped_node.next
            # 삭제할 노드로부터 값 리턴
            return popped_node.data

    # 연결리스트의 노드출력을 위한 기능
    def ord_desc(self):
        node = self.top
        while node:
            print(node.data)
            node = node.next

s = Stack()

print('1,2,3 차례대로 추가하기:')
s = Stack()
s.push(1)
s.push(2)
s.push(3)
s.ord_desc()

print('대기열에서 빼기:')
s.pop()
s.ord_desc()

# 1,2,3 차례대로 추가하기:
# 3
# 2
# 1
# 대기열에서 빼기:
# 2
# 1

스택(Stack)의 사용 사례

재귀 알고리즘을 사용하는 경우 스택이 유용하다.

 

• 재귀 알고리즘
  • 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
  • 재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다.
• 웹 브라우저 방문기록 (뒤로가기)
• 실행 취소 (undo)
• 역순 문자열 만들기 등등