Table of Contents

Recall that a queue is a data structure that follows the FIFO (first in, first out) principle.

And a stack is a data structure that follows the LIFO (last in, first out) principle.

Create a Queue

class Stack {
  constructor() {
    this.data = []
  }
  push(record) {
    this.data.push(record)
  }
  pop() {
    return this.data.pop()
  }
  peek() {
    return this.data[this.data.length - 1]
  }

  isEmpty() {
    return this.data.length === 0
  }
}

Create Queue from a Stack

class QueueFromStack {
  constructor() {
    this.first = new Stack()
    this.second = new Stack()
  }

  enqueue(item) {
    this.first.push(item)
  }

  dequeue() {
    while (this.first.peek()) {
      this.second.push(this.first.pop())
    }

    let val = this.second.pop()

    while (this.second.peek()) {
      this.first.push(this.second.pop())
    }
    return val
  }

  peek() {
    while (this.first.peek()) {
      this.second.push(this.first.pop())
    }

    let val = this.second.peek()

    while (this.second.peek()) {
      this.first.push(this.second.pop())
    }
    return val
  }

  isEmpty() {
    return this.first.peek() === undefined
  }
}

const s = new Stack()
s.push(1)
s.push(2)
console.log(s.peek()) // returns 2
console.log(s.pop())
console.log(s.pop())
console.log(s.isEmpty()) // returns 1

const qfs = new QueueFromStack()

console.log(qfs.isEmpty()) // true
qfs.enqueue('A')
qfs.enqueue('B')
qfs.enqueue('C')
qfs.enqueue('D')
console.log(qfs.peek()) // A
console.log(qfs.dequeue()) // A
console.log(qfs.dequeue()) // B
console.log(qfs.dequeue()) // C
console.log(qfs.dequeue()) // D
console.log(qfs.isEmpty()) // true

Using a Stack that does not use arrays

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

// Last in, first out

class Stack {
  constructor() {
    this.top = null
    this.bottom = null
    this.length = 0
  }

  peek() {
    return this.top
  }

  push(val) {
    const newNode = new Node(val)

    // check if this is the first item in the stack
    if (this.length === 0) {
      this.top = newNode
      this.bottom = newNode
    } else {
      // if we have items...
      const temp = this.top
      this.top = newNode
      this.top.next = temp
    }

    this.length++
    return this
  }

  pop() {
    // if there is no top
    if (!this.top) {
      return null
    }

    if (this.top === this.bottom) {
      this.bottom = null
    }

    // hold the top
    const result = this.top
    // make the second node the first
    this.top = this.top.next
    this.length--
    return result
  }

  isEmpty() {
    // return true or false
    if (this.length === 0) {
      return true
    }
    return false
  }
}

class QueueFromStack {
  constructor() {
    this.first = new Stack()
    this.last = new Stack()
    this.length = 0
  }

  enqueue(value) {
    this.first.push(value)
  }

  dequeue() {
    while (this.first.peek()) {
      this.last.push(this.first.pop())
    }

    let result = this.last.pop()

    while (this.last.peek()) {
      this.first.push(this.last.pop())
    }
    return result
  }
}