[자료구조] 스택(Stack) & 큐(Queue)

2022년 04월 04일

스택(Stack)

스택은 ‘쌓다 라는 의미로 데이터를 쌓아 올리는 형태의 자료 구조이다.

가장 나중에 삽입된 데이터가 가장 먼저 삭제되는 후입 선출(Last In, First Out) 특징을 갖기 때문에 모든 연산은 최상단에서 일어난다.

실생활 예로 테니스 공 통이나 일회용 종이컵을 꺼내는걸 생각할 수 있다.

대표적인 메서드로는 push와 pop이 있다.

시간 복잡도(Time complexity)

push와 pop은 최상단에서만 일어나므로 시간 복잡도는 O(1)이다.
탐색 : 특정 데이터를 찾을 때 까지 수행하기 때문에 O(n)이다.

연결리스트로 스택 구현하기(JS)

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

class Stack {
  constructor(value) {
    const newNode = new Node(value);
    this.top = newNode;
    this.length = 1;
  }

  push(value) {
    const newNode = new Node(value);
    if (this.length === 0) {
      this.top = newNode;
    } else {
      newNode.next = this.top;
      this.top = newNode;
    }
    this.length++;
    return this;
  }

  pop() {
    if (this.length === 0) return undefined;
    const temp = this.top;
    this.top = this.top.next;
    temp.next = null;

    this.length--;
    return temp;
  }
}

큐(Queue)

큐는 먼저 들어온 것이 먼저 나가는 선입선출 (First In, First Out)의 자료 구조이다.

실생활 예로는 줄을 서는 것을 생각해 볼 수 있다.

대표적인 메서드로는 enqueue와 dequeue가 있다.

시간 복잡도(Time complexity)

삽입 : O(1) (enqueue로 값을 넣기만 하면 되기 때문에)
삭제 : O(1) (dequeue로 값을 빼기만 하면 되기 때문에)
탐색 : O(n) (특정 데이터를 찾을 때 까지 수행하기 때문에)

연결리스트로 큐 구현하기(JS)

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

class Queue {
  constructor(value) {
    const newNode = new Node(value);
    this.first = newNode;
    this.last = newNode;
    this.length = 1;
  }

  enqueue(value) {
    const newNode = new Node(value);

    if (this.length === 0) {
      this.first = newNode;
      this.last = newNode;
    } else {
      this.last.next = newNode;
      this.last = newNode;
    }
    this.length++;
    return this;
  }

  dequeue() {
    if (this.length === 0) return undefined;

    const temp = this.first;

    if (this.length === 1) {
      this.first = null;
      this.last = null;
    } else {
      this.first = this.first.next;
      temp.next = null;
    }
    this.length--;
    return temp;
  }
}