[C#] 스택(Stack), 큐(Queue) 속도 차이

실험 배경

캐시메모리 지역성 때문에 스택이 큐보다 push, pop 하는데 속도가 더 빠르다 해서

실험을 해보았는데 데이터 push만 하는 경우에도 스택이 더 빨라서 그 이유를 찾아보았습니다.

 

실험 환경

Windows 10

유니티, C#

 

결과

결론부터 말하자만 스택이 더 빠르다.

C#에서 스택은 배열, 큐는 순환배열로 이루어져 있어

조건검사 하는데 좀 더 많은 연산을 하는 것 같다.

 

실험코드, 참고 사이트는 아래에 적겠습니다.

 

---

테스트

Stack

실험 코드

실험 코드
using System;
using System.Collections.Generic;
using UnityEngine;

public class TimeTester : MonoBehaviour
{
    private Queue<int> queue = new Queue<int>();
    private Stack<int> stack = new Stack<int>();


    void Start()
    {
        int repeat = 5000000;

        CheckTime(() =>
        {
            stack = new Stack<int>();
            for (int i = 0; i < repeat; i++)
            {
                stack.Push(0);
            }

        }, "Stack Test", 10);

    }
    

    private void CheckTime(Action action, string testName, int repeat)
    {
        double sum = 0;
        for (int i = 1; i <= repeat; i++)
        {
            var watch = new System.Diagnostics.Stopwatch();
            watch.Start();

            action();

            watch.Stop();
            sum += watch.ElapsedMilliseconds;

            Debug.Log(testName + "반복" + i + ": " + repeat + ", 시간: " + watch.ElapsedMilliseconds + "ms");
            GC.Collect();
        }

        Debug.Log(testName + "평균: " + sum / repeat + "ms");
    }
}

---

Queue

실험코드

using System;
using System.Collections.Generic;
using UnityEngine;

public class TimeTester : MonoBehaviour
{
    private Queue<int> queue = new Queue<int>();
    private Stack<int> stack = new Stack<int>();


    void Start()
    {
        int repeat = 5000000;

        CheckTime(() =>
        {
            queue = new Queue<int>();
            for (int i = 0; i < repeat; i++)
            {
                queue.Enqueue(0);
            }

        }, "Queue Test", 10);

    }

    private void CheckTime(Action action, string testName, int repeat)
    {
        double sum = 0;
        for (int i = 1; i <= repeat; i++)
        {
            var watch = new System.Diagnostics.Stopwatch();
            watch.Start();

            action();

            watch.Stop();
            sum += watch.ElapsedMilliseconds;

            Debug.Log(testName + "반복" + i + ": " + repeat + ", 시간: " + watch.ElapsedMilliseconds + "ms");
            GC.Collect();
        }

        Debug.Log(testName + "평균: " + sum / repeat + "ms");
    }
}

---

둘의 차이점

C#에서 스택은 배열, 큐는 순환배열(원형큐)로 이루어져있다.

 

아래 사이트에서 확인해볼 수 있습니다.

스택: https://docs.microsoft.com/ko-kr/dotnet/api/system.collections.generic.stack-1?view=net-6.0 

큐: https://docs.microsoft.com/ko-kr/dotnet/api/system.collections.generic.queue-1?view=net-6.0 

 

경험상 순환배열로 구현하는게 복잡하다고 알고있긴 하지만 코드를 직접 확인해보겠습니다.

 

 

스택의 Push 함수

데이터를 넣는데 최대 크기를 넘어가면 새로운 배열을 생성해 복사하도록 돼있다.

https://referencesource.microsoft.com/#System/compmod/system/collections/generic/stack.cs,c5371bef044c6ab6

큐의 Enqueue 함수

스택과 같이 최대 크기가 넘어가면 새로운 배열을 할당하도록 돼있습니다.

스택보다 코드가 길고 연산할 것도 많아보입니다.

https://referencesource.microsoft.com/#System/compmod/system/collections/generic/queue.cs,6dba415a0e1792b0