4. Stack & Queue Basic


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