(3) Stack, Queue

Stack과 Queue, 뭐가 다를까?

두 자료구조의 핵심 차이는 데이터를 꺼내는 순서이다.

넣는 방식은 동일하지만 꺼내는 방향이 정반대이다.

 

Stack

LIFO(= Last In, First Out) 나중에 넣은 것이 먼저 나온다. 책을 쌓아두고 맨 위부터 꺼내는 것과 같다.

핵심 연산

(1) push - 맨 위의 요소 추가

시간 복잡도 O(1)

(2) pop - 맨  위 요소 제거

시간 복잡도 O(1)

(3) peek - 맨 위 요소 확인 (제거하지 않음)

시간 복잡도 O(1)

(4) isEmpty - 비어있는지 확인.

시간 복잡도 O(1)

 

Stack의 핵심 연산 시간복잡도가 모두 O(1)인 이유는 크기와 상관없이 항상 고정된 위치(Top)만 접근하기 때문이다.

추가로 탐색도, 이동도, 재정렬도 없기 때문에 모두 같은 시간 복잡도를 가지게 된다.

 

Javascript 로 Stack 구현

// ── Stack: 배열 활용 ──────────────────────────────────
// JS 배열은 동적 크기를 지원하므로 Stack으로 완벽히 활용 가능
// push/pop 모두 배열 끝을 사용하므로 진짜 O(1)

const stack = [];

stack.push(1);       // [1]
stack.push(2);       // [1, 2]
stack.push(3);       // [1, 2, 3]

// peek: 마지막 인덱스로 접근
const top = stack[stack.length - 1]; // 3, 제거 안 됨

stack.pop();          // 3 반환 → [1, 2]
stack.pop();          // 2 반환 → [1]

// isEmpty: length 체크
if (stack.length === 0) console.log('비어있음');

 

Stack의 장단점

장점

1. 구현 및 사용의 용이성

JS 배열의 push/pop 만으로 완전한 Stack이 된다. 별도 클래스나 라이브러리가 필요없다.

 

2. 빠른 데이터 처리 속도

데이터 삽입(push)과 삭제(pop)가 항상 맨 뒤(top)에서만 일어나므로 데이터 접근 및 처리 속도가 매우 빠르다.

 

3. 후입선출(LIFO)의 유용성

최신 데이터를 먼처 처리하거나 마지막 작업을 취소하고 이전 상태로 되돌리는 기능 ( ex. Undo 브라우저 뒤로가기 ) 구현에 최적화되어 있다.

 

4. 재귀 알고리즘 구현

함수 호출 시 메모리 관리에 사용되어 재귀 함수나 트리의 깊이 우선 탐색 (DFS)을 구현하는 데 필수적이다.

 

단점

1. 데이터 접근의 제한성

(1) 임의 접근 불가 : 특정 위치의 데이터를 직접 확인하거나 수정할 수 없다.

(2) 순차적 제거 필요 : 중간이나 바닥에 있는 데이터를 꺼내려면 반드시 그 위의 데이터들을 모두 순서대로 먼저 제거해야 한다.

 

2. 메모리 및 크기 관련 문제

(1) 스택 오버 플로우 : 고정된 크기의 배열로 구현할 경우, 할당된 메모리 용량을 초과해 데이터를 삽입하면 오류가 발생한다.

(2) 공간 낭비 : 최대 데이터 개수를 미리 정해주어야 하는 경우, 사용하지 않는 공간까지 점유하게 되어 메모리 효율이 떨어질 수 있다.

 

3. 탐색 및 데이터 처리 효율

(1) 검색 성능 저하 : 특정 데이터를 찾기 위해서는 스택의 모든 요소를 하나씩 꺼내며 확인해야 하므로 검색에 적합하지 않다.

(2) 재귀 호출 제한 : 프로그램 실행시 함수 호출 정보를 저장하는 시스탬 스택의 경우, 호출 깊이가 너무 깊어지면 오류가 발생하게 된다.

 

4. Java 언어적 특성(Stack 클래스)
(1) 설계적 결함: Java의 java.util.Stack 클래스는 Vector를 상속받아 구현되어, 스택의 의도와 달리 중간 데이터 삽입/삭제가 가능해지는 논리적 오류가 발생할 수 있다.
(2) 성능 문제: 동기화 처리가 되어 있어 멀티스레드 환경이 아닌 경우 불필요한 성능 저하를 유발할 수 있다.

 

그럼 Stack은 언제 써야 할까?

1. 작업 되돌리기 및 경로 추적
(1) Undo / Redo:

문서 편집기에서 'Ctrl + Z'를 눌러 직전 작업을 취소할 때, 가장 마지막에 수행한 작업부터 되돌리기 위해 사용한다.

(2) 브라우저 뒤로 가기:

사용자가 방문한 페이지 기록을 스택에 쌓아두고, 뒤로 가기 버튼을 누르면 가장 최근 방문한 페이지부터 순차적으로 보여줄 수 있다.

2. 프로그래밍 및 알고리즘 구현
(1) 함수 호출 관리(Call Stack):

함수 내에서 다른 함수가 호출될 때, 실행 중이던 함수의 상태(복귀 주소, 변수 등)를 저장했다가 호출된 함수가 종료되면 다시 꺼내어 원래 흐름으로 돌아간다.

(2) 재귀(Recursion) 알고리즘:

함수가 자기 자신을 호출할 때 내부적으로 스택 구조를 사용하여 호출 순서를 관리한다.

(3) DFS(깊이 우선 탐색):

그래프 탐색 시 한 경로를 깊게 파고든 후 다시 돌아와야 할 때 사용한다.

3. 문법 검사 및 수식 처리
(1) 괄호 유효성 검사:

코드나 수식에서 ( ), { } 등의 괄호가 올바르게 닫혔는지 확인할 때 사용한다.

(여는 괄호를 스택에 넣고, 닫는 괄호가 나오면 스택에서 꺼내 짝을 맞춤).

(2) 수식 계산(후위 표기법):

중위 표기법(2+3)을 컴퓨터가 계산하기 쉬운 후위 표기법(2 3 +)으로 바꾸거나 계산할 때 활용한다.

 

Queue

FIFO(= First In, First Out) 먼저 넣은 것이 먼저 나온다. 줄 서기 처럼, 먼저 온 순서대로 처리된다.

 

핵심 연산

(1) Enqueue (삽입): 큐의 맨 뒤(Rear)에 새로운 데이터를 추가한다.
(2) Dequeue (삭제): 큐의 맨 앞(Front)에 있는 데이터를 꺼내서 반환한다.
(3) Peek/Front (조회): 데이터를 삭제하지 않고 맨 앞에 무엇이 있는지 확인만 한다.
(4) isEmpty (확인): 큐가 비어있는지 확인하여 에러를 방지한다.

 

이론적으로 큐의 핵심연산의 시간 복잡도는 O(1)이다.

이유는 큐의 동작원리가 "데이터를 옮기는 것"이 아니라 "위치를 가르키는 지점(포인터)만 옮기는 것"을 전제로 하기 때문이다.

큐 구조에서 가장 앞에 있는 데이터의 위치(Front)와 새로운 데이터가 들어올 위치(Rear)를 가르키는 포인터가 있다고 가정했을 때

데이터를 삭제 (Dequeue) 할때 실제 데이터를 삭제한 뒤 나머지 데이터들을 앞으로 당기는 것이 아니라, 

그저 가장 앞에 있는 데이터의 위치를 나타내는 화살표(Front 포인터)를 한 칸 옆으로 옮기기만 하면 된다.

 

이를 비유하자면 맛집 줄서기에서 앞사람이 들어갔을때 뒷 사람들이 모두 무거운 짐을 들고 한 칸식 앞으로 이동하는 것이 아니라,

은행해서 대기 전광판 숫자가 '1번'에서 '2번'으로 바뀌는 것과 같다.

대기실에 앉아있는 사람(=데이터)이 10명이든 1000명이든 은행원이 전광판 숫자를 하나 올리는 데 걸리는 시간은 항상 동일하다.

이처럼 실제로 데이터를 물리적으로 이동시키지 않고 '어디가 앞인지' 가리키는 정보만 수정하기 때문에 큐의 핵심 연산은 데이터의 양에 상관없이 항상 일정한 시간, 즉 O(1)의 속도로 처리될 수 있다. 

 

Javascript 로 Queue 구현

JavaScript에는 별도의 Queue 클래스가 내장되어 있지 않지만, Array 객체를 사용하여 쉽게 구현하고 활용할 수 있다.

const queue = [];

// Enqueue: 데이터 추가
queue.push("Task 1");
queue.push("Task 2");

// Dequeue: 데이터 추출 (가장 먼저 들어온 "Task 1"이 나옴)
const firstTask = queue.shift(); 

console.log(firstTask); // "Task 1"
console.log(queue);    // ["Task 2"]

하지만 여기서 주의할 점이 있다. 위 코드에서 사용한 shitf()메서드는 이론적인 O(1)이 아니라 O(n)의 시간 복잡도를 가진다.

그 이유는 JS의 배열이 내부적으로 '줄서기'방식으로 동작하기 때문이다. shift() 로 맨 앞의 "Task1"을 꺼내는 순간,

배열은 빈자리를 채우기 위해 뒤에 있는 모든 데이터 "Task 2" 등을 한 칸씩 앞으로 당긴다.

결국 데이터가 100만개라면 100만번의 이동이 발생하게 된다. 따라서 JS에서 진정한 의미의 O(1)큐를 구현하려면 배열 메서드에 의존하지 않고 앞서 설명한 포인터 방식을 직접 코드로 구현해야 한다.

 

그렇다면 JS에서 데이터 이동없이 포인터 방식으로 시간복잡도 O(1) 큐를 구현하려면 어떻게 해야할까?

바로 객체 (Object)와 인덱스 카운터를 활용하는 것이다.

 

class Queue {
  constructor() {
    this.items = {}; // 데이터를 저장할 객체
    this.head = 0;   // 전광판: 지금 나갈 차례 (Front 포인터)
    this.tail = 0;   // 전광판: 다음에 들어올 자리 (Rear 포인터)
  }

  // Enqueue: 맨 뒤에 데이터 추가
  enqueue(item) {
    this.items[this.tail] = item;
    this.tail++;
  }

  // Dequeue: 맨 앞의 데이터를 꺼내고 전광판 숫자만 올림
  dequeue() {
    if (this.head === this.tail) return null; // 큐가 비었을 때

    const item = this.items[this.head];
    delete this.items[this.head]; // 데이터 삭제 (다른 데이터 이동 없음!)
    this.head++; // 전광판 숫자 '딸깍' 옮기기
    return item;
  }
}

const myQueue = new Queue();

myQueue.enqueue("Task 1");
// this.items[0] = "Task 1" 가 저장됨. (tail이 0이므로)
// this.tail이 1로 증가
// 결과: { 0: "Task 1" }, head: 0, tail: 1

myQueue.enqueue("Task 2");
// this.items[1] = "Task 2" 가 저장됨. (tail이 1이므로)
// this.tail이 2로 증가
// 결과: { 0: "Task 1", 1: "Task 2" }, head: 0, tail: 2

console.log(myQueue.dequeue()); // "Task 1" (나머지 데이터를 당기지 않음!)
// item = this.items[0] ("Task 1")를 변수에 잠시 담아둠. (head가 0이므로)
// delete this.items[0] 객체에서 0번 데이터를 삭제
// this.head가 1로 증가
// 결과: { 1: "Task 2" }, head: 1, tail: 2 (반환값: "Task 1")
// 여기서 1번에 있는 "B"는 가만히 있고, head 숫자만 1로 바뀌어서 이제 "다음은 1번을 부를 거야"라는 상태가 된 것

 

요약하자면
데이터 추가 시: tail 번호 자리에 데이터를 넣고, tail을 1 키운다.
데이터 삭제 시: head 번호 자리에 있는 걸 꺼내고, head를 1 키운다.
데이터의 이동: 전혀 발생하지 않는다. 오직 head와 tail이라는 숫자(인덱스)만 계속 증가할 뿐이다.
이렇게 숫자를 직접 관리하기 때문에 배열에서 데이터를 앞으로 밀고 당기는 연산(비용)이 사라지게 됩니다. 때문에 시간복잡도 O(1)이 되는것이다.

 

Queue의 장단점

장점

(1) 데이터 처리의 공정성: 

먼저 들어온 순서대로 처리(FIFO)되므로 데이터의 왜곡이나 누락 없이 순차적인 실행을 보장한다.

(2) 효율적인 속도 : 

삽입과 삭제가 매우 빠르다. 데이터가 100만 개여도 맨 앞과 맨 뒤만 건드리기 때문이다.

 

(3) 비동기 시스템 최적화:

데이터가 들어오는 속도와 나가는 속도가 다를 때, 이를 중간에서 조절하는 완충 작용(Buffering)에 탁월하다.

이는 백엔드 시스템의 핵심인 비동기 메시지 처리의 근간이 되기도 한다. 이와 관련하여 시스템 간의 통신을 효율적으로 조절하는 메시지 큐(Message Queue)에 대해서는 추후 별도의 포스팅을 통해 더 자세히 다루어 보려고한다!

 

단점

(1) 중간 데이터 접근 불가:

큐는 오직 맨 앞(Front)과 맨 뒤(Rear)만 관리한다. 중간에 있는 데이터를 확인하거나 수정하는 것이 불가능하며, 이를 하려면 데이터를 다 꺼내야 한다.

(2) 공간 낭비 문제 (배열 구현 시):

일반적인 배열로 구현하고 head 포인터만 옮길 경우, 앞부분에 빈 공간이 생겨 메모리가 낭비될 수 있다.

(이를 해결하기 위해 원형 큐 등을 사용한다.)

큐의 종류에 관해서는 추후 별도의 포스팅으로 다룰 예정입니다!

 

그럼 Queue은 언제 써야 할까?

큐는 주로 "순서가 중요한 대기열"이 필요한 모든 상황에 사용한다.
(1) 순차적인 실행이 필요할 때
프린터 출력 대기열: 먼저 '인쇄'를 누른 문서부터 순서대로 출력한다.
티켓 예매 시스템: 서버에 접속한 순서대로 대기 번호를 부여하고 처리한다.

(2) 서로 다른 속도의 장치/작업을 연결할 때 (버퍼링)
네트워크 패킷 처리: 데이터가 한꺼번에 몰려올 때, 큐에 잠시 담아두고 처리 가능한 속도로 하나씩 꺼내 쓴다.
동영상 스트리밍: 영상을 재생하는 속도보다 데이터를 받아오는 속도가 빠를 때 큐에 미리 저장(버퍼링)해둔다.

 

(3) 알고리즘 구현
BFS (너비 우선 탐색): 가까운 노드부터 차례대로 방문해야 하는 그래프 탐색에서 필수적으로 사용된다.

 

 

---

결국 Stack과 Queue는 "어떻게 꺼내느냐"의 차이에서 시작하지만, 실제로는 사고방식의 차이에 가깝다.

Stack은 가장 최근의 상태를 기준으로 생각한다.

지금 막 했던 작업, 방금 들어온 데이터, 현재의 흐름을 중심으로 움직인다. 그래서 Undo, 재귀, DFS, 괄호 검사처럼 

"되돌아가야 하는 문제"에 강하다.

Queue는 순서를 보존하는 데 집중한다.

먼저 온 것을 먼저 처리해야 하는 시스템, 공정성이 중요한 환경, 처리 속도를 조절해야 하는 비동기 흐름에서 빛을 발한다.

그래서 BFS, 버퍼링, 작업 대기열에 최적이다.

 

문제를 어떻게 바라볼지 결정하는 관점으로 바라보았을때 
“가장 최근 상태부터 되돌려야 하는가?” → Stack
“먼저 온 순서를 보장해야 하는가?” → Queue
이 질문 하나만 정확히 던질 수 있다면 이미 절반은 해결한 것이라고 생각한다.

 

 

 

참고 

https://devuna.tistory.com/22

[자료구조] 스택 (STACK), 큐(QUEUE) 개념/비교 /활용 예시