C# - 스택 (Stack), 큐 (Queue)

스택 (Stack)

자료를 적층 구조로 쌓아 올린 것을 의미한다.

후입선출 (LIFO, Last In First Out) 또는 선입후출 (FILO, First In Last Out) 의 구조로

나중에 쌓은 것이 먼저 나온다는 뜻이다.

즉, 상자나 카드 같은 것을 쌓아 올리고, 그것을 위에서부터 꺼내는 방식이다.

웹 브라우저의 뒤로가기 기능, 프로그램의 Undo 기능 같은 것들을 예시로 들 수 있다.

 

DFS(깊이 우선 탐색) 알고리즘에서도 사용된다.

DFS 에 대해서는 이전 글에 정리되어있다.

 

기본적인 사용 방식은 리스트와 매우 비슷하다

Stack<int> myStack = new Stack<int>();

 

주요 메서드

Push : 데이터를 스텍 위에 추가한다.

stack.Push(n);

 

Pop : 스택 맨 위 요소를 꺼내 제거하고 반환한다. 비어있으면 예외 발생.

int poped = stack.Pop();

 

Peek : 맨 위 요소를 확인(반환)한다.

int peek = stack.Peek();

 

Contains : 특정 요소가 스택에 있는지 확인한다. (bool 반환)

bool exists = stack.Contains(10);

 

Clear : 모든 요소를 제거한다.

stack.Clear();

 

Count : 현재 스택에 들어있는 요소 개수를 반환한다.

Console.WriteLine(stack.Count);

 

ToArray, ToList(LINQ) : 배열, 리스트로 변환한다.

int[] arr = stack.ToArray();

 

 

 

예시 코드로 한번 살펴보자.

using System;
using System.Collections.Generic;

namespace StackExample
{
    class Program
    {
        static void Main(string[] args)
        {
            Stack<char> keyInputs = new Stack<char>();

            // Push: 자료 넣기
            keyInputs.Push('a');
            keyInputs.Push('s');
            keyInputs.Push('d');
            keyInputs.Push('f');

            // Peek: 가장 위의 요소 확인
            Console.WriteLine($"Peek: {keyInputs.Peek()}"); // f

            // Pop: 꺼내면서 제거
            while (keyInputs.Count > 0)
            {
                char popped = keyInputs.Pop();
                Console.WriteLine(popped);
            }
        }
    }
}

 

이렇게 Push하면 위에서부터 f d s a 순으로 쌓이게 되며 Peek 시 가장 위(가장 나중)에 쌓인 f가 출력된다.

즉 Push는 배열의 맨 앞 쪽에 추가하는 기능처럼 보이는데 실제로는 위로 쌓인다고 이해하는 게 맞다..

ToArray로 변환했을 때, Pop의 순서대로 배열을 만들기 때문에 맨 위의 숫자부터 { f, d, s, a } 형태의 배열이 만들어진다.

 

 

 

스택 오버플로우 (Stack Overflow)

stackoverflow.com 라는 사이트를 한 번쯤은 들어봤을 거다.

아니라더라도 프로그래밍을 계속 하게되면 언젠가 반드시 들어보게 될 거다...

프로그래밍에서 스택(Stack)은 단순히 자료구조만 뜻하는 게 아니다.

프로그램이 실행될 때, 호출 스택(Call Stack)이라는 메모리 영역에 함수 호출 정보(변수, 리턴 주소)가 쌓인다.

함수가 호출될 때, 스택에 Push되고, 종료될때 Pop 되는 구조다.

방금 배운 자료구조의 Stack과 동일한 형태다.

아마 이런 동작 원리까지 생각해서 이런 네이밍이 된 거 같다.

 

그리고 이런 콜 스택이 종료 지점이 정확하게 정의되지 않아 무한루프에 빠진 재귀함수, 혹은 너무 깊거나 많은 함수의 반복 호출이 발생하면 이 스택이 넘쳐 프로그램이 터져버리는 현상을 스택 오버플로우 라고 한다.

정확히는 System.StackOverflowException 이 발생한다.

 

 

---

 

큐 (Queue)

스택을 알았으면 큐는 쉽게 이해할 수 있다.

스택의 정 반대로, 선입선출(FIFO, First In First Out) 구조다.

현실적으로 간단하게 줄 서기를 생각하면 된다.

줄을 먼저 선 사람이 먼저 서비스를 받는다.

 

근데 이거 어디서 많이 들어봤을 거다.

롤, 오버워치 같은 게임의 매칭시스템을 "큐 돌린다" 라고 흔히들 말하곤 하는데 바로 그 큐가 맞다.

게임 서버 매칭 대기열, 운영체제의 프로세스 스케쥴링, 서버 트래픽 처리, BFS(너비 우선 탐색) 알고리즘 등에 사용된다.

 

기본적인 사용법도 매우 쉽다. Stack을 queue로만 바꿔주면 된다.

Queue<int> myQueue = new Queue<int>();

 

주요 메서드

Enqueue : 데이터를 큐의 뒤쪽에 추가한다.

queue.Enqueue(n);

 

Dequeue : 큐의 맨 앞 요소를 꺼내면서 제거한다. 비어있으면 예외 발생.

int first = queue.Dequeue();

 

Peek : 큐의 맨 앞 요소를 확인만 하고 제거하지 않는다.

int peek = queue.Peek();

 

Contains : 특정 요소가 큐에 있는지 확인한다. bool 반환.

bool exists = queue.Contains(n);

 

Clear : 모든 요소를 제거한다.

queue.Clear();

 

Count : 현재 큐에 들어있는 요소 개수를 반환한다.

Console.WriteLine(queue.Count);

 

ToArray, ToList(LINQ) : 배열, 리스트로 변환한다.

int[] arr = queue.ToArray();

 

 

 

예시 코드는 다음과 같다

using System;
using System.Collections.Generic;

namespace QueueExample
{
    class Program
    {
        static void Main(string[] args)
        {
            Queue<char> keyInputs = new Queue<char>();

            // Enqueue: 데이터 넣기
            keyInputs.Enqueue('a');
            keyInputs.Enqueue('b');
            keyInputs.Enqueue('c');
            keyInputs.Enqueue('d');

            // Dequeue: 가장 앞에서 꺼내기
            while (keyInputs.Count > 0)
            {
                char dequeued = keyInputs.Dequeue();
                Console.WriteLine(dequeued);
            }
        }
    }
}

 

a b c d 순서대로 입력되고, 나갈 때도 입력된 순으로 a b c d 가 나가게 된다.

들어온 순서대로 쌓이고, 꺼낼 때도 먼저 들어온 녀석, 즉 맨 앞의 인덱스를 내보낸다고 이해하면 된다.

ToArray로 변환했을 때 { a, b, c, d } 순으로 나와서 스택보다는 조금 더 직관적인 느낌도 든다.