Stack과 Queue의 차이

🗃️ Stack

stack은 “쌓다”라는 의미로, Last In First Out(LIFO, 후입선출) 구조의 자료구조이다.

스택은 프링글스와 같은 구조라고 생각하면 쉽다. 입구가 하나이기 때문에, 가장 먼저 쌓인 과자가 가장 마지막에 나오게 된다.

Stack	프링글스

스택은 대표적으로 단계적으로 함수를 호출하고 실행할 때 사용한다.

• 요소를 넣은 행위 : push
• 요소를 빼는 행위 : pop
• 맨 위의 요소 : top

👀 스택 코딩테스트 예제

---

프로그래머스 - 올바른 괄호

const solution = (s) => {
  let stack = [];

  for (let x of s) {
    if (x === "(") {
      stack.push(x);
    } else {
      if (stack.length === 0) {
        // 왼쪽, 오른쪽 괄호의 수가 맞지 않아도 false
        return false;
      }
      stack.pop();
    }
  }
  // 모든 원소를 다 돌고 stack에 아무것도 남아있지 않으면 모든 괄호에 대해 짝이 맞다는 것!
  return stack.length === 0;
};

console.log(solution("()()")); // true
console.log(solution("(())()")); // true
console.log(solution(")()(")); // false
console.log(solution("(()(")); // false
console.log(solution("(()))))")); // false
console.log(solution("())(()")); // false

※ 그 밖의 스택 사례 : 웹 브라우저 방문 기록 등

👉 Queue

First In First Out(FIFO, 선입선출) 구조의 자료 구조이다.

Queue	휴지심

• 삭제 연산이 수행되는 곳 : 프론트(front)
• 삽입 연산이 이루어지는 곳 : 리어(rear)
• 리어(rear)에서 이루어지는 삽입 연산 : 인큐(enqueue)
• 프론트(front)에서 이루어지는 삭제 연산 : 디큐(dequeue)

👀 큐 코딩테스트 예제

---

프로그래머스 - 이중우선순위큐

const solution = (operations) => {
  let queue = [];

  for (op of operations) {
    const [char, n] = op.split(" ");
    const num = Number(n);

    switch (char) {
      case "I":
        queue.push(num);
        queue.sort((a, b) => a - b);
        break;
      case "D":
        // "D 1" : 최대값 삭제
        if (num === 1) queue.pop();
        // "D -1" : 최소값 삭제
        else queue.shift();
        break;
    }
  }
  return queue.length === 0 ? [0, 0] : [queue.at(-1), queue.at(0)];
};

console.log(
  solution(["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]),
); // [0,0]
console.log(
  solution([
    "I -45",
    "I 653",
    "D 1",
    "I -642",
    "I 45",
    "I 97",
    "D 1",
    "D -1",
    "I 333",
  ]),
); // [333, -45]
console.log(solution(["I 7", "I 5", "I -5", "D -1"])); // [7, 5]

※ 그 밖의 큐 사례 : 서비스 센터의 대기시간

---

※ 이미지 출처 : 이선협 강사님 데브코스