숙제 : LinkedList로 Stack, Queue 구현하기

queue : enqueue, dequeue, peek

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

class Queue {
  length = 0;
  head = null;
  tail = null;

  enqueue(value) {
    // stack.push와 동일
    const newNode = new Node(value);
    if (this.length == 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
    return this.length;
  }

  dequeue() {
    let rslt;
    // head.next의 prev를 null로 설정 & head 업데이트
    if (this.length > 0) {
      if (this.length == 1) {
        rslt = this.head.value;
        this.head = null;
        this.tail = null;
      } else {
        rslt = this.head.value;
        this.head.next.prev = null;
        this.head = this.head.next;
      }
      this.length--;
    }
    return rslt;
  }

  peek() {
    return this.head?.value;
  }

  get length() {
    return this.length;
  }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(3);
queue.enqueue(5);
queue.enqueue(4);
queue.enqueue(2);
console.log(queue.length); // 5
console.log(queue.dequeue()); // 1
console.log(queue.length); // 4
console.log(queue.peek()); // 3
console.log(queue.dequeue()); // 3
console.log(queue.peek()); // 5
console.log(queue.dequeue()); // 5
console.log(queue.peek()); // 4
console.log(queue.dequeue()); // 4
console.log(queue.dequeue()); // 2
console.log(queue.length); // 0
console.log(queue.dequeue()); // undefined
console.log(queue.peek()); // undefined

stack : push, pop, top

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

class Stack {
  length = 0;
  head = null;
  tail = null;

  push(value) {
    // 비어있으면 head = tail = newNode
    // 그 외엔 tail에다 추가 후 tail 업데이트

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

  pop() {
    // tail.prev를 tail로 업데이트
    // 비어있거나 하나만 있으면 undefined 반환
    let rslt = this.tail?.value;
    this.tail = !this.tail ? null : this.tail.prev;
    this.length = this.length - 1 < 0 ? 0 : this.length - 1;
    return rslt;
  }

  top() {
    return this.tail?.value;
  }

  get length() {
    return this.length;
  }
}

const stack = new Stack();
stack.push(1);
stack.push(3);
stack.push(5);
stack.push(4);
stack.push(2);
console.log(stack.length); // 5
console.log(stack.pop()); // 2
console.log(stack.length); // 4
console.log(stack.top()); // 4
console.log(stack.pop()); // 4
console.log(stack.top()); // 5
console.log(stack.pop()); // 5
console.log(stack.top()); // 3
console.log(stack.pop()); // 3
console.log(stack.pop()); // 1
console.log(stack.length); // 0
console.log(stack.pop()); // undefined
console.log(stack.top()); // undefined