CODEWITHSUNDEEP
javascriptdata-structuresstackqueue
stargiraffe
stargiraffe

Reputation: 85

Implementation of .pop() in Stacks and dequeue in Queues

I am currently studying Stacks and Queues and there is one thing that I quietly don't really get when implementing pop and dequeue.

So here is my Stack using arrays.


    const Stack = function() {
      this.store = []; 
      this.top = 0; 
    }
    
    Stack.prototype.push = function(value) {
      return this.store[this.top++] = value
    }
    
    Stack.prototype.pop = function() {
      if (!this.top) return;
    
      return this.store[--this.top]
    }

Let's say that I create new instance of my stack and add few numbers and pop one off.

    const stack= new Stack();
    
    stack.push(1) // store= [1], top = 1
    stack.push(2) // store= [1, 2], top =2
    stack.push(3) // store= [1, 2, 3], top = 3
    
    stack.pop() // store = [1,2,3], top = 2

After I pop off my last number, I am still left with the same store and just have the top decreased by 1.

What I don't get exactly is, when implementing Stack

  1. why do we keep the last element that was popped off?
  1. Same kind of question goes for Queues when Implementing dequeue.

    const Queue = function() {
      this.store = []; // stores data in an array
      this.first = this.last = 0; // tracks first and last position in the queue
    }
    
    Queue.prototype.enqueue = function(value) {
      return this.store[this.last++] = value
    }
    
    Queue.prototype.dequeue = function() {
      const dequeued = this.store[this.first];
    
      if (this.fist === this.last) return;
      this.store[this.first] = null;
      this.first++
    
      return dequeued;
    }
    
    const queue = new Queue();
    
    queue.enqueue(1) //store = [1], last = 1, first = 0
    queue.enqueue(2) //store = [1,2], last = 2, first = 0
    queue.enqueue(3) //store = [1,2,3], last = 3, first = 0
    
    console.log(queue.dequeue()) //store = [null,2,3], last = 3, first = 1

For dequeue, I am simply just replacing the value with null instead of really getting [2,3], when removing the first item in the queue.

  1. Same as Stacks, why do we have to keep a value in place?

Appreciate your help.

Upvotes: 1

Views: 1258

Answers (1)

jfriend00
jfriend00

Reputation: 707158

why do we keep the last element that was popped off? If we leave this off in the array, won't this take up more memory?

Yes, that implementation never shrinks the array size. The array will remain at its largest length. But, the values that have been popped off will be reused/ovewritten when new values are pushed onto the stack. This will not shrink the array when you pop values off it. That may or may not take more memory. Arrays are implemented internally with a bit of extra slack in them so that every time you increase or decrease their length by a small bit, they don't have to reallocate a new sized memory and copy the existing array over to the new block. So, leaving a few extra elements on the end of the array won't necessarily change things much or at all. Now, if you pushed thousands of elements onto the stack and then popped them all off, then you would indeed have a bunch of unused memory sitting in your empty stack and that would be inefficient. So, it really depends upon how much you're going to push onto the stack.

You could fairly easily insert a check for how many extra bytes are sitting on the end and (if more than some threshold), then reset the length of your array to allow the system to reallocate a smaller array. Unless you have a zillion of these stacks or unless you put a really large number of items on the stack, it's all probably inconsequential in the grand scheme of things, but if you had a proven reason that it would matter to your app, you could optimize it to use less memory in some circumstances.

For dequeue, I am simply just replacing the value with null instead of really getting [2,3], when removing the first item in the queue.

Same as Stacks, why do we have to keep a value in place?

The queue implementation seems more problematic as its implementation seems like it would grow larger forever since this.first and this.last are only ever incremented. There is no queue implementation reason to keep the old data. To keep from growing forever, this would need to copy down and resize the array or switch to more of a linked list type implementation where you can freely just remove the first link or add the last link without the restraints of an array.

If the values in the stack or queue are object references, then you can mitigate their impact by setting their stack or queue value to null after popping or dequeing them. This will allow the objects to be garbage collected when nobody else is using them.

A simple queue that doesn't accumulate memory would be like this:

const Queue = function() {
  this.store = []; // stores data in an array
}

Queue.prototype.enqueue = function(value) {
  // add to end of the queue
  this.store.push(value);
}

Queue.prototype.dequeue = function() {
  // remove oldest value from the start of the queue
  return this.store.shift();
}

Upvotes: 2

Related Questions