Queue

Prerequisite: Linked List

In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence. The operation of adding an element to the rear of the queue is known as enqueue, and the operation of removing an element from the front is known as dequeue. Other operations may also be allowed, often including a peek operation that returns the value of the next element to be dequeued without dequeuing it.

Let's take the example of an enqueue operation. This operation adds an element to the end of the queue.

After enqueue operation the queue becomes:

Here's the code for enqueue operation:

enqueue(item) {
// Here this.list is an object of LinkedList.
// this.list = new LinkedList();
this.list.append(item);
}

Now. Let's take an example of peek operation. This operation returns the first element of queue without removing it from the queue.

After peek operation the queue becomes:

Here's the code for peek operation:

peek() {
if (this.isEmpty()) {
return null;
}
//The first element in the list
return this.list.start.item;
}

Now. Let's take an example of dequeue operation. This operation returns the first element of the queue and removes it from the queue.

After dequeue operation the queue becomes:

Here's the code for dequeue operation:

dequeue() {
if (this.isEmpty()) {
return null;
}
//The first element in the list
const returnValue = this.list.start.item;
this.list.deleteItem(returnValue);
return returnValue;

Real Life Example:

In a stock market trading application the order for a particular stock of same price are executed in a FIFO order.

Let's say when the stock market opens, User A places a buy order for RELIANCE of quantity 10 and price 100₹. We add the order to the queue.

User B places a buy order for RELIANCE of quantity 15 and price 100₹. We add the order to the queue.

User C places a buy order for RELIANCE of quantity 4 and price 100₹. We add the order to the queue.

Now let's say USER Z places a sell order for RELIANCE of quantity 5 and price 100₹. We take 5 stocks from the queue. User A is allocated those 5 stocks as it was the first user to place an order for RELIANCE of price 100₹.

Now let's say USER Y places a sell order for RELIANCE of quantity 15 and price 100₹. We take 15 stocks from the queue. User A is allocated those 5 stocks as it was the first user to place an order for RELIANCE of price 100₹. After User A, User B was the next one to place order for RELIANCE of price 100₹. So remaining 10 stocks are allocated to User B.

Check out this link for implementation of this data structure using JavaScript.

Follow me on Twitter, Linkedin

Check out my portfolio at https://tejender-singh.github.io/