Stack과 Queue

스택과 큐는 많은 알고리즘에서 이용되는 기본적인 자료구조입니다.
그렇다면 스택과 큐는 무엇일까요?

스택
가장 최근에 삽입된 데이터가 가장 먼저 삭제 되는 Last-In-First-Out원칙을 따르는 자료구조

큐
가장 먼저 삽입된 데이터가 가장 먼저 삭제 되는 First-In-First-Out원칙을 따르는 자료구조

그러면 스택과 큐는 어떤 곳에 사용되고 있을까요?

스택은 되돌리기(ctrl+Z), 브라우저 뒤로가기, 괄호 짝 맞추기, DFS(그래프 탐색)등에 이용될 수 있습니다.
큐는 문서 인쇄 순서, 분산 시스템에서의 순서대로 스케줄 처리, BFS(그래프 탐색)등에 이용 될 수 있습니다.

스택과 큐 깊게 파고들기

스택은 배열을 이용하여 구현할 수 있습니다.

• 배열은 연속된 메모리 공간에 데이터를 저장할 수 있는 자료구조로
• 스택에서는 배열의 인덱스를 이용해 스택 포인터를 관리합니다.
• 스택 포인터는 push연산으로 데이터를 삽입할 때마다 증가하고, pop연산으로 데이터를 삭제할 때마다 감소합니다.

class Stack:
    def __init__(self):
        self.stack = []  # 스택의 배열
        self.top = -1    # 스택 포인터, 초기값은 -1

    def push(self, x):
        self.stack.append(x)  # 스택에 x를 삽입
        self.top += 1         # 스택 포인터를 증가시킴

    def pop(self):
        if self.top == -1:    # 스택이 비어있는 경우
            print("Error: Stack Underflow")
            return
        self.stack.pop()     # 스택의 가장 위에 있는 데이터를 삭제
        self.top -= 1        # 스택 포인터를 감소시킴

    def peek(self):
        if self.top == -1:    # 스택이 비어있는 경우
            print("Error: Stack is empty")
            return -1
        return self.stack[self.top]  # 스택의 가장 위에 있는 데이터 반환

    def isEmpty(self):
        return (self.top == -1)  # 스택이 비어있는지 확인

    def size(self):
        return (self.top + 1)    # 스택의 크기 반환

큐는 배열 혹은 연결 리스트를 이용하여 구현할 수 있습니다.

• 배열을 이용하여 구현하는 경우, 일반적으로 원형 큐(Circular Queue)를 사용합니다.
• 원형 큐는 배열의 처음과 끝을 연결하여 원형으로 만든 자료구조로, 큐가 가득 차거나 빌 경우 인덱스를 처음으로 되돌릴 수 있어 배열의 공간을 더 효율적으로 활용할 수 있습니다.
• 연결리스트를 이용하여 구현하는 경우, 일반적으로 단일 연결 리스트(Singly Linked List)를 이용합니다.
• 단일 연결 리스트는 각 노드가 다음 노드를 가리키는 구조를 가진 연결 리스트로 삽입과 삭제가 간편하나, 특정 노드에 접근 위해 처음부터 순회해야 하는 특징이 있습니다.

배열을 이용하여 큐 구현

class CircularQueue:
    def __init__(self, k: int):
        self.size = k     # 큐의 크기
        self.queue = [None] * k  # 큐의 배열
        self.head = -1    # 큐의 맨 앞 인덱스
        self.tail = -1    # 큐의 맨 뒤 인덱스

    def enqueue(self, value: int) -> bool:
        if self.isFull():  # 큐가 가득 찬 경우
            return False
        if self.isEmpty():  # 큐가 비어있는 경우
            self.head = 0
        self.tail = (self.tail + 1) % self.size  # 다음 인덱스로 이동
        self.queue[self.tail] = value           # 데이터 삽입
        return True

    def dequeue(self) -> bool:
        if self.isEmpty():  # 큐가 비어있는 경우
            return False
        if self.head == self.tail:  # 큐에 데이터가 하나만 있는 경우
            self.head, self.tail = -1, -1
        else:
            self.head = (self.head + 1) % self.size  # 다음 인덱스로 이동
        return True

    def front(self) -> int:
        if self.isEmpty():  # 큐가 비어있는 경우
            return -1
        return self.queue[self.head]

    def rear(self) -> int:
        if self.isEmpty():  # 큐가 비어있는 경우
            return -1
        return self.queue[self.tail]

    def isEmpty(self) -> bool:
        return self.head == -1 and self.tail == -1

    def isFull(self) -> bool:
        return (self.tail + 1) % self.size == self.head

연결 리스트를 이용하여 큐 구현

class Node:
    def __init__(self, value):
        self.val = value
        self.next = None

class Queue:
    def __init__(self):
        self.head = None  # 큐의 맨 앞 노드
        self.tail = None  # 큐의 맨 뒤 노드

    def enqueue(self, value):
        new_node = Node(value)
        if self.isEmpty():   # 큐가 비어있는 경우
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

    def dequeue(self):
        if self.isEmpty():   # 큐가 비어있는 경우
            return False
        self.head = self.head

스택을 이용해 큐를 구현하기

그렇다면, 스택을 이용해 큐를 어떻게 구현할 수 있을까요?
후입 선출구조를 이용해 선입 선출을 충족하기 위해서는 다음 과정을 거치게 됩니다.

1. 스택을 2개(입력 스택, 출력 스택) 준비합니다.
2. Push의 경우, 입력 스택에 입력된 데이터를 저장합니다.
3. Pop의 경우, 출력 스택이 비어 있다면 입력 스택의 자료를 모두 pop해 넘겨준 후 맨 앞 자료를 출력합니다.

class QueueImplementedByStack:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def pop(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

    def push(self, num):
        self.stack1.append(num)

큐를 이용해 스택 구현하기

이번에는 큐를 이용해 스택을 구현해 보겠습니다.
과정은 다음과 같습니다.

1. 큐를 2개 준비합니다. 각각 번갈아가면서 현재 큐와 서브 큐가 됩니다.
2. Push의 경우 현재 입력 가능한 큐에 데이터를 추가합니다.
3. Pop의 경우 현재 입력 가능한 큐에 저장된 데이터를 하나만 남기고 모두 서브 큐로 넘긴 후, 마지막 하나를 출력합니다.

from collections import deque

class StackImplementedByQueue:
    def __init__(self):
        self.queue1 = deque()
        self.queue2 = deque()
        self.queue_tuple = (self.queue1, self.queue2)  # 첫번째 queue가 현재 입력 가능한 queue

    def pop(self):
        current_queue = self.queue_tuple[0]
        sub_queue = self.queue_tuple[1]
        while len(current_queue) > 1:
            sub_queue.append(current_queue.popleft())
        self.queue_tuple = (sub_queue, current_queue)
        return current_queue.popleft()

    def push(self, num):
        self.queue_tuple[0].append(num)