자료구조 스택, 큐

자료구조 스택, 큐

스택(stack)

스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 후입선출(LIFO, Last In First Out)을 가진 자료구조이다.
재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰인다.

시간복잡도

• n 번째 참조 : O(n)
• 가장 앞 부분 참조 : O(1)
• 탐색 : O(n)
• 삽입 / 삭제(n번째 제외) : O(1)

JavaScript로 구현하기

class Stack {
  top = null;
  count = 0;
    
  push(data) {
    const node = new Node(data);
    node.next = this.top;
    this.top = node;
    return ++this.count;
  }
    
  pop() {
    if (!this.top) { // stack underflow 방지
      return false;
    }
    const data = this.top.data;
    this.top = this.top.next;
    // 예전 this.top의 메모리 정리
    this.count--;
    return data;
  }

  stackTop() {
    return this.top.data;
  }
}

class Node {
  next = null;
  constructor(data) {
    this.data = data;
  }
}

* stack overflow 와 stack underflow란
각각 주어진 스택 메모리보다 데이터를 더 넣거나,
스택 메모리가 비어있는데 데이터를 꺼내려 했을 때
발생하는 에러이다.

실습

입 출력 조건

// 1 X: 정수 X를 스택에 넣는다. (1 ≤ X ≤ 100,000)
// 2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
// 3: 스택에 들어있는 정수의 개수를 출력한다.
// 4: 스택이 비어있으면 1, 아니면 0을 출력한다.
// 5: 스택에 정수가 있다면 맨 위의 정수를 출력한다. 없다면 -1을 대신 출력한다.

큐(queue)

큐는 먼저 집어넣은 데이터가 먼저 나오는 선입선출(FIFO, First In First Oute)을 지닌 자료구조이다
CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비우선 탐색, 캐시 등에 사용된다.

시간 복잡도

• n번째 참조 : O(n)
• 가장 앞부분 참자 : O(1)
• 탐색 : O(n)
• 삽입 / 삭제 (n번째 제외) : O(1)

JavaScript로 구현하기

class Queue {
  count = 0;
  head = null;
  rear = null;
    
  enqueue(data) {
    const node = new Node(data);
    if (!this.head) {
      this.head = node;
    } else {
      this.rear.next = node;
    }
    this.rear = node;
    return ++this.count;
  };
    
  dequeue() {
    if (!this.head) { // stack underflow 방지
      return false;
    }
    const data = this.head.data;
    this.head = this.head.next;
    // this.head 메모리 클린
    --this.count;
    return data;
  };
    
  front() {
    return this.head?.data;
  }
}

class Node {
  next = null;
  constructor(data) {
    this.data = data;
  }
}

참고
인프런 강의 _ CS 지식의 정석 | 디자인패턴 네트워크 운영체제 데이터베이스 자료구조대시보드

ZeroCho 블로그

javascript-algorithms github