Skip to content

Latest commit

 

History

History
229 lines (172 loc) · 8.02 KB

스택과큐.md

File metadata and controls

229 lines (172 loc) · 8.02 KB
Raw

image

자료구조에서 스택과 큐는 가장 기본적인 개념이다. 이 개념을 포함하는 또 다른 자료구조인 DFS 는 스택을 활용하고, BFS 는 큐를 활용한다.

간략하게 말하면 스택(Stack)은 나중에 넣은 데이터가 먼저 나오는 형태, 큐(Queue)는 먼저 넣은 데이터가 먼저 나오는 형태이다. 참고로 덱(Deque)은 스택과 큐를 합친 형태이다.

✨ Stack

스택이란 쌓아올린다는 것을 의미하며, 스택 자료구조는 객체들의 집합소이며, 마치 책을 올리듯이 차곡차곡 쌓아서 데이터를 기록하는 자료구조이다.

LIFO

LIFO Last In First Out 마지막에 들어온 자료가 첫번째로 나가는 방식인 후입 선출을 사용하고 있다.

특징

  1. 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있다

  2. Top으로 정한 곳으로만 접근 가능하다. 최상단에는 가장 마지막에 들어온 자료가 위치하며, 이에 대한 삭제 역시, Top에서만 가능하다

  3. 최상단에 삽입하는 연산을 push라고 하며, 최상단에 삭제하는 연산을 pop이라고 한다

❗️ Stack Overflow ❗️

코드를 짜다가 스택오버플로우라는 에러를 많이 접했을 것이다.

이것은 말 그대로, 스택이라는 정해진 크기에 무언가를 계속 넣고 있다가 스택이 받아들일 수 있는 크기를 초과해서 흘러넘쳐버린 것을 의미한다.

위의 상황처럼 춤을 미친듯이 추는 로직을 구현했을 때, 무대라는 공간 stack의 범위를 벗어나면 stack overflow라는 오류를 발생시키는 것이다.

흔히, 재귀함수를 호출할 때 많이 발생한다.

따라서 스택이라는 것을 정리하면, 가장 마지막에 들어온 자료가 가장 먼저 삭제되는 구조라고 이해하면 된다.

활용 예시

스택의 가장 큰 특징인 후입선출을 활용하는 예시이다

  • 웹 브라우저 방문 기록(뒤로가기) 가장 나중에 열린 페이지부터 다시 보여준다.

  • 역순 문자열 만들기 가장 나중에 입력된 문자부터 출력한다.

  • 실행 취소 가장 나중에 실행된 것부터 실행을 취소한다.

  • 후위 표기법 계산

  • 수식의 괄호검사

JavaScript 코드

class Stack {
  constructor() {
    this.arr = [];
    this.index = 0;
  }
  push(item) {
    this.arr[this.index++] = item;
  }
  pop() {
    if (this.index <= 0) return null;
    else {
      const result = this.arr[--this.index];
      return result;
    }
  }
}
let stack = new Stack();
stack.push(1); // arr : [1}, index : 1
stack.push(2); // arr: [1, 2], index: 2
stack.push(3); // arr: [1, 2, 3], index: 3
console.log(stack.pop()); // 3 , index: 2
console.log(stack.pop()); // 2 , index: 1
console.log(stack.pop()); // 1 , index: 0
console.log(stack.pop()); // null

✨ Queue

큐는 단순히 스택의 반대 개념을 갖는다. 큐의 사전적 의미를 살펴보면 '무엇을 기다리는 사람의 줄' 또는 '줄을 서서 기다리는 것' 을 의미한다.

FIFO

FIFO First In First Out 처음 들어온 자료가 첫번째로 나가는 방식인 선입 선출을 사용하고 있다. 앞서 살펴본 정해진 위치인 top에서만 자료 작업이 이루어지는 스택과 달리, 큐는 앞에서는 삭제가, 뒤쪽에서는 삽입의 작업이 양쪽으로 진행된다

슈퍼에 가서 물건을 계산하기 위해 줄을 서고, 차례대로 계산을 진행할 수 있는 상황이라고 이해하면 편하다.

때문에, 큐는 순서를 보장하고 싶은 상황에 사용하는 것이 적절하다.

특징

  1. 삭제가 이루어지는 곳을 front(앞), 삽입이 이루어지는 곳을 rear(뒤)

  2. 큐의 front에서 작업을 넣는 것을 dequeue, 큐의 rear에서 작업을 꺼내는 것을 enqueue라고 한다.

즉, 큐의 front 원소는 가장 먼저 큐에 들어왔던 자료가 되는 것이며 rear 원소는 가장 마지막에 큐에 들어왔던 자료라고 볼 수 있다.

활용 예시

큐는 시간순서대로 작업을 처리할 때 사용하는 것이 좋다

  • 은행 업무
  • 프로세스 관리
  • 캐시 구현
  • BFS

JavaScript 코드

class Queue {
  constructor() {
    this.arr = [];
    this.head = 0;
    this.tail = 0;
  }
  enqueue(item) {
    this.arr[this.tail++] = item;
  }
  dequeue() {
    if (this.head >= this.tail) return null;
    else {
      const result = this.arr[this.head++];
      return result;
    }
  }
}
let queue = new Queue();
queue.enqueue(1); // arr: [1] head: 0 tail: 1
queue.enqueue(2); // arr: [1, 2] head: 0 tail: 2
queue.enqueue(3); // arr: [1, 2, 3] head: 0 tail: 3
console.log(queue.dequeue()); // 1 , head: 1 tail: 3
console.log(queue.dequeue()); // 2 , // head: 2 tail: 3
console.log(queue.dequeue()); // 3 , // head: 3 tail: 3
console.log(queue.dequeue()); // null , // head: 3 tail: 3

✨ Deque

double-ended queue 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조이다. 큐와 스택을 합친 형태이며, 두 개의 포인터를 사용한다.

JavaScript 코드

class Deque {
  constructor() {
    this.arr = [];
    this.head = 0;
    this.tail = 0;
  }
  pushFront(item) {
    if (this.arr[0]) {
      for (let i = this.arr.length; i > 0; i -= 1) {
        this.arr[i] = this.arr[i - 1];
      }
    }
    this.arr[this.head] = item;
    this.tail++;
  }
  pushBack(item) {
    this.arr[this.tail++] = item;
  }
  popFront() {
    if (this.head >= this.tail) return null;
    else {
      const result = this.arr[this.head++];
      return result;
    }
  }
  popBack() {
    if (this.head >= this.tail) return null;
    else {
      const result = this.arr[--this.tail];
      return result;
    }
  }
}

let deque = new Deque();
deque.pushFront(1); // arr: [1] head: 0 tail: 1
deque.pushFront(2); // arr: [2, 1] head: 0 tail: 2

console.log(deque.popFront()); // 2, head: 1 tail: 2
deque.pushFront(3); // arr: [2, 3, 1] head: 1 tail: 3

console.log(deque.popFront()); // 3, head: 2 tail: 3
console.log(deque.popFront()); // 1, head: 3 tail: 3
console.log(deque.popFront()); // null

deque.pushBack(5); // arr: [5] head: 3 tail: 4
// 실제 배열 출력은 arr: [2, 3, 1, 5] 이지만 배열 요소 2, 3, 1은 popFront()를 하였기에 shift()가 된 요소로 생각할 수 있다.

console.log(deque.popBack()); // 5, head: 3 tail: 3
console.log(deque.popBack()); // null

deque.pushBack(6); // arr: [6] head: 3 tail: 4
// 실제 배열 출력은 arr: [2, 3, 1, 6] 이지만 배열 요소 2, 3, 1 은 popFront()를 하였기에 shift()가 된 요소로, 배열 요소 5는 popBack()을 실행해서 pop()가 된 요소로 생각할 수 있다.

deque.pushFront(9); // arr: [9, 6] head: 3 tail: 5

📚 학습할 때, 참고한 자료 📚