스택 및 큐

개요

스택(Stacks) 및 큐(queues)는 엘리먼트를 추가하고 제거할 수 있는 순서를 지정하는 컴퓨터 공학의 일반적인 데이터 구조입니다. 스택과 큐를 사용하면 데이터와 상호작용하는 순서를 다음과 같이 제어할 수 있습니다.

• 스택: 선입후출(first-in, last-out, FILO) 순서로 엘리먼트를 삽입 및 제거하는 컨테이너입니다. 읽을 책 더미 맨 위에서 책을 선택하는 것이 이에 해당합니다.

• 큐: 선입선출(first-in, first-out, FIFO) 순서로 엘리먼트를 삽입 및 제거하는 컨테이너입니다. 식사를 기다리는 고객의 줄을 처리하는 것이 이에 해당합니다.

스택 및 큐는 기본 코드가 유사하지만 저마다 주요 차이점과 강점이 존재하며, 이를 활용하면 빠르고 효율적이며 직관적인 경험을 제작할 수 있습니다.

스택

스택은 쌓여 있는 팬케이크 더미라고 생각하면 됩니다. 아침 식사를 하러 식당에 갔는데, 웨이터가 무한히 쌓여 있는 팬케이크 더미를 준다고 가정해 보세요. 여러분은 예의를 차리기 위해 한 번에 팬케이크 하나씩, 더미 맨 위에 있는 팬케이크만 가져가기로 합니다. 여러분은 웨이터에게 더미 맨 위로 새 팬케이크를 푸시(push)해 달라고 부탁하고, 배고파지면 더미 맨 위에서 팬케이크를 팝핑(pop)해서 접시에 놓고 먹을 수 있습니다. 더미 중간에 있는 특정 팬케이크를 먹고 싶다면, 원하는 팬케이크에 도달할 때까지 맨 위에서부터 계속해서 팬케이크를 먹어야 합니다. 맨 처음에 추가한 팬케이크는 가장 나중에 제거됩니다. 따라서 스택은 FILO, 즉 선입후출 데이터 구조라고 할 수 있습니다.

사용 시점

스택은 이벤트를 수행한 순서를 기억하는 능력, 즉 백트래킹이 필요할 때 유용합니다. 이는 실행 취소 기능, 이벤트 체인, 일련의 선택 등에 적용할 수 있습니다. 예를 들어, 여러 갈래의 경로가 있는 미로를 풀어야 하는 로봇이 있다고 가정해 보겠습니다. 미로에서 갈림길을 만나면 로봇은 경로를 선택하고 해당 선택을 스택에 푸시합니다. 막다른 길에 다다르면 로봇은 스택을 백트래킹하여 취할 수 있는 새 경로를 찾을 때까지 선택을 팝핑합니다.

Verse 구현

Verse API에는 기본으로 제공되는 스택 구현이 없지만, 직접 생성할 수 있습니다.

배열이나 연결된 목록 등 모든 순서의 데이터 구조를 사용하는 스택의 엘리먼트를 구현할 수 있습니다. 이 예시에서는 스택 상단에 쉽게 액세스할 수 있도록 배열을 사용하겠습니다.

stack<public>(t:type) := class:
    Elements<internal>:[]t = array{}

Elements 배열은 타입 t인 스택에 오브젝트를 저장합니다. 즉, 이는 int, float, stack 등 어떤 타입의 엘리먼트로도 스택을 초기화할 수 있다는 뜻입니다. type을 스택 클래스의 실행인자로 사용하는 것은 [파라미터 타입](parametric-types-in-verse)의 예시입니다.

몇 가지 헬퍼 함수를 먼저 정의해 보겠습니다. 엘리먼트의 Push() 및 Pop()을 수행할 수 있도록 스택 상단이 어디인지 알아야 합니다. 스택 상단을 파악하려면 Size(), IsEmpty(), Peek()이라는 3가지 함수가 필요합니다.

# Returns the size of the stack.
    Size<public>()<transacts>:int=
        Elements.Length

    # Succeeds if the stack is empty.
    IsEmpty<public>()<decides><transacts>:void=
        Size() = 0

    # Returns the top element of the stack.
    Peek<public>()<decides><transacts>:t=

Size() 함수는 단순히 Elements 배열의 Length를 반환합니다. IsEmpty() 함수는 Size() 함수를 호출하며, Size()가 0과 같지 않을 경우 실패하는 <transacts> 지정자를 가지고 있습니다.

Peek() 함수는 엘리먼트 배열의 상단(Length - 1) 인덱스에서 엘리먼트를 반환합니다. 배열이 비어 있을 경우 배열 액세스에 실패할 수 있으므로, 이 함수는 <decides><transacts> 지정자를 가집니다.

스택을 인스턴스화하기 위해 생성자 함수를 사용할 수 있습니다. 생성자는 관련 클래스의 인스턴스를 생성하는 특수 함수입니다. 생성자는 오브젝트의 초기 값을 설정하고 Elements의 값에 액세스하여 엘리먼트의 초기 배열에 할당하도록 허용합니다.

# Creates and returns a stack from an initial array of elements InitialElements.
CreateStack<public><constructor>(InitialElements:[]t where t:type) := stack(t):
    Elements := InitialElements

푸시 및 팝

스택에 엘리먼트를 추가하거나 스택에서 엘리먼트를 제거하려면, 스택 상단에 새 엘리먼트를 push하거나 상단에서 pop해야 합니다.

# Adds NewElement to the top of the stack by returning a new
# stack with NewElement as the top
Push<public>(NewElement:t):stack(t)=
    stack(t){Elements := Elements + array{NewElement}}

# Removes the element on top of the stack and returns a tuple of both a new
# stack with the top element removed and the removed element.
Pop<public>()<decides><transacts>:tuple(stack(t),t)=
    FirstElement := Peek[]
    (stack(t){Elements := Elements.RemoveElement[Elements.Length - 1]}, FirstElement)

Push() 함수는 스택 상단에 넣고 싶은 엘리먼트를 취하여 해당 엘리먼트가 상단에 있는 새 스택을 반환합니다. 현재의 스택을 수정하는 것이 아니라 새 스택을 반환하는 것은 함수 프로그래밍의 예시로, 부작용의 위험을 줄여 줍니다.

Pop() 함수를 구현하려면, 먼저 Peek()를 사용하여 스택 상단의 엘리먼트를 찾아야 합니다. 그런 다음 (RemoveElement[] 함수를 사용하여) 상단에서 엘리먼트를 제거하고, 또한 해당 엘리먼트가 없는 새 스택을 반환해야 합니다. 튜플을 사용하여 새 스택과 제거된 엘리먼트를 동시에 반환할 수 있습니다. 배열 액세스의 실패 가능 표현식과 Peek() 호출로 인해, Pop()은 <decides><transacts> 지정자를 가져야 합니다.

완성된 코드

스택 클래스의 완성된 코드는 아래 제공된 것과 같습니다.

stack<public>(t:type) := class:
    Elements<internal>:[]t = array{}

    # Adds NewElement to the top of the stack by returning a new
    # stack with NewElement as the top
    Push<public>(NewElement:t):stack(t)=
        stack(t){Elements := Elements + array{NewElement}}

    # Removes the element on top of the stack and returns a tuple of both a new
    # stack with the top element removed and the removed element.

큐

큐는 초밥이 놓여 있는 컨베이어 벨트라고 생각하면 됩니다. 여러분이 컨베이어 벨트에서 한 번에 하나씩 초밥 접시를 보내는 초밥집에 있고, 초밥 접시는 주문 순서대로 도착한다고 가정해 보세요. 줄 맨 앞에서 접시를 큐 제거(dequeue)하여 접시를 가져다가 먹을 수 있지만, 한 번에 접시 하나만 집을 수 있습니다. 새 접시를 주문하고 싶으면 요리사에게 줄 맨 뒤에 접시를 큐 등록(enqueue)해 달라고 요청합니다. 큐에 이미 다른 초밥 접시가 있는 경우, 뒤에 있는 접시에 도달할 때까지 줄 앞의 접시를 계속해서 먹어야 합니다. 가장 처음에 추가한 초밥 접시는 가장 처음에 제거됩니다. 따라서 큐는 FIFO, 즉 선입선출 데이터 구조라고 할 수 있습니다.

사용 시점

큐는 도착 시점을 기준으로 데이터를 처리해야 하는 경우 유용합니다. 드라이브 스루에서 고객을 응대하거나, 콜센터에서 대기 중인 콜이 쌓이거나, 인터뷰에서 선수에게 질문을 연달아 하는 것 등이 여기에 해당합니다. 예를 들어, 플레이어가 한 번에 하나씩 작업을 수행하거나 경험하는 동안 다른 플레이어가 대기할 공간을 제작하려는 경우, 큐를 사용하여 선입선출 기반으로 도착 시점에 따라 플레이어의 순서를 정렬할 수 있습니다.

Verse 구현

Verse API에는 기본으로 제공되는 큐 구현이 없지만, 직접 생성할 수 있습니다.

스택과 마찬가지로, 배열이나 링크된 목록 등 모든 순서의 데이터 구조를 사용하는 큐의 엘리먼트를 구현할 수 있습니다. 이 예시에서는 큐 앞과 뒤에 모두 쉽게 액세스할 수 있도록 배열을 사용하겠습니다. 연결된 목록을 사용한 큐 구현은 이 코드 스니펫을 확인하세요.

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}

Elements 배열은 타입 t인 큐에 오브젝트를 저장합니다. 즉, 이는 int, float, queue 등 어떤 타입의 엘리먼트로도 스택을 초기화할 수 있다는 뜻입니다. type을 스택 클래스의 실행인자로 사용하는 것은 [파라미터 타입](parametric-types-in-verse)의 예시입니다.

스택과 마찬가지로, 큐에도 몇 가지의 헬퍼 함수가 필요합니다. Enqueue() 및 Dequeue()를 수행할 수 있도록 큐의 앞과 뒤가 어디인지 알아야 합니다. 큐의 크기를 파악하는 것과 큐가 비어 있는지 여부를 아는 것도 유용합니다. 이는 Size(), IsEmpty(), Front(), Back()이라는 4가지 함수에서 정의할 수 있습니다.

# Returns the size of the queue
Size<public>()<transacts>:int=
    Elements.Length

# Succeeds if the queue is empty
IsEmpty<public>()<decides><transacts>:void=
    Size() = 0

# Returns the element at the front of the queue.
Front<public>()<decides><transacts>:t=

Size() 함수는 Elements 배열의 Length를 반환합니다. IsEmpty() 함수는 Size() 함수를 호출하며, Size()가 0과 같지 않을 경우 실패하는 <transacts> 지정자를 가지고 있습니다.

Front() 및 Rear() 함수는 엘리먼트 배열의 앞(index 0) 및 뒤(Length - 1) 인덱스에서 엘리먼트를 반환합니다. 배열이 비어 있을 경우 배열 액세스에 실패할 수 있으므로 두 함수는 모두 <decides><transacts> 지정자를 가집니다.

stack과 마찬가지로 queue 클래스 역시 Elements 배열을 지정하는 데 생성자 함수를 사용해야 합니다. 생성자 함수는 Elements의 값에 액세스하여 엘리먼트의 초기 배열에 지정하도록 허용합니다.

# Creates and returns a queue from an initial array of elements InitialElements.
CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t):
    Elements := InitialElements

큐 등록 및 큐 제거

큐에 엘리먼트를 추가하거나 큐에서 엘리먼트를 제거하려면, 큐 뒤에 새 엘리먼트를 큐 등록하거나 큐 앞에서 엘리먼트를 큐 제거해야 합니다.

# Adds a new element to the back of the queue by returning a
# new queue with NewElement at the back.
Enqueue<public>(NewElement:t):queue(t)=
    queue(t){Elements := Elements + array{NewElement}}

# Removes the element at the front of the queue and returns a tuple of
# both a new queue with the element removed and the removed element.
Dequeue<public>()<decides><transacts>:tuple(queue(t),t)=
    FirstElement := Front[]
    (queue(t){Elements := Elements.RemoveElement[0]}, FirstElement)

Enqueue() 함수는 큐에 삽입하고 싶은 엘리먼트를 취하여 새 엘리먼트가 맨 뒤에 있는 새 큐를 반환합니다. 현재의 큐를 수정하는 것이 아니라 새 큐를 반환하는 것은 함수 프로그래밍의 예시로, 부작용의 위험을 줄여 줍니다.

Dequeue() 함수의 경우 (RemoveElement[] 함수를 사용하여) 큐 맨 앞의 엘리먼트를 제거 및 반환하고, 또한 첫 번째 엘리먼트가 제거된 새 큐를 반환해야 합니다. 배역 액세스의 실패 가능 표현식과 Front() 호출로 인해, Dequeue()는 <decides><transacts> 지정자를 가져야 합니다.

완성된 코드

큐 클래스의 완성된 코드는 아래 제공된 것과 같습니다.

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}

    # Adds a new element to the back of the queue by returning a
    # new queue with NewElement at the back.
    Enqueue<public>(NewElement:t):queue(t)=
        queue(t){Elements := Elements + array{NewElement}}

    # Removes the element at the front of the queue and returns a tuple of
    # both a new queue with the element removed and the removed element.

직접 해 보기

스택 및 큐를 반복작업하고 발전시키는 데는 수많은 방법이 존재하며, 함수 기능을 추가할 수 있는 다양한 방법을 탐색해 보는 것이 좋습니다. 시작에 도움이 되는 몇 가지 아이디어를 준비했습니다.

• 큐를 순환 큐로 전환하여 마지막 엘리먼트가 첫 번째 엘리먼트와 연결되고 큐가 계속해서 루프하도록 해 보세요.

• 오브젝트가 큐 입장 시점뿐만 아니라 다른 값에도 기반하여 정렬되는 우선순위 큐를 만들어 보세요.

• 하노이 탑과 같이 스택을 사용하는 게임을 제작해 보세요. 고객이 대기열에서 기다려야 하는 레스토랑 게임을 제작해 보는 것도 좋습니다.