Data Structures: Stacks and Queues

Stacks and Queues are common data structures you may be questioned on during a job interview. Let's take a look at what Stack and Queues are from a high level.

Stack

A stack is a linear data structure that operates in a LIFO (Last In First Out) order. Think of a stack of plates. Each plate is stacked on top of an existing one, and the last plate stacked is the first one removed. Stack data structures operate the same way. Data is added to the end of the structure, and when acted upon is removed from the end of that same structure.

Queue

A queue is a linear data structure that operates in a FIFO (First In First Out) order. A common metaphor for a queue is a check out line at the store. Whoever is at the front of the line gets to check out first. A queue data structure operates in a similar fashion, data is added to the end of the stack and removed and acted upon from the front.

Implementations

Let's create some simple implementations of these data structures using JavaScript arrays and array methods.

Stack

We can create a simple stack class using a JavaScript array and the built in array methods push and pop. Push adds a new value to the end of the array. Pop removes and returns the last value in the array. This allows our data structure to operate in LIFO order.

class Stack {
    constructor() {
        this.stack = []
    }

    push(value) {
        this.stack.push(value)
    }

    pop() {
        return this.stack.pop()
    }
}

const stack = new Stack()

stack.push('a') // -> stack: [ 'a' ] 
stack.push('b') // -> stack: [ 'a', 'b' ]
stack.push('c') // -> stack: [ 'a', 'b', 'c' ]

stack.pop() // -> returns 'c', stack: [ 'a', 'b' ]

Queue

We can create a simple queue class using a JavaScript array and the built in array methods push and shift. Push adds a new value to the end of the array. Shift removes and returns the first value in the array. This allows our data structure to operate in FIFO order.

class Queue {
    constructor() {
        this.stack = []
    }

    push(value) {
        this.stack.push(value)
    }

    shift() {
        return this.stack.shift()
    }
}

const queue = new Queue()

queue.push('a') // -> queue: [ 'a' ] 
queue.push('b') // -> queue: [ 'a', 'b' ]
queue.push('c') // -> queue: [ 'a', 'b', 'c' ]

queue.shift() // -> returns 'a', queue: [ 'b', 'c' ]

Summary

Stacks and Queues are both linear data structures, stacks however operate in LIFO order while Queues operate in FIFO order. The different removal order of these structures allows them to be useful in different ways.