4. Stack & Queue Basic

임쿠쿠·2021년 11월 20일
0

1. Stack

LIFO(Last In First Out)

  • 웹페이지 뒤로가기 시, 가장 최신의 페이지 부터 뒤로가기 실행

코드 구현

class StackNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  push(val) {
    if(this.size === 0) {
      this.top = new StackNode(val);
    } else {
      const pushNode = new StackNode(val);
      pushNode.next = this.top;
      this.top = pushNode;
    }

    this.size ++;
  }

  getTop() {
    return this.top.val;
  }

  pop() {
    if(this.size === 0) return null;
    const popNode = this.top;
    this.top = this.top.next;
    this.size--;
    return popNode.val;
  }
}

const stack = new Stack();
stack.push('a');
stack.push('b');
stack.push('c');
console.log(stack.getTop());
console.log(stack.pop());
console.log(stack.getTop());

2. Queue

FIFO(Last In First Out)

class QueueNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.front = null;
    this.back = null;
    this.size = 0;
  }

  enqueue(val) {
    const newNode = new QueueNode(val);
    if(this.size === 0) {
      this.front = newNode;
      this.back = newNode;
    } else {
      this.back.next = newNode;
      this.back = newNode;
    }

    this.size++;
    // a -> b -> c -> d
    // F              B
  }

  dequeue() {
    if(this.size === 0) {
      return null;
    }

    const removedNode = this.front;

    if (this.size === 1) {
      this.back = null;
    }

    this.front = this.front.next;

    this.size--;
    return removedNode.val;
  }
}

const queue = new Queue();
queue.enqueue('a');
queue.enqueue('b');
queue.enqueue('c');
console.log(queue.front);
console.log(queue.back);
queue.dequeue();
queue.dequeue();
queue.dequeue();
queue.dequeue();
queue.dequeue();
console.log(queue.front);

참고 : codebyte - stack & queue

profile
Pay it forward

0개의 댓글