[Data_Structure] Stack / Queue

먹보·2022년 12월 24일

MUK_BO's Data_Structure & Algorithm

목록 보기

6/15

✍️ 스택 (Stack)

스택이란 선형 자료구조의 일종(LINEAR)으로 말 그대로 쌓인다는 뜻으로 데이터가 하나 하나 들어오는 순서대로 쌓인 다는 것이다.

스택에서 가장 중요한 개념은 FILO 와 LIFO 으로 First In Last Out & Last In First Out 먼저 저장된 데이터가 나중에 나오고 마지막에 들어간 데이터가 제일 처음에 나온다라는 의미이다.

⇒ ex) 브라우저: 뒤로 가기 버튼, 설거지: 쌓여가는 그릇과 넣어지는 그릇 순서

📝 스택의 특징

FILO : First In Last Out
LIFO : Last In FIrst Out
스택에서 저장은 push라고 한다.
스택에서 데이터 읽음은 pop이라고 하면 읽음과 동시에 삭제한다.
데이터 접근 : 스택에서는 오로지 가장 맨 위에 있는 요소에만 접근이 가능하다.
빈 스택 : 요소가 비어 있는 스택을 빈 스택이라고 부르는데 빈 스택에서 요소를 제거하려고 하면 언더플로우 에러를 발생 시킨다.

const stack = [];

const element = stack.pop();
if (element === undefined) {
  console.log("Error: Stack underflow");
}

풀 스택 : 스택이 최대 용량에 도달한 경우 풀스택이라고 일컫는데, 만약 이때 요소를 추가하게 되면 오퍼플로우 에러를 발생 시킨다.

const stack = [];
const MAX_CAPACITY = 3;

stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4); 

if (stack.length >= MAX_CAPACITY) {
  console.log("Error: Stack overflow");
}

사실 여기에서는 직접 설정을 했지만, 본래라면 메모리 과부하가 일어나면 자동으로 스택 오버플로우 에러를 일으킨다.

📝 스택의 시간 복잡도

Push : O(1)
Pop : O(1)
Peek : O(1)
탐색 : O(n)

✍️ 큐 (Queue)

큐 도 마찬가지로 선형 자료주고의 일종으로 스택과 반대로 먼저 들어간 데이터가 맨 앞에서 대기하다 먼저 나오게 되는 구조이며 (FIFO : First In First Out) 큐의 종류에는 두 종류가 있다.

📝 Priority Queue

일반적인 큐에 우선순위(PRIORITY)가 부여된 것으로서 저장된 데이터에 순위가 더해진 것이다. 그렇기에 FIFO이 아닌 순위가 더 높은 데이터가 먼저 처리 된다.

⇒ 만약 우선 순위가 동일하다면 삽입된 순서대로 dequeue된다


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

  enqueue(element, priority) {
    let obj = { element: element, priority: priority };
    let inserted = false;
    for (let i = 0; i < this.items.length; i++) {
      if (obj.priority < this.items[i].priority) {
        this.items.splice(i, 0, obj);
        inserted = true;
        break;
      }
    }
    if (!inserted) {
      this.items.push(obj);
    }
  }

  dequeue() {
    return this.items.shift();
  }

  peek() {
    return this.items[0];
  }
}

Priorty Queue를 간단하게 구현해봤다.

📝 Double Ended Queue (Deque)

큐의 양 끝에서 enqueue과 dequeue를 할 수 있는 자료 구조이다.

⇒ ex) 맛집 예약 시스템, OS 프로세스 스케쥴링 시스템, 최근에 방문한 사이트 주소 기록 등에 쓰인다.

class Deque {
  constructor() {
    this.items = [];
  }
  
  addFront(element) {
    this.items.unshift(element);
  }

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

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

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

  peekFront() {
    return this.items[0];
  }

  peekBack() {
    return this.items[this.items.length - 1];
  }
}