Stacks and Queues

Stacks and Queues

Stacks

Describe Stacks

Stacks are linear data structures. Linear data structures are made up of elements that are in a particular order, and are traversed in a specific way. The last item on the stack is the first item that is taken off the stack (LIFO).

A stack is like a pile of airport security trays. The are stacked up from bottom to top. The person using the next tray takes the first one from the top.

Stacks are implemented with a set of functions.

• When an item is added to the stack, the operation is called push.

• When an item is deleted and taken off the top of the stack, the operation is called pop.

• If you want to look at the item on the top of the stack, the operation is called top or peek.

• An isEmpty function checks whether or not a stack is empty.

• The size function returns the number of items in the queue.

  3 Common Uses for Stacks

• Undo/redo functionality

• Saving and retrieving browser history

Describe the general process of sorting a stack

Example Implementation (courtesy of Roger Schmidt)

const LinkedList = require('../lib/linked-list.js')


class Stack {
  // constructor()
  //   create a new LinkedList to be the stack
  constructor(){
    this.stack = new LinkedList()
  }

  // length()
  //   returns the length of the stack
  length(){
    return this.stack.length;
  }

  // push(val)
  //   takes a value to store in the stack
  //   returns a reference to self for chaining
  push(val){
    this.stack.push(val);
    return this;
  }

  // pop()
  //   removes and return the value of the next item according to the rules
  //   of the stack
  pop(){
    return this.stack.pop();
  }

  // peek()
  //   return the value of the next item according to the rules
  //   of the stack
  //   does not change the stack
  peek(){
    return this.stack.get(this.stack.length - 1);
  }

  // isEmpty()
  //   return true if the queue is empty, false otherwise
  isEmpty(){
    return this.stack.length === 0;
  }
}

module.exports = Stack;

Resources

• CS50: Stacks
• BaseCS: Stacks and Overflows

Queues

Describe Queues

Queues are linear data structures and follow the first in, first out (FIFO) principle. Queues are different from stacks because when data is added, it is added to the end of the queue, AKA the tail.

A queue is like the line at the DMV. The first person in is the first person out.

Queues are implemented with a set of functions

• Adding an item to the tail is called enqueuing
• Removing an item from the head is called dequeuing

Example uses for queues

• Job Scheduling

Example Implementation (courtesy of Roger Schmidt)

const LinkedList = require('../lib/linked-list.js')


class Queue {

  // constructor()
  //   create a new LinkedList to be the queue
  constructor(){
    this.queue = new LinkedList()
  }

  // length()
  //   returns the length of the queue
  length(){
    return this.queue.length;
  }

  // enqueue(val)
  //   takes a value to store in the queue
  //   returns a reference to self for chaining
  enqueue(val){
    this.queue.unshift(val);
    return this;
  }

  // dequeue()
  //   removes and return the value of the next item according to the rules
  //   of the queue
  dequeue(){
    return this.queue.pop()
  }

  // peek()
  //   return the value of the next item according to the rules
  //   of the queue
  //   does not change the queue
  peek(){
    return this.queue.get(this.queue.length - 1);
  }


  // isEmpty()
  //   return true if the queue is empty, false otherwise
  isEmpty(){
    return this.queue.length === 0;
  }
}

module.exports = Queue;

Resources