[자료구조] 스택(Stack)과 큐(Que)

스택과 큐 자료구조

스택(Stack)

스택이란?

가장 대표적인 선형 자료구조 중에 하나로, 한 문장으로 정리하면 접시를 쌓아둔 더미라고 할 수 있다.

스택의 가장 큰 특징은 가장 나중에 들어온 데이터가 가장 먼저 나가는 후입선출, 즉 LIFO(Last In, First Out) 구조라는 것이다.

새 접시를 위해 올리고(push), 설거지할 때 위에서부터 꺼내는 것(pop)처럼 리스트의 한쪽으로 삽입과 삭제 연산을 수행한다.

동작(주요 연산)

 

• push(x) : 맨 위에 항목 추가
• pop() : 맨 위 항목 제거 후 반환
• peek() / top() : 맨 위 항목 확인(제거하지 않음)
• size() : 스택의 크기 출력
• isEmpty() : 비어있는지 확인

 

시간복잡도

• push, pop, peek 등: O(1) (상수 시간)

스택의 활용

• 실행취소(undo): 최근 작업이 먼저 취소됨 → 스택
• 브라우저 뒤로가기
• 역 문자열 만들기
• 후위 표기법 : 연산자를 연산 대상의 뒤에 쓰는 연산 표기법 (1+2 => 1 2 +)
• 재귀적 알고리즘 : 자신을 정의할 때, 자기 자신 재창조하는 방법
• 괄호 검사(올바른 괄호 짝 맞추기)

간단 구현(배열을 사용)

JavaScript:

class Stack {
  constructor() { this.arr = []; }
  push(x) { this.arr.push(x); }
  pop() { return this.arr.pop(); }      // 만약 비어있으면 undefined
  peek() { return this.arr[this.arr.length-1]; }
  isEmpty() { return this.arr.length === 0; }
}

 

---

큐(Que)

큐란?

큐 역시 스택과 같은 선형 자료구조 중에 하나로, 한 문장으로 정리하면 식당 대기줄라고 할 수 있다.

큐의 특징은 스택과는 반대로 가장 먼저 들어온 데이터가 먼저 나가는 선입선출, 즉 FIFO(First In, First Out) 구조라는 것이다.

식당 대기줄에서 앞에 선 사람이 먼저 서비스를 받고(pop, dequeue), 새 손님이 맨 뒤에 선다(push, enqueue). 큐의 한쪽 끝에서는 삽입 연산이, 반대쪽에서는 삭제 연산이 수행되는 것이다.

동작(주요 연산)

• enqueue(x) 또는 push : 뒤(끝)에 항목 추가
• dequeue() 또는 shift : 앞(머리)에서 항목 제거 후 반환
• peek() / front() : 앞쪽 항목 확인
• isEmpty() : 비어있는지 확인

시간복잡도

• 배열로 naive 구현 시 dequeue가 O(n)일 수 있음(앞에서 빼면 shift 비용).
• 하지만 링 버퍼(circular buffer) 또는 연결 리스트로 구현하면 enqueue/dequeue 모두 O(1).

큐의 활용

• 우선순위의 예약
• 프로세스 관리
• 은행 업무
• 너비 우선 탐색(BFS) 알고리즘

간단 구현(연결 리스트 방식)

JavaScript (간단한 배열 방식 — 실무에선 링버퍼 권장):

class Queue {
  constructor(){ this.arr = []; }
  enqueue(x) { this.arr.push(x); }
  dequeue() { return this.arr.shift(); } // shift는 O(n)
  peek() { return this.arr[0]; }
  isEmpty() { return this.arr.length === 0; }
}

 

---

선형큐(Linear Queue)와 원형큐(Circular Queue)

선형큐(Linear Queue)란?

우리가 보통 일반적은 큐를 얘기할 때의 구조가 선형 큐다. 말 그래도 일직선 형태의 큐로, 쉽게 말하면 끝없이 이어진 줄 서기(사람 계속 추가 가능)이다.

front(꺼낼 위치)와 rear(삽입할 위치)가 일방향으로 이동하는 선입선출 구조인데, 단점은 데이터를 몇 개 빼면 앞부분이 비어 있게 된다. 즉, 메모리 낭비를 발생시킨다.

 

JavaScript 예시

class LinearQueue {
  constructor(size) {
    this.queue = new Array(size);
    this.front = 0;
    this.rear = 0;
    this.maxSize = size;
  }

  enqueue(item) {
    if (this.rear === this.maxSize) {
      console.log("Queue is full");
      return;
    }
    this.queue[this.rear++] = item;
  }

  dequeue() {
    if (this.front === this.rear) {
      console.log("Queue is empty");
      return;
    }
    const item = this.queue[this.front];
    this.queue[this.front++] = null; // 공간 낭비 발생
    return item;
  }

  display() {
    console.log(this.queue);
  }
}

const q = new LinearQueue(5);
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.dequeue();
q.enqueue(40);
q.enqueue(50);
q.enqueue(60); // Queue is full
q.display();

// 결과
Queue is full
[null, 20, 30, 40, 50]

 

※ shift()를 사용할 때 문제점

shift()를 썼을 때 모든 요소를 왼쪽으로 한 칸씩 이동시키므로 메모리 낭비를 일으키는 선형 큐의 단점을 보완하는 것처럼 보이지만, 실제로는 더 비효율적이다. 매번 배열 전체를 복사하는 일이므로 시간복잡도가 O(n) 발생하여 성능상 최악이다.

 

따라서 shift()로 삭제하는 방식 대신 front만 이동하는 포인터 증가 방식이 시간 복잡도 O(1) 발생하여 효율적이다.

---

원형큐(Circular Queue)란?

선형 큐의 "공간 낭비" 단점을 보완헤 배열 끝과 처음을 이어주는 구조로, 배열 끝(rear)까지 갔다면, 앞부분 비어있는 공간을 재활용한다. 즉, 인덱스를 원형(나머지 연산 %)으로 돌려서 사용한다. 비유적으로 말하면 좌석이 5개짜리 회전식 놀이구다. 자리가 다 차면 더 못 타고, 누가 내리면 다시 탈 수 있다. 따라서 원형 큐는 배열 크기가 고정되어야 한다.

class CircularQueue {
  constructor(size) {
    this.queue = new Array(size);
    this.front = 0;
    this.rear = 0;
    this.maxSize = size;
    this.count = 0; // 현재 원소 개수
  }

  enqueue(item) {
    if (this.count === this.maxSize) {
      console.log("Queue is full");
      return;
    }
    this.queue[this.rear] = item;
    this.rear = (this.rear + 1) % this.maxSize; // 원형 이동
    this.count++;
  }

  dequeue() {
    if (this.count === 0) {
      console.log("Queue is empty");
      return;
    }
    const item = this.queue[this.front];
    this.queue[this.front] = null;
    this.front = (this.front + 1) % this.maxSize; // 원형 이동
    this.count--;
    return item;
  }

  display() {
    console.log(this.queue);
  }
}

const cq = new CircularQueue(5);
cq.enqueue(10);
cq.enqueue(20);
cq.enqueue(30);
cq.dequeue();
cq.enqueue(40);
cq.enqueue(50);
cq.enqueue(60); // 들어감 (원형이라 가능)
cq.display();

// 결과
[60, 20, 30, 40, 50]

 

원형 큐는 배열의 끝까지 갔을 때, 다시 처음(인덱스 0)으로 돌아와서 데이터를 넣거나 빼는 구조다. 

% 연산을 써서 배열 길이를 기준으로 순환한다.

rear = (rear + 1) % maxSize;
front = (front + 1) % maxSize;

 

그래서 원형 큐의 배열 길이는 고정이어야 하는데 % maxSize 연산이 원형을 유지하게 해주는데 만약 배열의 길이가 바뀌면 이 수학적 계산이 깨져버린다.

 

---