Implementation of Stacks and Queues

In the last post, we learned how stacks and queues work as well as why they are implemented. They are used for the undo mechanism in text editors(stacks),event loops for browsers(queues), and much more. Now let's take a crack at implementing these two data structures.

Stack implementation

After discussing how stacks are modeled(FIFO, LILO), like a stack of books, we also learned what operations stacks use to add and remove data, called push, which adds data, and pop, that removes the most recently added data. Let's get started by creating the class.

class Stack {

constructor(){
  this.storage = []
  }
}

Here we have the stack class to create new stacks that will contain our elements. But we need to add the methods to this class in order to push and pop elements into our stack objects. Here's the code for push operation.

push(element) {
this.storage.push(element)
}

Now we can add elements to any newly created stack object(and at O(1) time complexity!). Next we need to be able to remove data from the top of the stack, our pop operation.

pop(){
  if(this.storage.length === 0){
    return "Empty stack"
  }
  return this.storage.pop()
}

Now we can remove items from the top of the stack and have it returned to us. But before deciding whether we want to just remove data from the top wildly, it would be nice to look at the top and see what element we're working with. This is called the peek operation.

peek(){ 
    return this.items[this.items.length - 1]; 
} 

Lastly, we have two helper methods: isEmpty and printStack to return whether the stack is empty, and to return a string of all the elements concatenated into a string, respectively.

isEmpty(){ 
    return this.items.length == 0; 
} 

printStack(){ 
    var str = ""; 
    for (var i = 0; i < this.items.length; i++) 
        str += this.items[i] + " "; 
    return str; 
} 

Queues

Queues are modeled differently than stacks, going by the FILO principle, similar to a line in a grocery store. In a queue, we are using both ends of the stack to add/delete data. The names of these operations are enqueue, to add data, and dequeue, to delete data.

We'll use the same starting code from the stack class.

class Queue 
{ 

    constructor() 
    { 
        this.storage = []; 
    } 

} 

Let's continue by adding the enqueue method to our queue, the way we add elements to the queue.

enqueue(element) 
{     
    this.items.push(element); 
} 

Pretty straightforward, no different from the stack so far. However, the the difference lies in the order of removal. We also need to work with both ends of the structure. This means that instead of using pop we use shift.

dequeue() 
{ 
    if(this.isEmpty()) 
        return "Queue is empty"; 
    return this.items.shift(); 
} 

Using shift removes the first elements that were pushed into the queue, keeping the first-in-first-out order. The last method we'll add is the front operation, similar to the peek operation in the stack except we'll be returning the front element in the queue.

front() 
{ 
    if(this.isEmpty()) 
        return "No elements in Queue"; 
    return this.items[0]; 
} 

Those are the core operations needed for a queue. We can add some helper methods just like we did for the stack.

isEmpty() 
{  
    return this.items.length == 0; 
} 

printQueue() 
{ 
    var str = ""; 
    for(var i = 0; i < this.items.length; i++) 
        str += this.items[i] +" "; 
    return str; 
}