[알고리즘과 자료구조] 스택과 큐에 대해서 알아보기

📖 '누구나 자료구조와 알고리즘'책을 공부한 내용을 담고 있습니다!

9장 스택과 큐로 간결한 코드 생성

'누구나 자료구조와 알고리즘'책을 통해서 다양한 자료구조에 따른 성능 차이에 대해 배우고 있다. 책을 공부하기 전보다 자료구조에 대해 이해를 바탕으로 효율적인 코드를 고민하게 된다.

이번 장은 자료구조 중 익숙한 '스택'과 '큐'에 대해서 알아보자!

9-1. 스택

'스택(Stack)'이란?
: 후입선출(LIFO, Last In First Out) 방식의 자료 구조로, 가장 마지막에 추가된 요소가 가장 먼저 제거되는 특성을 가진다.

스택은 원소들의 리스트라고 보면 된다. 데이터를 저장하는 방법은 배열과 같지만, 스택은 다음과 같은 3가지 제약이 있다.

1. 데이터는 스택의 끝에만 삽입할 수 있다. (push)

2	6	9	1	4	8
스택의 밑 (bottom)					스택의 위 (top)

2. 데이터는 스택의 끝에서만 삭제할 수 있다. (pop)

스택의 위에서 원소를 제거하는 것을 스택으로부터 팝(POP)한다고 한다. 스택의 제약으로 인해 데이터는 위에서만 팝할 수 있다.

3. 스택의 마지막 원소만 읽을 수 있다. (peek)

스택은 후입선출되는 구조를 갖고 있기 때문에, 마지막으로 들어온 원소가 가장 먼저 나가게 된다.

9-2. 추상 데이터 타입

스택은 프로그래밍 언어에 내장되어 있지 않는다. 스택을 사용하기 위해서 내장 데이터 구조를 사용해서 사용자가 직접 스택을 구현해야 한다. 다음 코드는 배열을 이용해서 스택을 구현한 것이다.

class Stack {
  constructor() {
    this.items = []; // 스택을 저장할 배열
  }

  // 스택에 요소를 추가하는 push 메소드
  push(element) {
    this.items.push(element);
  }

  // 스택에서 가장 위에 있는 요소를 제거하고 반환하는 pop 메소드
  pop() {
    // 스택이 비어있지 않은지 확인
    if (this.items.length == 0) {
      return "Underflow"; // 스택이 비어있으면 Underflow 반환
    }
    return this.items.pop(); // 스택의 마지막 요소를 제거하고 반환
  }

  // 스택이 비어있는지 확인하는 메소드
  isEmpty() {
    return this.items.length == 0;
  }

  // 스택의 가장 위에 있는 요소를 확인하는 메소드
  peek() {
    return this.items[this.items.length - 1];
  }

  // 스택에 저장된 모든 요소를 출력하는 메소드
  printStack() {
    let str = "";
    for (let i = 0; i < this.items.length; i++) {
      str += this.items[i] + " ";
    }
    return str.trim();
  }
}

원래 배열은 인덱스를 사용해서 어떤 값이든 읽을 수 있는데, 스택으로 구현했기 때문에 마지막 항목만 읽을 수 있다.
스택의 LIFO 방식으로 동작하는 리스트를 구현할 수 있다면, 배열로 구현하든 다른 내장 데이터 구조로 구현하든 그건 중요하지 않다. 그렇기 때문에 스택은 추상 데이터 타입에 속한다.

9-3. 스택 다뤄보기

스택은 임시 데이터를 다룰 때 사용하는 알고리즘에 유용하다

자바스크립트 린터(Linter)는 코드를 검사해서 괄호 문법이 올바른지 분석하는 프로그램을 만들어보자.

괄호 문법의 오류 사항
1. 여는 괄호는 있는데 닫는 괄호가 없는 경우
	(var x = 2;
2. 여는 괄호가 없는데 닫는 괄호가 나오는 경우
	var x = 2;)
3. 괄호의 종류가 다른 경우
	(var x = 2;]    

이 3가지 에러를 확인하는 알고리즘을 어떻게 구현할 수 있을까? 스택을 사용해서 린터 알고리리즘을 구현할 수 있다.

1. 괄호가 아닌 모든 문자는 무시하고 넘어간다.
2. 여는 괄호가 나오면 스택에 푸시한다.
3. 닫는 괄호가 나오면 다음을 확인한다.
	3-1. 여는 괄호와 같은 종류가 맞는지, 다르면 문법 오류 3번이다.
    3-2. 스택에 원소가 없어서 POP할 수 없다면 문법 오류 2번이다.
    3-3. 닫는 괄호가 없으면 문법 오류 1번이다.
4. 문자열의 끝에 도달했을 때 스택이 비어 있으면 모든 괄호가 올바르게 닫혔다는 것을 의미한다.

코드 구현: 스택 기반 코드 린터

function isBalancedBrackets(inputString) {
    const stack = [];
    const bracketsMap = {
        ')': '(',
        '}': '{',
        ']': '['
    };

    for (let char of inputString) {
        if (['(', '{', '['].includes(char)) {
            // 여는 괄호일 경우 스택에 푸시
            stack.push(char);
        } else if ([')', '}', ']'].includes(char)) {
            // 닫는 괄호일 경우
            if (stack.length === 0 || stack.pop() !== bracketsMap[char]) {
                // 스택이 비어있거나, 스택의 최상단 요소가 현재 닫는 괄호와 짝이 맞지 않는 경우
                return false;
            }
        }
    }

    // 스택이 비어있다면 모든 괄호가 올바르게 닫혔음을 의미
    return stack.length === 0;
}

* stack.pop()은 JavaScript에서 배열의 마지막 요소를 제거하고 그 요소를 반환하는 메서드

9-4. 제약을 갖는 데이터 구조의 중요성

스택을 배열로 구현한다면, 배열도 스택이 하는 일을 할 수 있지 않을까?

스택처럼 제약을 갖는 데이터 구조가 중요한 이유는

1. 제약을 갖는 데이터 구조를 사용하면 잠재적 버그를 막을 수 있다.
배열의 경우 중간 값도 제거할 수 있기 때문에 잘못 중간 값을 제거하면 린터 알고리즘이 고장난다. 스택의 위에서만 입력하고 삭제 가능한, 제약적인 데이터 덕분에 값을 잘못 처리하는 오류를 줄일 수 있다.

2. 제약을 갖는 데이터 구조는 문제를 해결하는 새로운 사고 모델(Mental Model)을 제공한다.
스택의 특징으로 인해 후입 선출에 입각해 문제를 해결할 수 있다.

스택 요약

스택은 마지막에 들어 온 데이터부터 처리해야 한다. 스택의 훌륭한 활용 사례로 "되돌리기" 함수가 있다. 가장 마지막에 입력한 값을 POP 해서 이전 값으로 돌아갈 수 있다.

9-5. 큐

'큐(Queue)'란?
: 선입선출"(FIFO, First In First Out) 방식의 자료 구조로, 가장 먼저 추가된 요소가 가장 먼저 제거되는 특성을 가진다.

큐 또한 임시 데이터를 처리하기 위해 디자인된 데이터 구조이다. 스택 처럼 추상 데이터 타입이다. 다음은 큐의 세가지 제약 사항이다.

1. 데이터는 큐의 끝에만 삽입할 수 있다. (Enqueue)

2. 데이터는 큐의 앞에서만 삭제할 수 있다. (Dequeue)

3. 큐의 앞에 있는 원소만 읽을 수 있다. (read)

자바스크립트를 사용해 큐(Queue) 구현하기

class Queue {
  constructor() {
    this.items = [];
  }

  // 큐에 요소를 추가하는 메소드
  enqueue(element) {
    this.items.push(element);
  }

  // 큐에서 요소를 제거하고 반환하는 메소드
  dequeue() {
    if(this.isEmpty()) {
      return "Queue is empty";
    }
    return this.items.shift();
  }

  // 큐가 비어있는지 확인하는 메소드
  isEmpty() {
    return this.items.length === 0;
  }

  // 큐의 가장 앞에 있는 요소를 반환하는 메소드
  front() {
    if(this.isEmpty()) {
      return "Queue is empty";
    }
    return this.items[0];
  }

  // 큐에 저장된 모든 요소를 출력하는 메소드
  printQueue() {
    let str = "";
    for(let i = 0; i < this.items.length; i++) {
      str += this.items[i] + " ";
    }
    return str;
  }
}

9-6. 큐 다뤄보기

요약

• 스택(Stack)은 후입선출(LIFO, Last In First Out) 방식으로, 가장 마지막에 추가된 요소가 가장 먼저 제거된다.
• 스택의 주요 연산에는 push (데이터 추가), pop (데이터 제거 및 반환), peek (마지막 요소 조회) 등이 있으며, 웹 브라우저의 뒤로 가기 기능, 함수 호출 스택 등에 활용된다.
• 큐는 선입선출(FIFO, First In First Out) 방식으로, 가장 먼저 추가된 요소가 가장 먼저 제거된다.
• 큐의 주요 연산에는 enqueue (데이터 추가), dequeue (데이터 제거 및 반환), front (첫 번째 요소 조회) 등이 있으며, 메시지 처리 시스템, CPU 작업 스케줄링 등에 적합하다.
• 스택과 큐 모두 추상 데이터 타입으로, 배열 같은 내장 데이터 구조를 사용하여 사용자가 직접 구현해야 한다.

연습문제

1. 전화를 건 사람을 잠시 대기시킨 후 "다음 연결 가능한 통화원"에게 연결해 주는 콜센터 소프트웨어를 작성 중이라면 스택을 쓰겠는가 큐를 쓰겠는가?

• 큐, 전화 온 순서대로 연결해야 되기 때문에 선입선출 방식을 사용하는 큐를 사용하겠다.

2. 1,2,3,4,5,6의 순서대로 스택에 수를 푸시한 후 두 항목을 팝하면 스택에서 어떤 수를 읽는가?

• 4, 스택은 마지막 수부터 POP하고, 마지막 수부터 읽는다.
  6, 5가 차례대로 나가고, 4를 읽는다.

3. 1,2,3,4,5,6의 순서대로 큐에 수를 삽입한 후 두 항목을 다큐하면 큐에서 어떤 수를 읽는가?

• 3, 큐는 앞부터 삭제하고, 앞부터 읽는다. 1,2가 나가고, 3를 읽는다.

4. 스택을 사용해 문자열을 거꾸로 만드는 함수를 작성하라(예를 들어 "abcde"는 "edcba"가 된다.) 앞서 구현했던 스택 클랙스를 사용해도 좋다.

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.items.length == 0) {
      return "Underflow";
    }
    return this.items.pop();
  }

  isEmpty() {
    return this.items.length == 0;
  }
}

function reverseString(inputString) {
  let stack = new Stack();
  // 문자열의 각 문자를 스택에 푸시
  for (let i = 0; i < inputString.length; i++) {
    stack.push(inputString[i]);
  }

  let reversedString = "";
  // 스택이 비어있지 않을 때까지 팝하여 새 문자열 생성
  while (!stack.isEmpty()) {
    reversedString += stack.pop();
  }

  return reversedString;
}

// 함수 사용 예시
console.log(reverseString("abcde")); // "edcba"