[자료구조] 스택과 큐 Stack vs Queue

 

스택은 “쌓다”라는 의미로, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조이다. 위 사진과 같이 데이터가 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조를 가지고 있다. 또한, 스택은 정해진 방향으로만 쌓을 수 있으며, top으로 정한 곳을 통해서만 접근 가능하다. 새로 넣는 자료 혹은 삭제할 때도 top이 가르키는 가장 맨 위에서 진행된다.

용어

• top(peek) : 가장 최근에 저장된 데이터 / 가장 먼저 삭제 될 데이터
• push : 데이터를 삽입하는 것, 삽입 된 데이터는 삭제시 가장 먼저 삭제 될 데이터가 된다
• pop : 데이터를 삭제할 때 사용, 가장 최근에 저장된 데이타가 삭제된다

활용 예시

• 웹 브라우저 방문기록(뒤로가기) : 가장 나중에 열린 페이지부터 다시 보여준다
• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다
• 실행 취소(Undo / Ctrl+z) : 가장 나중에 실행된 것부터 실행을 취소한다
• 재귀 함수
• 종이컵 : 쌓아놓고 쓸 때 가장 나중에 쌓아놓은 종이컵을 먼저 사용한다

간단한 코드 예시

function createStack() {
  const items = [];

  // 스택에 요소 추가
  function push(element) {
    items.push(element);
  }

  // 스택에서 요소 제거 후 반환
  function pop() {
    if (isEmpty()) {
      return "스택이 비어 있습니다.";
    }
    return items.pop();
  }

  // 스택의 가장 상단 요소 반환
  function peek() {
    return items[items.length - 1];
  }

  // 스택이 비어 있는지 확인
  function isEmpty() {
    return items.length === 0;
  }

  // 스택의 크기 반환
  function size() {
    return items.length;
  }

  // 스택 내용을 문자열로 반환
  function print() {
    return items.toString();
  }

  return {
    push,
    pop,
    peek,
    isEmpty,
    size,
    print
  };
}

// 스택 사용 예시
const stack = createStack();
console.log(stack.isEmpty()); // true 출력

stack.push(10);
stack.push(20);
stack.push(30);

console.log(stack.print()); // "10,20,30" 출력
console.log(stack.size()); // 3 출력
console.log(stack.isEmpty()); // false 출력
console.log(stack.peek()); // 30 출력

console.log(stack.pop()); // 30 출력
console.log(stack.print()); // "10,20" 출력

시간 복잡도

삽입과 삭제시에 O(1), 탐색에는 O(n)

요약

• 스택은 가장 마지막에 저장된 데이터가 가장 먼저 삭제되는 후입선출(LIFO, Last In First Out) 구조이다.
• 스택은 한쪽 방향에서만 데이터의 삽입과 삭제가 가능하다
• 스택에서 자료를 삽입할 때나 삭제할 때도 top을 통해서만 가능하다
• push는 삽입 pop은 삭제하는 연산이다

비어있는 스택에서 원소를 추출할려고 하면 stack underflow
스택이 넘치는 경우 stack overflow
(개발자 친구인 stack overflow 사이트가 여기서 유래 됐다)

 

---

 

큐(Queue)는 스택과 정 반대로 가장 먼저 들어온 것이 가장 먼저 나가는 선입선출, FIFO(First In First Out)의 구조를 가지고 있다. 즉, 한 쪽에서는 데이터 삽입, 다른 한 쪽에서는 데이터의 삭제만 가능한 구조이다. 삭제 연산이 수행되는 곳을 Front, 삽입 연산이 이루어지는 곳이 Rear라고 부르고 Rear에서 이루어지는 삽입 연산을 인큐(Enqueue)라고 부르며, Front에서 이루어지는 삭제 연산을 디큐(Dequeue)라고 부른다.

용어

• Enqueue : 큐에 데이터 삽입
• Dequeue(Shift) : 큐에 데이터 삭제
• Peek: 가장 앞의 요소를 반환
• Front : Dequeue시 삭제되는 데이터(가장 먼저 저장된 데이터)를 가르킨다
• Rear : 추가될 새로운 요소의 위치를 가르킨다

활용 예시

• BFS 알고리즘
• 프로세스 관리(콜백 큐)
• 프린터의 대기열
• 은행 업무
• 서비스 센터의 대기시간

간단한 코드 예시

function createQueue() {
  const items = [];

  // 큐에 요소 추가
  function enqueue(element) {
    items.push(element);
  }

  // 큐에서 요소 제거 후 반환
  function dequeue() {
    if (isEmpty()) {
      return "큐가 비어 있습니다.";
    }
    return items.shift();
  }

  // 큐의 첫 번째 요소 반환
  function peek() {
    return items[0];
  }

  // 큐가 비어 있는지 확인
  function isEmpty() {
    return items.length === 0;
  }

  // 큐의 크기 반환
  function size() {
    return items.length;
  }

  // 큐 내용을 문자열로 반환
  function print() {
    return items.toString();
  }

  return {
    enqueue,
    dequeue,
    peek,
    isEmpty,
    size,
    print
  };
}

// 큐 사용 예시
const queue = createQueue();
console.log(queue.isEmpty()); // true 출력

queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);

console.log(queue.print()); // "10,20,30" 출력
console.log(queue.size()); // 3 출력
console.log(queue.isEmpty()); // false 출력
console.log(queue.peek()); // 10 출력

console.log(queue.dequeue()); // 10 출력
console.log(queue.print()); // "20,30" 출력

시간 복잡도

스택과 마찬가지로 삽입과 삭제시에 O(1), 탐색에는 O(n)

 

---

심화

우선순위 큐(Priority Queue)

출처 : https://velog.io/@sisofiy626/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-2.-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue-%EB%8D%B1Deque

 

우선순위 큐의 각 요소는 값(data)과 우선순위(priority), 총 2개의 데이터를 가지고 있다. 즉, 선형 큐와는 달리 우선순위가 높은 요소일수록 먼저 삭제되는 특징을 가지고 있으며 우선 순위가 같은 데이터일 경우 삽입 순서를 따른다.

 

삽입 및 삭제 시 우선 순위에 따라 요소들을 정렬 해야하기 때문에 주로 힙(Heap)이라는 자료구조로 구현되며 실행활에서 병원의 응급실에서는 응급 환자가 우선 순위가 높으므로 먼저 진료를 받고 일반 환자는 순서가 뒤로 밀리는 것과 같은 맥락이다.

간단한 코드 예시

function createPriorityQueue() {
  const items = [];

  // 우선순위와 함께 요소 추가
  function enqueue(element, priority) {
    const queueElement = { element, priority };
    let added = false;
    for (let i = 0; i < items.length; i++) {
      if (queueElement.priority < items[i].priority) {
        items.splice(i, 0, queueElement);
        added = true;
        break;
      }
    }
    if (!added) {
      items.push(queueElement);
    }
  }

  // 가장 우선순위가 높은 요소 제거 후 반환
  function dequeue() {
    if (isEmpty()) {
      return "우선순위 큐가 비어 있습니다.";
    }
    return items.shift().element;
  }

  // 우선순위 큐가 비어 있는지 확인
  function isEmpty() {
    return items.length === 0;
  }

  // 우선순위 큐의 크기 반환
  function size() {
    return items.length;
  }

  // 우선순위 큐 내용을 문자열로 반환
  function print() {
    let result = '';
    for (let i = 0; i < items.length; i++) {
      result += `${items[i].element} - ${items[i].priority}`;
      if (i !== items.length - 1) {
        result += ', ';
      }
    }
    return result;
  }

  return {
    enqueue,
    dequeue,
    isEmpty,
    size,
    print
  };
}

// 우선순위 큐 사용 예시
const priorityQueue = createPriorityQueue();
priorityQueue.enqueue('A', 2);
priorityQueue.enqueue('B', 3);
priorityQueue.enqueue('C', 1);

console.log(priorityQueue.print()); // "C - 1, A - 2, B - 3" 출력

console.log(priorityQueue.dequeue()); // "C" 출력
console.log(priorityQueue.print()); // "A - 2, B - 3" 출력

시간 복잡도

• 어떻게 구현하느냐에 따라 달라진다

힙을 기준으로 삽입과 삭제시에 O(logn), 우선순위가 가장 높은 요소를 탐색할 때는 O(1)

원형 큐 (= 환형 큐, Circular Queue, Ring Buffer)

 

출처 : https://velog.io/@sisofiy626/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-2.-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue-%EB%8D%B1Deque

 

원형 큐는 선형 큐의 단점을 보완하기 위해 나왔다. 큐는 사이즈가 고정되어 있고 데이터의 삽입과 삭제 시 나머지 요소들은 이동하지 않는다. 즉, 데이터의 삽입과 삭제가 반복되면 언젠가 Rear는 큐의 마지막 인덱스를 가르키게 되고 이전에 삭제 작업을 진행하여 앞에 빈 공간이 있더라도 활용하지 못한다.

출처 : https://velog.io/@sisofiy626/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-2.-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue-%EB%8D%B1Deque

 

- 선형 큐는 이러한 빈 공간을 활용하기 위해 현재 요소들을 앞으로 재배치하는 별도의 작업이 필요하다

 

출처 : https://velog.io/@sisofiy626/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-2.-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue-%EB%8D%B1Deque

 

- 반대로 원형큐는 Front와 Rear가 그림처럼 순환하기 때문에 빈 공간을 사용하기 위한 별도의 작업이 필요하지 않는다.

 

간단한 코드 예시

function createCircularQueue(capacity) {
  const items = new Array(capacity);
  let front = 0;
  let rear = 0;
  let size = 0;

  // 큐에 요소 추가
  function enqueue(element) {
    if (isFull()) {
      return "원형 큐가 가득 찼습니다.";
    }
    items[rear] = element;
    rear = (rear + 1) % capacity;
    size++;
  }

  // 큐에서 요소 제거 후 반환
  function dequeue() {
    if (isEmpty()) {
      return "원형 큐가 비어 있습니다.";
    }
    const element = items[front];
    items[front] = undefined; // 요소 제거
    front = (front + 1) % capacity;
    size--;
    return element;
  }

  // 큐의 첫 번째 요소 반환
  function peek() {
    return items[front];
  }

  // 큐가 비어 있는지 확인
  function isEmpty() {
    return size === 0;
  }

  // 큐가 가득 찼는지 확인
  function isFull() {
    return size === capacity;
  }

  // 큐의 크기 반환
  function getSize() {
    return size;
  }

  // 큐 내용을 문자열로 반환
  function print() {
    let result = '';
    for (let i = front; i < front + size; i++) {
      result += `${items[i % capacity]}`;
      if (i !== front + size - 1) {
        result += ', ';
      }
    }
    return result;
  }

  return {
    enqueue,
    dequeue,
    peek,
    isEmpty,
    isFull,
    getSize,
    print
  };
}

// 원형 큐 사용 예시
const circularQueue = createCircularQueue(5);
circularQueue.enqueue('A');
circularQueue.enqueue('B');
circularQueue.enqueue('C');
circularQueue.enqueue('D');

console.log(circularQueue.print()); // "A, B, C, D" 출력

console.log(circularQueue.dequeue()); // "A" 출력
console.log(circularQueue.print()); // "B, C, D" 출력

circularQueue.enqueue('E');
circularQueue.enqueue('F');

console.log(circularQueue.print()); // "B, C, D, E, F" 출력

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

// 원형 큐에서는 배열의 마지막 요소 다음에 첫 번째 요소가 온다고 가정, 배열의 끝과 시작을 연결하여 원형으로 관리
// front를 한 칸 앞으로 이동시킨 후, 큐의 최대 용량(capacity)로 나눈 나머지를 취하는 것을 의미
// front 포인터가 배열의 끝에 도달하면 다시 배열의 시작으로 이동하여 원형 구조를 유지할 수 있다

• 좀 더 쉽게 예를 들면, 큐의 전체 사이즈가 5이고 현재 Rear가 마지막 인덱스 4를 가르킨다고 한다면, 인덱스는 5가 될텐데 여기에 큐의 전체사이즈를 나눈 나머지를 구하는 것이다. 5 % 5 = 0이므로 이 값을 Rear에 할당하여 인덱스가 다시 0을 가리키게 하는 것

덱 (Deque, Double-ended Queue)

출처 : https://velog.io/@sisofiy626/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-2.-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue-%EB%8D%B1Deque

 

덱은 큐 2개를 겹쳐 놓은 것과 같기 때문에 Double ended Queue라고 부르며 Deque이라는 명칭은 이를 축약형으로 부르는 것이다.

 

덱은 이름처럼 양쪽에서 데이터의 입, 출력(삽입과 삭제)이 모두 가능한 자료구조이다

 

스택, 큐와 마찬가지로 front와 rear라는 포인터가 있으며 이들은 각각 가장 앞, 뒤에 있는 데이터를 가르킨다. 다만, 스택과 큐의 Rear는 다음 요소가 삽입 될 위치를 가르키는 반면 덱의 Rear는 마지막 요소를 가르키고 있게 된다.

간단한 코드 예시

function createDeque() {
  const deque = [];

  // 덱의 앞쪽에 요소 추가
  function addFront(element) {
    deque.unshift(element);
  }

  // 덱의 뒤쪽에 요소 추가
  function addRear(element) {
    deque.push(element);
  }

  // 덱의 앞쪽에서 요소 제거 후 반환
  function removeFront() {
    if (isEmpty()) {
      return "덱이 비어 있습니다.";
    }
    return deque.shift();
  }

  // 덱의 뒤쪽에서 요소 제거 후 반환
  function removeRear() {
    if (isEmpty()) {
      return "덱이 비어 있습니다.";
    }
    return deque.pop();
  }

  // 덱의 첫 번째 요소 반환
  function peekFront() {
    return deque[0];
  }

  // 덱의 마지막 요소 반환
  function peekRear() {
    return deque[deque.length - 1];
  }

  // 덱이 비어 있는지 확인
  function isEmpty() {
    return deque.length === 0;
  }

  // 덱의 크기 반환
  function size() {
    return deque.length;
  }

  // 덱 내용을 문자열로 반환
  function print() {
    return deque.toString();
  }

  return {
    addFront,
    addRear,
    removeFront,
    removeRear,
    peekFront,
    peekRear,
    isEmpty,
    size,
    print
  };
}

// 덱 사용 예시
const deque = createDeque();
deque.addFront(10);
deque.addRear(20);
deque.addFront(5);

console.log(deque.print()); // "5, 10, 20" 출력

console.log(deque.removeFront()); // 5 출력
console.log(deque.removeRear()); // 20 출력

console.log(deque.print()); // "10" 출력

 

요약

• 큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.
• 큐는 들어올 때, rear로 들어오지만 나올때는 front부터 빠지는 특성
• 접근 방법은 가장 첫 원소와 끝 원소로만 가능
• 큐에서 프론트 원소는 가장 먼저 큐에 들어왔던 첫 번째 원소가 되는 것이며, 리어 원소는 가장 늦게 큐에 들어온 마지막 원소가 되는 것이다.
• 가장 먼저 들어온 프론트 원소가 가장 먼저 삭제된다.
• 우선순위 큐는 각 항목에 우선순위를 부여하여, 우선순위가 높은 항목이 먼저 제거되는 자료구조
• 원형 큐는 고정된 크기의 버퍼를 가지며, 큐의 끝에 도달하면 다시 처음으로 돌아가는 특징을 가지고 있다
• 덱은 양쪽 긑에서 삽입과 삭제가 모두 가능한 자료구조로 Double-ended Queue의 줄임말이다

 

 

 

 

 

Reference

• 누구나 자료구조와 알고리즘, 제이엔그로우
• https://velog.io/@sisofiy626/자료구조-2.-스택Stack과-큐Queue-덱Deque
• https://jud00.tistory.com/entry/자료구조-스택Stack과-큐Queue에-대해서-알아보자
• https://devuna.tistory.com/22
• https://velog.io/@wlwl99/스택Stack-큐Queue