Skip to main content

06. 자료구조(스택, 큐)

자료구조(스택, 큐)​

stack & queue & deque

스택(Stack)​

스택(stack)이란 쌓아 올린다는 것을 의미한다. 따라서 스택 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다.

스택(위의 사진에서 왼쪽)은 Top으로 정한 곳으로 들어가 Top으로 나간다.

스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가지게 된다.

이러한 스택의 구조를 후입선출(LIFO, Last-In-First-Out) 구조라고 한다.

큐(Queue)​

큐(Queue)는 줄을 서서 기다리는 것을 의미한다. 따라서 큐 자료구조라는 것은 마치 선착순 줄을 서는 것과 같이 차례대로 적재하는 자료구조를 말한다.

큐(위의 사진에서 가운데)는 Bottom에서 들어와 Top으로 나간다.

따라서 일상생활에서 놀이동산에서 줄을 서서 기다리는 것, 은행에서 먼저 온 사람의 업무를 창구에서 처리하는 것과 같이 이러한 큐의 구조를 선입선출(FIFO, First in first out) 구조라고 한다.

데크(Deque)​

스택(Stack)과 큐(Queue)가 결합한 자료구조 양쪽 끝에서 삽입, 삭제 가능하다.

문제 풀이​

Ch.06 - 01. 올바른 괄호​

function solution(braketStr: string): "YES" | "NO" {
  if (braketStr.length % 2 === 1) return "NO";

  const braketStack: Array<string> = [];

  for (const bracket of braketStr) {
    if (bracket === "(") braketStack.push(bracket);
    else if (braketStack.pop() !== "(") return "NO";
  }

  return braketStack.length === 0 ? "YES" : "NO";
}

Ch.06 - 02. 괄호문자제거​

function solution(str: string): string {
  let answer: string = "";

  const stack: Array<string> = [];
  for (const char of str) {
    if (char === "(") stack.push(char);
    else if (char === ")") stack.pop();
    else if (stack.length === 0) answer += char;
  }

  return answer;
}

Ch.06 - 03. 크레인 인형뽑기(카카오 기출)​

function solution(board: Array<Array<number>>, moves: Array<number>): number {
  let answer: number = 0;

  const catchDollStack: Array<number> = [];
  moves.forEach((movePointer) => {
    for (let i = 0; i < board.length; i++) {
      const curCatchDoll: number = board[i][movePointer - 1] || 0;

      if (curCatchDoll) {
        board[i][movePointer - 1] = 0;

        if (curCatchDoll === catchDollStack.at(-1)) {
          catchDollStack.pop();
          answer += 2;
        } else catchDollStack.push(curCatchDoll);

        break;
      }
    }
  });

  return answer;
}

Ch.06 - 04. 후위식 연산(postfix)​

function solution(str: string): number {
  const stack: Array<number> = [];
  for (const tmp of str) {
    const tempNum: number = Number.parseInt(tmp, 10);

    if (Number.isInteger(tempNum)) {
      stack.push(tempNum);
    } else {
      const rightVal: number = stack.pop();
      const leftVal: number = stack.pop();

      switch (tmp) {
        case "+":
          stack.push(leftVal + rightVal);
          break;
        case "-":
          stack.push(leftVal - rightVal);
          break;
        case "*":
          stack.push(leftVal * rightVal);
          break;
        case "/":
          stack.push(leftVal / rightVal);
          break;

        default:
          break;
      }
    }
  }

  return stack[0];
}

Ch.06 - 05. 쇠막대기​

function solution(str: string): number {
  let answer = 0;
  const stack: Array<string> = [];

  for (let i = 0; i < str.length; i++) {
    const braket: string = str[i];

    if (braket === "(") stack.push(braket);
    else {
      stack.pop();

      if (str[i - 1] === "(") answer += stack.length;
      else answer++;
    }
  }

  return answer;
}

Ch.06 - 06. 공주 구하기​

function solution(n: number, m: number): number {
  const queue: Array<number> = Array.from({ length: n }, (_, i) => i + 1);

  while (1 < queue.length) {
    for (let i = 1; i < m; i++) queue.push(queue.shift());
    queue.shift();
  }

  return queue[0];
}

Ch.06 - 07. 교육과정 설계​

function solution(mySchedule: string, classSchedule: string): "YES" | "NO" {
  const queue: Array<string> = mySchedule.split("");

  for (const curLecture of classSchedule) {
    if (curLecture === queue[0]) queue.shift();
  }

  return queue.length === 0 ? "YES" : "NO";
}

참고​