Data Structures With JavaScript: Stack and Queue
Two of the most commonly used data structures in web development are stacks and queues. Many users of the Internet, including web developers, are unaware of this amazing fact. If you are one of these developers, then prepare yourself for two enlightening examples: the 'undo' operation of a text editor uses a stack to organize data; the eventloop of a web browser, which handles events (clicks, hoovers, etc.), uses a queue to process data.
Now pause for a moment and imagine how many times we, as both a user and developer, use stacks and queues. That is amazing, right? Due to their ubiquity and similarity in design, I have decided to use them to introduce you to data structures.
A Stack
In computer science, a stack is a linear data structure. If this statement holds marginal value to you, as it originally did with me, consider this alternative: A stack organizes data into sequential order.
This sequential order is commonly described as a stack of dishes at a cafeteria. When a plate is added to a stack of dishes, the plate retains the order of when it was added; moreover, when a plate is added, it is pushed towards the bottom of a stack. Every time we add a new plate, the plate is pushed towards the bottom of the stack, but it also represents the top of the stack of plates.
This process of adding plates will retain the sequential order of when each plate was added into the stack. Removing plates from a stack will also retain the sequential order of all plates. If a plate is removed from the top of a stack, every other plate in the stack will still retain the correct order in the stack. What I am describing, possibly with too many words, is how plates are added and removed at most cafeterias!
To provide a more technical example of a stack, let us recall the 'undo' operation of a text editor. Every time text is added to a text editor, this text is pushed into a stack. The first addition to the text editor represents the bottom of the stack; the most recent change represents the top of the stack. If a user wants to undo the most recent change, the top of the stack is removed. This process can be repeated until there are no more additions to the stack, which is a blank file!
Operations of a Stack
Since we now have a conceptual model of a stack, let us define the two operations of a stack:

push(data)
adds data. 
pop()
removes the most recently added data.
Implementation of a Stack
Now let us write the code for a stack!
Properties of a Stack
For our implementation, we will create a constructor named Stack
. Each instance of Stack
will have two properties: _size
and _storage
.
function Stack() { this._size = 0; this._storage = {}; }
this._storage
enables each instance of Stack
to have its own container for storing data; this._size
reflects the number of times data was pushed to the current version of a Stack
. If a new instance of Stack
is created and data is pushed into its storage, then this._size
will increase to 1. If data is pushed, again, into the stack, this._size
will increase to 2. If data is removed from the stack, then this._size
will decrease to 1.
Methods of a Stack
We need to define methods that can add (push) and remove (pop) data from a stack. Let's start with pushing data.
Method 1 of 2: push(data)
(This method can be shared among all instances of Stack
, so we'll add it to the prototype of Stack
.)
We have two requirements for this method:
 Every time we add data, we want to increment the size of our stack.
 Every time we add data, we want to retain the order in which it was added.
Stack.prototype.push = function(data) { // increases the size of our storage var size = this._size++; // assigns size as a key of storage // assigns data as the value of this key this._storage[size] = data; };
Our implementation of push(data)
includes the following logic. Declare a variable named size
and assign it the value of this._size++
. Assign size
as a key of this._storage
. And assign data
as the value of a corresponding key.
If our stack invoked push(data)
five times, then the size of our stack would be 5. The first push to the stack would assign that data a key of 1 in this._storage
. The fifth invocation of push(data)
would assign that data a key of 5 in this._storage
. We've just assigned order to our data!
Method 2 of 2: pop()
We can now push data to a stack; the next logical step is popping (removing) data from a stack. Popping data from a stack is not simply removing data; it is removing only the most recently added data.
Here are our goals for this method:
 Use a stack's current size to get the most recently added data.
 Delete the most recently added data.
 Decrement
_this._size
by one.  Return the most recently deleted data.
Stack.prototype.pop = function() { var size = this._size, deletedData; deletedData = this._storage[size]; delete this._storage[size]; this.size; return deletedData; };
pop()
meets each of our four goals. First, we declare two variables: size
is initialized to the size of a stack; deletedData
is assigned to the data most recently added to a stack. Second, we delete the keyvalue pair of our most recently added data. Third, we decrement the size of a stack by 1. Fourth, we return the data that was removed from the stack.
If we test our current implementation of pop()
, we find that it works for the following usecase. If we push(data)
data to a stack, the size of the stack increments by one. If we pop()
data from our stack, the size of our stack decrements by one.
A problem arises, however, when we reverse the order of invocation. Consider the following scenario: we invoke pop()
and then push(data)
. The size of our stack changes to 1 and then to 0. But the correct size of our stack is 1!
To handle this use case, we will add an if
statement to pop()
.
Stack.prototype.pop = function() { var size = this._size, deletedData; if (size) { deletedData = this._storage[size]; delete this._storage[size]; this._size; return deletedData; } };
With the addition of our if
statement, the body of our code is executed only when there is data in our storage.
Complete Implementation of a Stack
Our implementation of Stack
is complete. Regardless of the order in which we invoke either of our methods, our code works! Here is the final version of our code:
function Stack() { this._size = 0; this._storage = {}; } Stack.prototype.push = function(data) { var size = ++this._size; this._storage[size] = data; }; Stack.prototype.pop = function() { var size = this._size, deletedData; if (size) { deletedData = this._storage[size]; delete this._storage[size]; this._size; return deletedData; } };
From Stack to Queue
A stack is useful when we want to add data in sequential order and remove data. Based on its definition, a stack can remove only the most recently added data. What happens if we want to remove the oldest data? We want to use a data structure named queue.
A Queue
Similar to a stack, a queue is a linear data structure. Unlike a stack, a queue deletes only the oldest added data.
To help you conceptualize how this would work, let's take a moment to use an analogy. Imagine a queue being very similar to the ticketing system of a deli. Each customer takes a ticket and is served when their number is called. The customer who takes the first ticket should be served first.
Let's further imagine that this ticket has the number "one" displayed on it. The next ticket has the number "two" displayed on it. The customer who takes the second ticket will be served second. (If our ticketing system operated like a stack, the customer who entered the stack first would be the last to be served!)
A more practical example of a queue is the eventloop of a web browser. As different events are being triggered, such as the click of a button, they are added to an eventloop's queue and handled in the order they entered the queue.
Operations of a Queue
Since we now have a conceptual model of a queue, let us define its operations. As you will notice, the operations of a queue are very similar to a stack. The difference lies in where data is removed.

enqueue(data)
adds data to a queue. 
dequeue
removes the oldest added data to a queue.
Implementation of a Queue
Now let us write the code for a queue!
Properties of a Queue
For our implementation, we will create a constructor named Queue
. We will then add three properties: _oldestIndex
, _newestIndex
, and _storage
. The need for both _oldestIndex
and _newestIndex
will become clearer during the next section.
function Queue() { this._oldestIndex = 1; this._newestIndex = 1; this._storage = {}; }
Methods of a Queue
We will now create the three methods shared amongst all instances of a queue: size()
, enqueue(data)
, and dequeue(data)
. I will outline the objectives for each method, reveal the code for each method, and then explain the code for each method.
Method 1 of 3: size()
We have two objectives for this method:
 Return the correct size for a queue.
 Retain the correct range of keys for a queue.
Queue.prototype.size = function() { return this._newestIndex  this._oldestIndex; };
Implementing size()
might appear trivial, but you will quickly find that to be untrue. To understand why, we must quickly revisit how size
was implemented for a stack.
Using our conceptual model of a stack, let's imagine that we push five plates onto a stack. The size of our stack is five and each plate has a number associated with it from one (first added plate) to five (last added plate). If we remove three plates, then we have two plates. We can simply subtract three from five to get the correct size, which is two. Here's the most important point about the size of a stack: The current size represents the correct key associated with the plate at top of the stack (2) and the other plate in the stack (1). In other words, the range of keys is always from the current size to 1.
Now, let's apply this implementation of stack's size
to our queue. Imagine that five customers take a ticket from our ticketing system. The first customer has a ticket displaying the number 1 and the fifth customer has a ticket displaying the number 5. With a queue, the customer with the first ticket is served first.
Let's now imagine that the first customer is served and that this ticket is removed from the queue. Similar to a stack, we can get the correct size of our queue by subtracting 1 from 5. Our queue currently has four unserved tickets. Now, this is where a problem arises: the size no longer represents the correct ticket numbers. If we simply subtracted one from five, we would have a size of 4. We cannot use 4 to determine the current range of remaining tickets in the queue. Do we have tickets in the queue with the numbers from 1 to 4 or from 2 to 5? The answer is unclear.
This is the benefit of having the following two properties in a queue: _oldestIndex
and _newestIndex
. All of this may seem confusing—I'm still occasionally confused. What helps me rationalize everything is the following example I've developed.
Imagine that our deli has two ticketing systems:

_newestIndex
represents a ticket from a customer ticketing system. 
_oldestIndex
represents a ticket from an employee ticketing system.
Here's the hardest concept to grasp in regards to having two ticketing systems: When the numbers in both systems are identical, every customer in the queue has been addressed and the queue is empty. We will use the following scenario to reinforce this logic:
 A customer takes a ticket. The customer's ticket number, which is retrieved from
_newestIndex
, is 1. The next ticket available in the customer ticket system is 2.  An employee does not take a ticket, and the current ticket in the employee ticket system is 1.
 We take the current ticket number in the customer system (2) and subtract the number in the employee system (1) to get the number 1. The number 1 represents the number of tickets still in the queue that have not been removed.
 The employee takes a ticket from their ticketing system. This ticket represents the customer ticket being served. The ticket that was served is retrieved from
_oldestIndex
, which displays the number 1.  We repeat step 4, and now the difference is zero—there are no more tickets in the queue!
We now have a property (_newestIndex
) that can tell us the largest number (key) assigned in the queue and a property (_oldestIndex
) that can tell us the oldest index number (key) in the queue.
We have adequately explored size()
, so let's now move to enqueue(data)
.
Method 2 of 3: enqueue(data)
For enqueue
, we have two objectives:
 Use
_newestIndex
as a key ofthis._storage
and use any data being added as the value of that key.  Increment the value of
_newestIndex
by 1.
Based on these two objectives, we will create the following implementation of enqueue(data)
:
Queue.prototype.enqueue = function(data) { this._storage[this._newestIndex] = data; this._newestIndex++; };
The body of this method contains two lines of code. On the first line, we use this._newestIndex
to create a new key for this._storage
and assign data
to it. this._newestIndex
always starts at 1. On the second line of code, we increment this._newestIndex
by 1, which updates its value to 2.
That's all the code we need for enqueue(data)
. Let's now implement dequeue()
.
Method 3 of 3: dequeue()
Here are the objectives for this method:
 Remove the oldest data in a queue.
 Increment
_oldestIndex
by one.
Queue.prototype.dequeue = function() { var oldestIndex = this._oldestIndex, deletedData = this._storage[oldestIndex]; delete this._storage[oldestIndex]; this._oldestIndex++; return deletedData; };
In the body of dequeue()
, we declare two variables. The first variable, oldestIndex
, is assigned a queue's current value for this._oldestIndex
. The second variable, deletedData
, is assigned the value contained in this._storage[oldestIndex]
.
Next, we delete the oldest index in the queue. After it is deleted, we increment this._oldestIndex
by 1. Finally, we return the data we just deleted.
Similar to the problem in our first implementation of pop()
with a stack, our implementation of dequeue()
does not handle situations where data is removed before any data is added. We need to create a conditional to handle this use case.
Queue.prototype.dequeue = function() { var oldestIndex = this._oldestIndex, newestIndex = this._newestIndex, deletedData; if (oldestIndex !== newestIndex) { deletedData = this._storage[oldestIndex]; delete this._storage[oldestIndex]; this._oldestIndex++; return deletedData; } };
Whenever the values of oldestIndex
and newestIndex
are not equal, then we execute the logic we had before.
Complete Implementation of a Queue
Our implementation of a queue is complete. Let's view the entire code.
function Queue() { this._oldestIndex = 1; this._newestIndex = 1; this._storage = {}; } Queue.prototype.size = function() { return this._newestIndex  this._oldestIndex; }; Queue.prototype.enqueue = function(data) { this._storage[this._newestIndex] = data; this._newestIndex++; }; Queue.prototype.dequeue = function() { var oldestIndex = this._oldestIndex, newestIndex = this._newestIndex, deletedData; if (oldestIndex !== newestIndex) { deletedData = this._storage[oldestIndex]; delete this._storage[oldestIndex]; this._oldestIndex++; return deletedData; } };
Conclusion
In this article, we've explored two linear data structures: stacks and queues. A stack stores data in sequential order and removes the most recently added data; a queue stores data in sequential order but removes the oldest added data.
If the implementation of these data structures seems trivial, remind yourself of the purpose of data structures. They aren't designed to be overly complicated; they are designed to help us organize data. In this context, if you find yourself with data that needs to be organized in sequential order, consider using a stack or queue.
Source: Tuts Plus
… [Trackback]
[…] Read More here: designncode.in/datastructureswithjavascriptstackandqueue/ […]
… [Trackback]
[…] There you will find 84556 more Infos: designncode.in/datastructureswithjavascriptstackandqueue/ […]
… [Trackback]
[…] Read More here: designncode.in/datastructureswithjavascriptstackandqueue/ […]
… [Trackback]
[…] Read More: designncode.in/datastructureswithjavascriptstackandqueue/ […]
… [Trackback]
[…] There you will find 41215 more Infos: designncode.in/datastructureswithjavascriptstackandqueue/ […]
… [Trackback]
[…] There you will find 35240 more Infos: designncode.in/datastructureswithjavascriptstackandqueue/ […]
… [Trackback]
[…] Read More Infos here: designncode.in/datastructureswithjavascriptstackandqueue/ […]
… [Trackback]
[…] Read More Infos here: designncode.in/datastructureswithjavascriptstackandqueue/ […]
… [Trackback]
[…] Read More: designncode.in/datastructureswithjavascriptstackandqueue/ […]
… [Trackback]
[…] Informations on that Topic: designncode.in/datastructureswithjavascriptstackandqueue/ […]
… [Trackback]
[…] Read More here: designncode.in/datastructureswithjavascriptstackandqueue/ […]
… [Trackback]
[…] There you will find 26815 more Infos: designncode.in/datastructureswithjavascriptstackandqueue/ […]
… [Trackback]
[…] Informations on that Topic: designncode.in/datastructureswithjavascriptstackandqueue/ […]
… [Trackback]
[…] Informations on that Topic: designncode.in/datastructureswithjavascriptstackandqueue/ […]
… [Trackback]
[…] Read More here: designncode.in/datastructureswithjavascriptstackandqueue/ […]
… [Trackback]
[…] Read More: designncode.in/datastructureswithjavascriptstackandqueue/ […]
… [Trackback]
[…] There you will find 89741 more Infos: designncode.in/datastructureswithjavascriptstackandqueue/ […]
… [Trackback]
[…] Read More: designncode.in/datastructureswithjavascriptstackandqueue/ […]