[자료구조] 스택(Stack)과 큐(Queue) 비교

선형 자료 구조인 스택과 큐는 데이터 구조에서 중요한 역할을 하는 두 가지 개념이다.
면접에서 자주 물어보는 내용이니 잘 숙지해 둘 필요가 있다.
(*선형 자료 구조: 데이터가 순차적으로 배열되어, 각 요소가 정확히 하나의 앞 요소와 하나의 뒤 요소를 가지는 구조이다. 데이터의 순서가 중요하며, 요소 간의 관계가 일대일로 연결되어 있다.)

스택(Stack)

스택은 선형 자료 구조의 한 종류로, 후입선출 (LIFO, Last In First Out) 원칙에 따라 작동하는 데이터 구조이다. 즉, 마지막에 삽입된 요소가 가장 먼저 제거된다. 스택의 각 요소는 다음과 같은 방식으로 정렬된다.

A,B,C의 순서로 push 했다면 pop 했을 때 C부터 나오게 된다

• Push: 스택의 맨 위에 요소를 추가한다.
• Pop: 스택의 맨 위에 있는 요소를 제거하고 반환한다.
• Peek: 스택의 맨 위에 있는 요소를 제거하지 않고 반환한다.
• IsEmpty: 스택이 비어 있는지 확인한다.

스택을 사용하는 경우

• 재귀적인 알고리즘에서 호출 스택을 관리할 때
• 웹 브라우저의 뒤로가기 기능
• 수식 계산기에서 괄호의 짝을 맞출 때
• 되돌리기(Undo) 기능 구현

스택을 배열로 구현할 때의 장단점

장점: 구현이 간단하고, 인덱스를 통해 빠른 접근이 가능하다.
단점: 크기가 고정되어 있어 메모리 낭비가 발생할 수 있으며, 크기를 초과할 경우에 동적으로 확장이 불가능하다.

스택 오버플로우와 언더플로우란?

스택 오버플로(Stack Overflow): 스택이 가득 찬 상태에서 Push 연산을 시도할 때 발생한다.
스택 언더플로(Stack Underflow): 스택이 비어있는 상태에서 Pop 연산을 시도할 때 발생한다.

간단한 유니티 스택 활용 예시

 유니티에서 스택은 주로 게임 오브젝트의 상태를 관리하거나, 되돌리기 기능(Undo)을 구현할 때 유용하다. 예를 들어, 플레이어의 이동 기록을 스택에 저장해두고, 플레이어가 되돌리기 버튼을 눌렀을 때 이전 위치로 돌아가도록 하는 기능을 구현할 때 사용할 수 있다.

using System.Collections.Generic;
using UnityEngine;

public class PlayerMovement : MonoBehaviour
{
    private Stack<Vector3> movementHistory = new Stack<Vector3>();

    void Update()
    {
        if (Input.GetKeyDown(KeyCode.W))
        {
            movementHistory.Push(transform.position);
            transform.Translate(Vector3.forward);
        }
        if (Input.GetKeyDown(KeyCode.U) && movementHistory.Count > 0)
        {
            transform.position = movementHistory.Pop();
        }
    }
}

위 예시 코드에서 플레이어가 'W'키를 누르면 현재 위치를 스택에 저장하고 앞으로 이동한다. 'U'키를 누르면 마지막 위치로 돌아간다.

큐(Queue)

 큐는 선형 자료 구조의 또 다른 종류로, 선입선출(FIFO, First In First Out)의 원칙을 따른다. 즉, 가장 먼저 삽입된 요소가 가장 먼저 제거된다. 큐의 각 요소는 다음과 같은 방식으로 정렬된다.

• Enqueue: 큐의 끝에 요소를 추가한다.
• Dequeue: 큐의 앞에서 요소를 제거하고 반환한다.
• Peek: 큐의 앞에 있는 요소를 제거하지 않고 반환한다.
• IsEmpty: 큐가 비어 있는지 확인한다.

큐를 사용해야 하는 상황

• 프린터의 인쇄 작업 대기열 관리
• 너비 우선 탐색(BFS) 알고리즘
• 네트워크 패킷 관리
• 작업 스캐줄링

큐를 연결 리스트로 구현할 때의 장단점

장점: 동적으로 크기를 조절할 수 있어 메모리 효율이 좋다.
단점: 각 요소에 대한 추가 메모리(포인터)가 필요하며, 구현이 배열보다 복잡할 수 있다.

순환 큐(Circular Queue)란 무엇인가?

순환 큐는 고정된 크기의 배열을 사용하여 큐를 구현할 것으로, 마지막 위치가 첫 번째 위치와 연결되어 순환 구조를 갖는다. 이 방식은 메모리 낭비를 줄이고 효율적인 큐 관리를 가능하게 한다.

간단한 유니티 큐 활용 예시

유니티에서 큐는 주로 작업의 순서를 관리하거나 NPC의 행동 대기열을 관리할 때 유리하다.
예를 들어, NPC가 여러 작업을 차례로 수행해야 하는 경우에 큐를 사용하여 작업을 관리할 수 있다.

using System.Collections.Generic;
using UnityEngine;

public class NPCBehavior : MonoBehaviour
{
    private Queue<Vector3> taskQueue = new Queue<Vector3>();

    void Start()
    {
        taskQueue.Enqueue(new Vector3(1, 0, 0));
        taskQueue.Enqueue(new Vector3(2, 0, 0));
        taskQueue.Enqueue(new Vector3(3, 0, 0));
    }

    void Update()
    {
        if (taskQueue.Count > 0 && !IsMoving())
        {
            Vector3 nextTask = taskQueue.Dequeue();
            StartCoroutine(MoveToPosition(nextTask));
        }
    }

    bool IsMoving()
    {
        // NPC가 현재 이동 중인지 여부를 반환하는 코드
        return false;
    }

    System.Collections.IEnumerator MoveToPosition(Vector3 position)
    {
        while ((transform.position - position).magnitude > 0.1f)
        {
            transform.position = Vector3.MoveTowards(transform.position, position, Time.deltaTime);
            yield return null;
        }
    }
}

위 예시 코드에서 NPC는 세 가지 위치로 차례로 이동해야 한다. 각 위치는 큐에 저장되고, NPC는 큐에서 위치를 하나씩 꺼내서 이동한다.