What do you need to know about Queue in Data Structure?

There are many types of data structures out there that are meant to store data in different ways. One of them is called a queue. The simplest example of a queue is the typical line that we all participate in from time to time.

In this article, we will dive deep into what exactly a queue is and how it is used to store and manipulate data.

Introduction to Queue

In the domains of data structure, a queue is a useful one in the realm of programming. It is similar to the ticket queue outside a cinema hall, where the first person entering the queue is the first person who gets the ticket.

To put it simply, a queue is an ordered collection of items where the insertion is done from one end known as either the rear end or the tail of the queue, whereas the deletion is done from another end known as the front end or the head of the queue.

A queue is a data structure in which whatever comes first will go out first. It follows the First-In-First-Out policy. In computing and systems theory, FIFO (an acronym for first in, first out) is a method for organising the manipulation of a data structure (often, specifically a data buffer) where the oldest (first) entry, or “head” of the queue, is processed first.

Depending on the application, a FIFO could be implemented as a hardware shift register or using different memory structures, typically a circular buffer, list or, in this case, a queue. Most software implementations of a FIFO queue are not thread-safe and require a locking mechanism to verify the data structure chain is being manipulated by only one thread at a time.

Before we get into the details of what a queue is, let us understand what a stack is.

What is a Stack?

Stack is an abstract data type with a predefined capacity. It is a simple data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack, and the only element that the stack can remove is the element at the top of the stack.

Features of a Stack

• Stack is an ordered list of similar data types.
• Stack is also based on the FIFO data structure method.
• There are 3 main operations of a stack which are push(), pop() and the data at the top of the stack is called top(). Insertion and removal of the data can only be done at the top.
• A stack can exist in Overflow and Underflow state if it is full or empty respectively.

The simplest application of a stack is to reverse a word. You push a given word to stack – letter by letter – and then pop letters from the stack.

Below are some code examples of how push() and pop() operation can be done in the C++ language.

# Push Operation
void Stack::push(int x){
    if(top >= 10){
        cout << "Stack Overflow \n" }
    else{
        a[++top] = x;
        cout << "Element Inserted \n";}}

# Pop Operation
int Stack::pop(){
    if(top < 0){
        cout << "Stack Underflow \n";
        return 0;}
    else{
        int d = a[top--];
        return d;}}

Now let us get back to the details of Queue.

Operations in Queue

There are a couple of operations in the queue that are given below.

• enqueue(data) adds a new item to the rear of the queue. It needs the item and returns nothing.

• isEmpty() tests to see whether the queue is empty. It needs no parameters and returns a boolean value.

• size() returns the number of items in the queue. It needs no parameters and returns an integer.

• dequeue() removes the front item from the queue. It needs no parameters and returns the item.
  
  Below shown are some queue() examples in Python:

class Queue:
  def __init__(self):
      self.items = []
  def isEmpty(self):
      return self.items == []
  def enqueue(self, item):
      self.items.insert(0,item)
  def dequeue(self):
      return self.items.pop()
  def size(self):
      return len(self.items)

Operations in Deque

The deque operations are given below. This data structure is a generalization of stacks and queues, called a double-ended queue or “deque” for short.

• addFront(data) adds a new item to the front of the deque. It needs the item and returns nothing.
  
• addRear(data) adds a new item to the rear of the deque. It needs the item and returns nothing.
  
• removeFront() removes the front item from the deque. It needs no parameters and returns the item. The deque is modified.
  
• removeRear() removes the rear item from the deque. It needs no parameters and returns the item. The deque is modified.
  
  Below shown are some dequeue() examples in Python:

class Deque:
  def __init__(self):
      self.items = []
  def addFront(self, item):
       self.items.append(item)
  def addRear(self, item):
       self.items.insert(0,item)
  def removeFront(self):
       return self.items.pop()
  def removeRear(self):
       return self.items.pop(0)

Implementation of a Queue

In most cases, there are 2 ways to implement a queue. Both stacks and queues can be implemented efficiently as arrays or as linked lists called Sequential Allocation and Linked List Allocation. Let us take a look at that.

Sequential Allocation

The sequential allocation simply means using an array to allocate the items to store in the queue.

A sequence has well-defined first and last elements. Every element of a
sequence except the first has a unique predecessor while every element except the last has a unique successor.

Given an array named X, we can index the array as X[1], X[2] or more generally X[n]. Logically, X[0] represents the first item, X[1] the second item and so on. This is one of the most common ways to implement stacks or queue if the maximum size of the array is known.

Linked List Allocation

For larger-scale applications, a linked list can be implemented as an alternative to an array. The storage requirement of linked representation of a queue with n elements is o(n) while the time requirement for operations is o(1).

In a linked queue, each node of the queue consists of two parts i.e. data part and the link part.

Each element of the queue points to its immediate next element in the memory. This is basically how the linked list works.

In the linked queue, there are two pointers maintained in the memory i.e. front pointer and rear pointer. The front pointer contains the address of the starting element of the queue while the rear pointer contains the address of the last element of the queue.

Types of Queue

The queue data structure is mainly used where there is a shared resource that has to serve multiple requests but can only serve a single request at a time. In such cases, we need to use the Queue data structure for queuing up the requests.

There are also different types of queue that can represent the data structure.

Linear Queue

In Linear Queue, an insertion takes place from one end while the deletion occurs from another end. The end at which the insertion takes place is known as the rear end, and the end at which the deletion takes place is known as the front end following the FIFO rule.

Circular Queue

In Circular Queue, all the nodes are represented as circular. It is similar to the linear Queue except that the last element of the queue is connected to the first element.

It is also known as Ring Buffer as all the ends are connected to another end.

Priority Queue

A priority queue is another special type of queue data structure in which each element has some priority associated with it. Based on the priority of the element, the elements are arranged in a priority queue.

If the elements occur with the same priority, then they are served according to the FIFO principle. A priority queue is implemented using Heap. This type of queue is applied to below:

• CPU Scheduling
• Graph algorithms like Dijkstra’s shortest path algorithm
• All queue applications where priority is involved.

Scalability Concepts of a Queue

Let us understand this statement right here – How do large scale distributed systems achieve reliability with so many pieces?

The key is an asynchronous processing system, typically built on a fundamental tool: the message queue or the message broker.

The synchronous part is primarily responsible for queuing up a task on the message queue, then communicating to the user the processing has started.

Once the message is on the queue, the system has promised the payment will happen. Now, the asynchronous part of the system continually reads messages off the queue and processes them one by one.

There is some example of an application that can handle large scale data processing and parallel execution as below.

Apache Kafka implements a publish-subscribe messaging model, which provides fault tolerance, scalability to handle large volumes of streaming data for distributed commit log in a Kappa architecture. Apache Kafka bridges the gaps that traditional messaging models failed to achieve. Kafka installations can decide via configuration if they take availability or consistency as a secondary concern. Depending on the use case, decisions can be made between the tradeoffs between eventual consistency and availability. Kafka can also partition data, meaning that when you have a proper shared key such as a user ID in online shopping, you can share it very well, hence promising reliability.

Java 8 has multiple classes to support functional-style operations on streams of elements, such as map-reduce transformations on collections. One of the classes is called Stream. It wasn’t possible to perform functional programming in Java earlier, at least not so easy, but Java 8 also introduced a powerful Stream API that provides many functional programming operations like map, filter, flat-map, reduce, collect, and so on.

Read more: https://www.java67.com/2016/09/map-reduce-example-java8.html#ixzz6svVyomLC

A stream is not a data structure that stores elements; instead, it conveys elements from a source such as a data structure, an array, and a generator function. Stream operations are divided into intermediate and terminal operations and are combined to form stream pipelines.

Streams also can facilitate parallel execution by reframing the computation as a pipeline of aggregate operations rather than as imperative operations on each element.

Summary

As we have reached the end of the article, let us recap some of the most important points in this article.

A queue is an ordered collection of items where the insertion is done from one end known as the rear end or the tail of the queue, whereas the deletion is done from another end known as the front end or the head of the queue following the FIFO order.

Stack is an abstract data type with a predefined capacity. It is a simple data structure that allows adding and removing elements in a particular order. A stack can exist in Overflow and Underflow states if it is full or empty respectively

There are multiple operations in queue and deque that is commonly used. There are also different types of queue such as linear, circular and priority that is used for other use cases.

FAQ

What are the different types of Queue?

Some of the types of queue include circular queue, priority queue and linear queue.

Related Posts