스택과 큐

스택은 후입선출 원리로 동작하는 선형 자료구조이다. 데이터를 저장하는 위치는 스택 포인터가 가리키며, 새로운 항목은 항상 스택의 꼭대기에 추가되고, 제거될 때도 꼭대기 항목부터 꺼낸다. 이는 접시를 쌓아 올리고 위에서부터 하나씩 꺼내는 것에 비유할 수 있다. 스택의 이러한 특성은 실행 취소 기능, 함수 호출 시의 복귀 주소 저장, 재귀 알고리즘 구현 등에 널리 활용된다.

반면, 큐는 선입선출 원리로 동작하는 선형 자료구조이다. 데이터는 큐의 뒤에서 삽입되고, 큐의 앞에서 제거된다. 이는 매표소에서 줄을 서서 기다리는 사람들의 순서와 유사하다. 큐는 순서를 보장해야 하는 작업 처리, 프로세스 스케줄링, 너비 우선 탐색 알고리즘, 데이터 버퍼링 등에 주로 사용된다.

두 자료구조 모두 데이터를 일렬로 저장하는 선형 구조이지만, 데이터의 삽입과 삭제가 발생하는 위치가 근본적으로 다르다. 스택은 한쪽 끝에서만 모든 작업이 이루어지는 반면, 큐는 삽입과 삭제가 서로 반대쪽 끝에서 이루어진다. 이 차이는 각 자료구조가 해결하는 문제의 종류를 결정짓는 핵심 요소이다.

스택의 주요 연산은 데이터의 삽입과 삭제가 한쪽 끝(top)에서만 이루어진다는 제약을 반영한다. 가장 핵심적인 연산은 push와 pop이다. push 연산은 스택의 최상위에 새로운 항목을 추가한다. pop 연산은 스택의 최상위에 있는 항목을 제거하고 그 값을 반환한다. 이 두 연산은 모두 스택의 top 위치에서만 작동하므로 상수 시간, 즉 O(1)의 복잡도를 가진다.

스택의 상태를 확인하는 보조 연산도 중요하다. peek (또는 top) 연산은 pop 연산처럼 항목을 제거하지 않고, 현재 최상위 항목이 무엇인지만 확인하여 반환한다. isEmpty 연산은 스택에 현재 요소가 하나도 없는지 여부를 불리언(Boolean) 값으로 반환한다. 일부 구현에서는 스택이 가질 수 있는 최대 크기를 확인하는 isFull 연산이나 현재 스택에 저장된 항목의 개수를 반환하는 연산을 제공하기도 한다.

이러한 연산들은 LIFO(Last-In, First-Out) 원칙을 정확히 구현하며, 스택을 활용하는 모든 알고리즘의 기초가 된다.

스택은 일반적으로 배열 또는 연결 리스트를 기반으로 구현된다. 배열을 사용한 구현은 메모리 접근이 빠르고 구현이 간단하다는 장점이 있다. 하지만 스택의 최대 크기를 미리 정해야 하므로, 크기 제한이 없다는 스택의 이론적 특성을 완전히 반영하지 못한다. 반면, 연결 리스트를 사용하면 동적으로 노드를 추가하거나 제거할 수 있어 크기 제한이 없다. 각 노드는 데이터와 다음 노드를 가리키는 포인터를 저장하며, 헤드 포인터가 스택의 최상단(top)을 가리킨다.

큐 역시 배열 또는 연결 리스트로 구현할 수 있다. 배열을 사용한 단순한 구현에서는 front와 rear 두 개의 인덱스 포인터를 관리한다. 데이터를 삽입할 때는 rear 인덱스를 증가시키고, 삭제할 때는 front 인덱스를 증가시킨다. 그러나 이 방식은 배열의 앞부분이 비어 있음에도 불구하고 rear가 배열 끝에 도달하면 더 이상 삽입할 수 없는 '가짜 오버플로우' 문제가 발생한다. 이 문제를 해결하기 위해 배열의 끝과 시작을 연결한 원형 큐 구조가 자주 사용된다.

다양한 프로그래밍 언어에서 스택과 큐는 표준 라이브러리를 통해 제공된다. 예를 들어, 자바에서는 java.util.Stack 클래스와 java.util.Queue 인터페이스가 있으며, 파이썬에서는 리스트를 스택으로 사용하거나 collections.deque를 스택과 큐 모두에 활용할 수 있다. C++의 표준 템플릿 라이브러리(STL)에는 stack과 queue 템플릿 클래스가 포함되어 있다.

스택의 가장 대표적인 응용 사례는 프로그램 카운터와 지역 변수 정보를 저장하는 호출 스택이다. 함수가 호출될 때마다 반환 주소와 실행 상태가 스택에 푸시(push)되고, 함수 실행이 종료되면 팝(pop)하여 이전 상태로 복귀한다. 이는 재귀 함수의 동작 원리이기도 하다. 또한, 괄호 검사나 HTML 태그 검증과 같이 열림과 닫힘의 순서가 중요한 문법 검사에 널리 사용된다. 후위 표기법 수식 계산이나 깊이 우선 탐색 알고리즘에서도 스택이 핵심 자료구조로 활용된다.

큐는 순서대로 처리해야 하는 작업을 관리할 때 유용하다. 프린터 스풀러는 대표적인 예시로, 여러 사용자의 인쇄 요청을 도착 순서대로 큐에 저장하여 순차적으로 처리한다. 운영체제의 작업 스케줄링에서도 라운드 로빈 방식으로 CPU 시간을 할당할 때 준비 큐를 사용한다. 너비 우선 탐색 알고리즘은 탐색 시작점의 인접 노드들을 큐에 넣고 순서대로 방문하는 방식으로 동작한다. 또한, 데이터 버퍼링이나 메시지 큐와 같은 프로듀서-컨슈머 문제 해결에도 큐가 필수적이다.

스택은 후입선출 원리로 동작하는 선형 자료구조이다. 데이터를 쌓아 올리는 구조로, 가장 나중에 추가된 항목이 가장 먼저 제거된다. 책을 바닥에 쌓아 올렸을 때, 가장 위에 있는 책을 먼저 꺼내는 것과 유사한 방식이다. 이 구조는 데이터의 삽입과 삭제가 한쪽 끝에서만 발생하며, 이 끝을 스택 포인터가 가리킨다.

반면, 큐는 선입선출 원리로 동작하는 선형 자료구조이다. 데이터는 뒤에서 추가되고 앞에서 제거된다. 매표소 앞의 줄을 서는 사람들의 순서와 같다. 가장 먼저 줄을 선 사람이 가장 먼저 표를 구매하고 떠난다. 큐는 데이터가 들어오는 리어와 데이터가 나가는 프론트라는 두 개의 지점을 관리한다.

두 자료구조 모두 기본적인 추상 데이터 타입으로, 프로그래밍에서 데이터의 임시 저장과 순서 제어에 널리 사용된다. 스택은 실행 취소 기능이나 함수 호출 관리에, 큐는 작업 대기열이나 메시지 버퍼 처리에 적합하다.

스택의 주요 연산은 후입선출 원칙에 따라 데이터를 관리한다. 가장 기본적인 연산은 데이터를 추가하는 Push와 데이터를 제거하는 Pop이다. Push 연산은 스택의 최상위(Top)에 새로운 요소를 쌓는다. Pop 연산은 현재 Top에 위치한 요소를 제거하고 그 값을 반환한다. Top이 가리키는 요소의 값을 제거하지 않고 확인만 하는 Peek (또는 Top) 연산도 자주 사용된다. 또한 스택이 비어 있는지 확인하는 IsEmpty 연산과 현재 스택에 저장된 요소의 개수를 반환하는 연산 등이 보조적으로 활용된다.

큐의 주요 연산은 선입선출 원칙을 따른다. 데이터를 큐의 뒤쪽(Rear)에 추가하는 연산을 Enqueue (또는 Add, Put)라고 한다. 반대로, 큐의 앞쪽(Front)에 위치한, 가장 먼저 들어온 데이터를 제거하고 반환하는 연산을 Dequeue (또는 Remove, Get)라고 한다. 스택과 마찬가지로 Front의 데이터를 제거하지 않고 조회하는 Peek 연산, 그리고 큐가 비었는지 또는 가득 찼는지 확인하는 연산들이 기본적으로 제공된다.

두 자료구조의 연산은 일반적으로 상수 시간(O(1))에 수행된다. Push/Pop 또는 Enqueue/Dequeue 연산은 저장 공간이 충분하다면 요소의 개수와 관계없이 일정한 시간이 소요된다. 이는 연결 리스트나 배열을 기반으로 구현했을 때 모두 성립하는 특징이다.

스택의 구현 방법은 크게 배열을 이용한 방법과 연결 리스트를 이용한 방법으로 나뉜다. 배열을 이용한 구현은 메모리 할당이 연속적이어서 접근 속도가 빠르고 구현이 간단하다는 장점이 있다. 하지만 스택의 최대 크기를 사전에 결정해야 하므로, 데이터 개수의 변동이 클 경우 메모리 낭비나 스택 오버플로가 발생할 수 있다. 반면, 연결 리스트를 이용한 구현은 동적 메모리 할당을 통해 노드를 추가하므로 크기에 제한이 없다. 그러나 각 노드가 다음 노드를 가리키는 포인터를 저장해야 하므로 추가적인 메모리 오버헤드가 발생하며, 배열에 비해 상대적으로 접근 속도가 느릴 수 있다.

큐 역시 배열과 연결 리스트를 사용하여 구현할 수 있다. 배열로 구현할 때는 순환 큐 방식을 주로 사용한다. 순환 큐는 배열의 처음과 끝을 논리적으로 연결하여, 배열의 끝에 도달했을 때 다시 앞부분의 빈 공간을 활용하는 방식이다. 이는 배열의 앞부분이 비어 있는 일반적인 선형 배열 큐의 메모리 낭비 문제를 해결한다. 연결 리스트를 이용한 구현은 헤드 포인터와 테일 포인터를 관리하여 삽입과 삭제를 양 끝에서 효율적으로 수행한다. 이 방식은 크기 제한이 없지만, 노드 간의 연결을 위한 포인터 저장 공간이 필요하다.

두 자료구조의 구현 선택은 사용되는 환경과 요구사항에 따라 달라진다. 메모리 크기가 제한적이고 데이터의 최대 개수를 예측할 수 있는 임베디드 시스템 등에서는 배열 기반 구현이 유리하다. 반면, 데이터의 삽입과 삭제가 빈번하고 그 규모를 예측하기 어려운 애플리케이션, 예를 들어 너비 우선 탐색 알고리즘에서 동적으로 노드를 관리할 때는 연결 리스트 기반 구현이 더 적합하다.

스택은 후입선출 방식으로 동작하기 때문에 실행 취소(Undo) 기능, 재귀 알고리즘의 호출 관리, 깊이 우선 탐색 알고리즘에 널리 사용된다. 웹 브라우저의 뒤로 가기 버튼은 방문한 페이지 주소를 스택에 저장하여 구현하는 대표적인 예시이다. 또한, 괄호 검사나 후위 표기법 계산기 같은 수식 평가 알고리즘에서도 핵심적인 역할을 한다.

큐는 선입선출 방식으로 동작하기 때문에 순서를 보장해야 하는 대기열 시스템에 적합하다. 프린터의 작업 스케줄링, CPU 스케줄링 알고리즘, 너비 우선 탐색 알고리즘에서 사용된다. 또한, 메시지 큐나 버퍼처럼 데이터 생산자와 소비자 간의 속도 차이를 완화하는 중간 매개체 역할을 하기도 한다.

구체적인 구현 사례를 비교하면 다음과 같다.

스택은 후입선출 방식으로 데이터를 처리한다. 이는 가장 나중에 삽입된 데이터가 가장 먼저 제거된다는 원리를 의미한다. 데이터의 삽입과 제거가 모두 리스트의 한쪽 끝에서만 발생하며, 이 끝을 스택 포인터가 가리킨다. 따라서 데이터 접근 순서는 삽입의 역순이 된다.

반면, 큐는 선입선출 방식으로 데이터를 처리한다. 이는 가장 먼저 삽입된 데이터가 가장 먼저 제거된다는 원리를 의미한다. 데이터는 리스트의 한쪽 끝(리어)에서 삽입되고, 반대쪽 끝(프론트)에서 제거된다. 이는 대기열과 같은 구조로, 도착한 순서대로 서비스를 받는 모델과 일치한다.

두 자료구조의 처리 방식 차이는 내부적인 데이터 접근 제한에서 비롯된다. 스택은 데이터에 대한 접근이 최상단 요소로 제한되어 있어, 중간에 있는 데이터를 직접 조회하거나 수정하는 연산은 기본적으로 제공하지 않는다. 큐 또한 데이터에 대한 접근이 프론트와 리어로 제한되어 있어, 대기 중인 데이터의 순서를 임의로 변경할 수 없다.

이러한 처리 방식의 차이는 각각의 전형적인 용도와 직결된다. 스택은 실행 취소 기능, 재귀 알고리즘, 괄호 검사와 같이 최근에 발생한 사건을 먼저 처리해야 하는 상황에 적합하다. 큐는 프린터 스풀링, CPU 스케줄링, 너비 우선 탐색과 같이 순서를 보존해야 하는 대기나 버퍼링 상황에 적합하다.

스택과 큐의 주요 연산들은 일반적으로 상수 시간, 즉 O(1)의 시간 복잡도를 가진다. 이는 데이터의 개수(n)와 관계없이 연산을 수행하는 데 일정한 시간이 소요됨을 의미한다. 이는 두 자료구조가 배열이나 연결 리스트를 기반으로 구현될 때, 삽입과 삭제가 항상 한쪽 끝(스택의 경우 top, 큐의 경우 rear와 front)에서만 발생하기 때문이다.

구체적인 연산별 시간 복잡도는 다음과 같다.

단, 이 상수 시간 복잡도는 이상적인 구현 환경을 가정한 것이다. 배열로 구현된 스택이 가득 찬 경우, 내부 배열의 크기를 동적으로 늘리는 과정에서 O(n)의 시간이 소요될 수 있다[1]. 또한, 특정 값을 찾거나 중간에 있는 데이터에 접근하는 연산은 지원하지 않으며, 이를 위해서는 전체 요소를 순회해야 하므로 O(n)의 시간이 필요하다.

따라서 스택과 큐는 데이터의 저장 순서에 따른 접근 제어가 주 목적이며, 삽입과 삭제의 효율성에 최적화된 자료구조라고 할 수 있다. 이 예측 가능한 성능 특성은 실시간 시스템이나 성능이 중요한 알고리즘 설계에서 이들을 선택하는 핵심 근거가 된다.

스택은 후입선출 방식으로 데이터를 처리하기 때문에, 가장 최근에 추가된 데이터에 우선적으로 접근해야 하는 상황에 적합하다. 대표적인 예로는 재귀 알고리즘의 호출 기록을 관리하는 호출 스택, 깊이 우선 탐색 알고리즘, 그리고 괄호 검사나 후위 표기법 계산기와 같은 구문 분석 작업이 있다. 또한 웹 브라우저의 '뒤로 가기' 기능이나 문서 편집기의 '실행 취소' 기능도 스택을 활용한 사례이다.

반면, 큐는 선입선출 방식을 따르므로, 데이터가 도착한 순서대로 처리해야 할 때 유용하다. 이는 대기열이 필요한 모든 시스템에 적용된다. 예를 들어, 프린터 스풀링, CPU 스케줄링, 너비 우선 탐색 알고리즘 등이 있다. 또한 네트워크 패킷 버퍼링이나 메시지 큐와 같은 비동기 통신 시스템에서 데이터의 순차적 전달을 보장하는 데에도 큐가 사용된다.

두 자료구조의 선택은 문제의 본질적인 요구사항에 의해 결정된다. 작업의 흐름이 중첩되거나 되돌리기가 필요한 경우에는 스택이, 순차적이고 공정한 처리 순서가 중요한 경우에는 큐가 일반적으로 더 적합한 해법이다. 예를 들어, 함수 호출은 자신을 호출한 함수로 반드시 돌아가야 하므로 스택이 필요하고, 은행 창구의 대기 줄은 먼저 온 사람이 먼저 서비스를 받아야 하므로 큐가 필요하다.

덱은 스택과 큐의 특성을 모두 가진 자료구조이다. 양쪽 끝에서 데이터의 삽입과 삭제가 모두 가능한 이중 종료 큐이다. 이 특성 때문에 'Double-Ended Queue'의 약어인 Deque로 불린다.

덱의 주요 연산은 네 가지로 구분된다. 앞쪽(front)에서 데이터를 추가하는 addFront(또는 pushFront) 연산과 제거하는 removeFront(또는 popFront) 연산이 있다. 뒤쪽(rear)에서 데이터를 추가하는 addRear(또는 pushBack) 연산과 제거하는 removeRear(또는 popBack) 연산이 있다. 일부 구현에서는 큐와 유사하게 enqueue, dequeue 용어를 사용하기도 하지만, 방향을 명시하는 것이 일반적이다.

덱은 연결 리스트나 동적 배열을 이용하여 구현한다. 연결 리스트를 사용하면 양쪽 끝에서의 삽입과 삭제를 상수 시간에 수행할 수 있다. 동적 배열을 사용할 경우, 앞쪽에서의 삽입/삭제는 요소들의 이동이 필요해 비효율적일 수 있으므로, 원형 버퍼 방식을 적용한 원형 덱 구현이 일반적이다. 주요 프로그래밍 언어의 표준 라이브러리에는 덱이 포함되어 있으며, 예를 들어 C++의 std::deque, 파이썬의 collections.deque가 대표적이다.

우선순위 큐는 각 요소가 연관된 우선순위 값을 가지며, 높은 우선순위를 가진 요소가 낮은 우선순위를 가진 요소보다 먼저 제거되는 추상 자료형이다. 일반적인 큐가 선입선출(FIFO) 방식을 따르는 것과 달리, 우선순위 큐는 요소의 추가 순서가 아닌 우선순위에 따라 제거 순서가 결정된다. 동일한 우선순위를 가진 요소들 사이의 순서는 일반적으로 추가된 순서(즉, FIFO)를 따르거나 구현에 따라 정의된다.

주요 연산으로는 새로운 요소와 그 우선순위를 삽입하는 연산(enqueue 또는 push), 그리고 가장 높은 우선순위를 가진 요소를 제거하고 반환하는 연산(dequeue 또는 pop)이 있다. 또한, 가장 높은 우선순위의 요소를 제거하지 않고 단순히 조회하는 peek 연산도 일반적으로 제공된다. 이러한 연산들의 효율성은 구현 방식에 크게 의존한다.

가장 널리 사용되는 구현 방식은 이진 힙 자료구조를 기반으로 한 것이다. 이진 힙은 완전 이진 트리의 형태를 가지며, 부모 노드의 우선순위가 자식 노드의 우선순위보다 항상 높은(또는 낮은) 힙 속성을 유지한다. 이 속성 덕분에 삽입과 삭제 연산 모두 O(log n)의 시간 복잡도로 효율적으로 수행될 수 있다. 우선순위 큐는 다익스트라 알고리즘, 허프만 코딩, 운영체제의 작업 스케줄링, 시뮬레이션 시스템의 이벤트 관리 등 다양한 분야에서 핵심적으로 활용된다.

원형 큐는 선형 큐의 공간 효율성 문제를 해결하기 위해 고안된 큐의 변형 자료구조이다. 선형 큐는 배열로 구현할 경우, 데이터를 삭제(dequeue)하면 앞쪽에 빈 공간이 생기지만, 새로운 데이터는 항상 뒤쪽에만 추가(enqueue)할 수 있어 공간이 낭비되는 문제가 있었다. 원형 큐는 이러한 문제를 해결하기 위해 배열의 마지막 인덱스와 첫 번째 인덱스를 논리적으로 연결하여 원형 구조를 형성한다. 이로 인해 배열의 앞부분에 생긴 빈 공간을 재활용할 수 있어, 배열 전체를 효율적으로 사용할 수 있다.

원형 큐의 핵심은 두 개의 포인터(프런트와 리어)를 사용하여 큐의 시작과 끝을 추적하는 것이다. 데이터가 추가되면 리어 포인터가 이동하고, 데이터가 제거되면 프런트 포인터가 이동한다. 포인터가 배열의 끝에 도달하면, 다음 위치는 배열의 처음(인덱스 0)으로 순환한다. 이 순환은 모듈로 연산(%)을 통해 구현된다. 예를 들어, 크기가 n인 배열에서 리어 포인터의 다음 위치는 (rear + 1) % n으로 계산된다. 이 구조에서 큐가 가득 찼는지와 비었는지를 구분하기 위해 일반적으로 하나의 공간을 의도적으로 비워둔다[2].

원형 큐의 주요 연산인 인큐와 디큐의 시간 복잡도는 O(1)이다. 이는 선형 큐와 동일하지만, 공간을 재활용함으로써 메모리 사용 측면에서 더 우수한 성능을 보인다. 구현은 배열을 기반으로 하는 것이 일반적이며, 포인터의 순환적 이동을 정확히 관리하는 것이 구현의 핵심이다.

원형 큐는 메모리 크기가 제한된 임베디드 시스템, 운영체제의 프로세스 스케줄링 버퍼, 네트워크 패킷 처리 버퍼 등 연속적인 데이터 스트림을 효율적으로 관리해야 하는 다양한 실시간 시스템에서 널리 활용된다.

스택의 후입선출 특성은 특정 유형의 알고리즘 설계에 매우 적합하다. 대표적으로 재귀 알고리즘의 반복적 구현, 깊이 우선 탐색, 그리고 괄호 검사나 수식 계산과 같은 문제 해결에 널리 사용된다.

재귀 함수는 내부적으로 호출 스택을 사용하여 동작한다. 따라서 재귀 알고리즘을 명시적인 스택 자료구조를 이용해 반복문 형태로 변환할 수 있다. 예를 들어, 트리 순회나 하노이의 탑 문제를 스택을 통해 구현하면 시스템의 호출 스택 오버플로우 위험을 줄일 수 있다. 깊이 우선 탐색 역시 재귀 또는 스택을 사용하여 구현하는 대표적인 그래프 탐색 알고리즘이다.

스택은 또한 구문 분석 분야에서 핵심적인 역할을 한다. 프로그래밍 언어의 컴파일러는 소스 코드에서 괄호의 짝이 맞는지 검사할 때 스택을 활용한다. 여는 괄호를 만나면 스택에 푸시하고, 닫는 괄호를 만나면 스택에서 팝하여 짝을 맞춰본다. 최종적으로 스택이 비어 있으면 모든 괄호의 짝이 올바른 것이다. 이 원리는 역폴란드 표기법 수식의 계산에도 적용된다. 연산자를 만나면 스택에서 필요한 수의 피연산자를 꺼내 계산하고, 결과를 다시 스택에 넣는 과정을 반복한다.

큐는 선입선출 방식의 데이터 처리 특성을 활용하여 다양한 알고리즘의 핵심 구성 요소로 사용된다. 대표적인 활용 분야는 너비 우선 탐색, 버퍼 관리, 스케줄링 알고리즘 등이다.

너비 우선 탐색은 그래프나 트리 구조에서 같은 깊이의 노드를 모두 탐색한 후 다음 깊이로 넘어가는 알고리즘이다. 시작 노드를 큐에 넣고, 큐에서 노드를 꺼내면서 그 노드의 인접 노드를 다시 큐에 추가하는 과정을 반복한다. 이 과정은 모든 노드를 방문하거나 목표 노드를 찾을 때까지 계속된다. 큐는 탐색해야 할 노드들을 순서대로 저장하고 관리하는 역할을 수행한다[3].

큐는 다익스트라 알고리즘의 변형이나 버퍼 구현에도 필수적이다. 네트워크 패킷 처리, 프린터의 작업 대기열, 운영체제의 프로세스 스케줄링(예: 라운드 로빈 스케줄링)은 모두 작업이나 데이터가 도착한 순서대로 처리되어야 하므로 큐를 사용한다. 또한 캐시 교체 정책 중 하나인 FIFO 알고리즘도 큐의 원리를 적용한 사례이다.

운영체제는 스택과 큐를 핵심 자료구조로 활용하여 시스템 자원을 관리하고 프로세스 실행을 제어한다. 이들은 메모리 할당, 작업 스케줄링, 인터럽트 처리 등 다양한 하위 시스템에서 기본적인 메커니즘을 제공한다.

스택은 주로 함수 호출 관리와 메모리 할당에 사용된다. 각 프로세스는 실행 중인 함수의 복귀 주소, 지역 변수, 매개변수 등을 저장하는 고유한 콜 스택을 가진다. 함수가 호출되면 새로운 스택 프레임이 푸시되고, 함수가 반환되면 해당 프레임이 팝되어 이전 실행 상태로 복귀한다. 또한 스택은 커널 모드와 사용자 모드 간 전환 시 레지스터 상태를 임시 저장하는 데에도 쓰인다.

큐는 프로세스 스케줄링과 입출력 요청 관리의 중심에 있다. 준비 상태의 프로세스들은 일반적으로 준비 큐에 대기하며, 스케줄러는 이 큐에서 특정 알고리즘(예: 라운드 로빈, 선입 선출)에 따라 다음에 실행할 프로세스를 선택한다. 다양한 장치의 입출력 요청도 해당 장치의 입출력 큐에 순서대로 쌓여 처리된다. 네트워크 패킷 처리나 프린터 스풀링도 큐를 통해 순차적 관리를 보장한다.

이러한 자료구조의 사용은 운영체제가 제한된 자원을 공정하고 효율적으로 분배하며, 다중 작업 환경에서 실행의 정확성과 안정성을 유지하는 데 기여한다.

네트워크 통신에서 패킷은 데이터 전송의 기본 단위이다. 이러한 패킷들은 다양한 네트워크 장비와 프로토콜에서 큐 자료구조를 통해 관리된다. 패킷이 라우터나 스위치에 도착하면, 장비는 이를 임시로 저장하는 버퍼에 큐 형태로 쌓아둔다. 그 후, FIFO 방식에 따라 도착한 순서대로 처리하여 다음 목적지로 전송한다. 이 과정은 네트워크의 혼잡을 완화하고 패킷 손실을 방지하는 데 핵심적인 역할을 한다.

특히, 네트워크 트래픽 관리와 QoS 정책 구현에 큐가 광범위하게 활용된다. 예를 들어, 대역폭이 제한된 링크에서는 여러 종류의 트래픽(예: 실시간 음성, 일반 데이터)이 경쟁한다. 네트워크 장비는 우선순위가 다른 여러 개의 큐를 사용하여 패킷을 분류한다. 높은 우선순위를 가진 실시간 패킷은 일반 데이터 패킷보다 먼저 처리되어 지연을 최소화한다. 또한, TCP 프로토콜의 재전송 메커니즘에서도 송신 측과 수신 측 모두 패킷을 큐에 보관하여 순서를 유지하고 손실을 탐지한다.

한편, 스택은 네트워크 프로토콜 스택의 개념적 모델에서 그 원리를 제공한다. OSI 7계층이나 TCP/IP 모델은 각 계층이 독립적인 기능을 수행하며, 데이터가 상위 계층에서 하위 계층으로 내려갈 때(캡슐화) 또는 반대로 올라올 때(역캡슐화) 스택과 유사한 LIFO 방식의 처리 구조를 가진다. 또한, 웹 브라우저의 '뒤로 가기' 기능은 방문한 URL 히스토리를 스택에 저장하여 구현된다. 사용자가 새 페이지를 방문하면 그 주소가 스택에 푸시되고, '뒤로 가기' 버튼을 누르면 가장 최근에 저장된 주소가 팝되어 이전 페이지로 이동한다.

컴파일러는 소스 코드를 기계어로 번역하는 과정에서 스택 자료구조를 광범위하게 활용한다. 대표적인 예는 구문 분석 단계에서 재귀적 하강 파서가 사용하는 호출 스택이다. 이 스택은 함수나 문법 규칙의 호출 기록을 관리하여, 복잡한 문법 구조를 올바르게 해석할 수 있도록 돕는다. 또한, 중위 표기법을 후위 표기법으로 변환하거나 후위 표기법 수식을 계산할 때도 스택이 핵심적인 역할을 수행한다.

컴파일러의 또 다른 핵심 구성 요소인 심볼 테이블 관리에도 스택이 사용된다. 블록 구조를 가진 언어(예: C 언어, 자바)에서 변수나 함수의 유효 범위를 관리할 때, 새로운 블록이 시작되면 스택에 새로운 심볼 테이블 프레임을 푸시하고, 블록이 종료되면 팝하여 이전 범위로 돌아간다. 이를 통해 동일한 이름을 가진 식별자라도 서로 다른 스코프에서 독립적으로 존재할 수 있다.

코드 최적화와 중간 코드 생성 과정에서도 스택과 큐의 개념이 응용된다. 예를 들어, 제어 흐름 그래프 분석이나 레지스터 할당 알고리즘 중 일부는 깊이 우선 탐색이나 너비 우선 탐색을 기반으로 하여, 각각 스택과 큐를 사용한다. 또한, 의존성 분석이나 작업 스케줄링을 위해 위상 정렬 알고리즘을 사용할 때는 진입차수가 0인 노드들을 관리하기 위해 큐를 자주 활용한다.

런타임 환경에서의 메모리 관리도 스택과 밀접한 관련이 있다. 대부분의 언어에서 지역 변수와 함수 호출 정보는 콜 스택에 저장된다. 함수가 호출될 때마다 스택 프레임이 쌓이고, 함수가 반환되면 해당 프레임이 제거되는 방식으로 메모리가 자동으로 관리된다. 이는 힙 메모리 관리와는 구분되는, 스택 자료구조의 원리가 하드웨어와 소프트웨어에 직접 반영된 대표적인 사례이다.