Data Structures Tutorial

Data Structures Tutorial Asymptotic Notation Structure and Union Array Data Structure Linked list Data Structure Type of Linked list Advantages and Disadvantages of linked list Queue Data Structure Implementation of Queue Stack Data Structure Implementation of Stack Sorting Insertion sort Quick sort Selection sort Heap sort Merge sort Bucket sort Count sort Radix sort Shell sort Tree Traversal of the binary tree Binary search tree Graph Spanning tree Linear Search Binary Search Hashing Collision Resolution Techniques

Misc Topic:

Priority Queue in Data Structure Deque in Data Structure Difference Between Linear And Non Linear Data Structures Queue Operations In Data Structure About Data Structures Data Structures Algorithms Types of Data Structures Big O Notations Introduction to Arrays Introduction to 1D-Arrays Operations on 1D-Arrays Introduction to 2D-Arrays Operations on 2D-Arrays Strings in Data Structures String Operations Application of 2D array Bubble Sort Insertion Sort Sorting Algorithms What is DFS Algorithm What Is Graph Data Structure What is the difference between Tree and Graph What is the difference between DFS and BFS Bucket Sort Dijkstra’s vs Bellman-Ford Algorithm Linear Queue Data Structure in C Stack Using Array Stack Using Linked List Recursion in Fibonacci Stack vs Array What is Skewed Binary Tree Primitive Data Structure in C Dynamic memory allocation of structure in C Application of Stack in Data Structures Binary Tree in Data Structures Heap Data Structure Recursion - Factorial and Fibonacci What is B tree what is B+ tree Huffman tree in Data Structures Insertion Sort vs Bubble Sort Adding one to the number represented an array of digits Bitwise Operators and their Important Tricks Blowfish algorithm Bubble Sort vs Selection Sort Hashing and its Applications Heap Sort vs Merge Sort Insertion Sort vs Selection Sort Merge Conflicts and ways to handle them Difference between Stack and Queue AVL tree in data structure c++ Bubble sort algorithm using Javascript Buffer overflow attack with examples Find out the area between two concentric circles Lowest common ancestor in a binary search tree Number of visible boxes putting one inside another Program to calculate the area of the circumcircle of an equilateral triangle Red-black Tree in Data Structures Strictly binary tree in Data Structures 2-3 Trees and Basic Operations on them Asynchronous advantage actor-critic (A3C) Algorithm Bubble Sort vs Heap Sort Digital Search Tree in Data Structures Minimum Spanning Tree Permutation Sort or Bogo Sort Quick Sort vs Merge Sort Boruvkas algorithm Bubble Sort vs Quick Sort Common Operations on various Data Structures Detect and Remove Loop in a Linked List How to Start Learning DSA Print kth least significant bit number Why is Binary Heap Preferred over BST for Priority Queue Bin Packing Problem Binary Tree Inorder Traversal Burning binary tree Equal Sum What is a Threaded Binary Tree? What is a full Binary Tree? Bubble Sort vs Merge Sort B+ Tree Program in Q language Deletion Operation from A B Tree Deletion Operation of the binary search tree in C++ language Does Overloading Work with Inheritance Balanced Binary Tree Binary tree deletion Binary tree insertion Cocktail Sort Comb Sort FIFO approach Operations of B Tree in C++ Language Recaman’s Sequence Tim Sort Understanding Data Processing Applications of trees in data structures Binary Tree Implementation Using Arrays Convert a Binary Tree into a Binary Search Tree Create a binary search tree Horizontal and Vertical Scaling Invert binary tree LCA of binary tree Linked List Representation of Binary Tree Optimal binary search tree in DSA Serialize and Deserialize a Binary Tree Tree terminology in Data structures Vertical Order Traversal of Binary Tree What is a Height-Balanced Tree in Data Structure Convert binary tree to a doubly linked list Fundamental of Algorithms Introduction and Implementation of Bloom Filter Optimal binary search tree using dynamic programming Right side view of binary tree Symmetric binary tree Trim a binary search tree What is a Sparse Matrix in Data Structure What is a Tree in Terms of a Graph What is the Use of Segment Trees in Data Structure What Should We Learn First Trees or Graphs in Data Structures All About Minimum Cost Spanning Trees in Data Structure Convert Binary Tree into a Threaded Binary Tree Difference between Structured and Object-Oriented Analysis FLEX (Fast Lexical Analyzer Generator) Object-Oriented Analysis and Design Sum of Nodes in a Binary Tree What are the types of Trees in Data Structure What is a 2-3 Tree in Data Structure What is a Spanning Tree in Data Structure What is an AVL Tree in Data Structure Given a Binary Tree, Check if it's balanced B Tree in Data Structure Convert Sorted List to Binary Search Tree Flattening a Linked List Given a Perfect Binary Tree, Reverse Alternate Levels Left View of Binary Tree What are Forest Trees in Data Structure Compare Balanced Binary Tree and Complete Binary Tree Diameter of a Binary Tree Given a Binary Tree Check the Zig Zag Traversal Given a Binary Tree Print the Shortest Path Given a Binary Tree Return All Root To Leaf Paths Given a Binary Tree Swap Nodes at K Height Given a Binary Tree Find Its Minimum Depth Given a Binary Tree Print the Pre Order Traversal in Recursive Given a Generate all Structurally Unique Binary Search Trees Perfect Binary Tree Threaded Binary Trees Function to Create a Copy of Binary Search Tree Function to Delete a Leaf Node from a Binary Tree Function to Insert a Node in a Binary Search Tree Given Two Binary Trees, Check if it is Symmetric A Full Binary Tree with n Nodes Applications of Different Linked Lists in Data Structure B+ Tree in Data Structure Construction of B tree in Data Structure Difference between B-tree and Binary Tree Finding Rank in a Binary Search Tree Finding the Maximum Element in a Binary Tree Finding the Minimum and Maximum Value of a Binary Tree Finding the Sum of All Paths in a Binary Tree Time Complexity of Selection Sort in Data Structure How to get Better in Data Structures and Algorithms Binary Tree Leaf Nodes Classification of Data Structure Difference between Static and Dynamic Data Structure Find the Union and Intersection of the Binary Search Tree Find the Vertical Next in a Binary Tree Finding a Deadlock in a Binary Search Tree Finding all Node of k Distance in a Binary Tree Finding Diagonal Sum in a Binary Tree Finding Diagonal Traversal of The Binary Tree Finding In-Order Successor Binary Tree Finding the gcd of Each Sibling of the Binary Tree Greedy Algorithm in Data Structure How to Calculate Space Complexity in Data Structure How to find missing numbers in an Array Kth Ancestor Node of Binary Tree Minimum Depth Binary Tree Mirror Binary Tree in Data Structure Red-Black Tree Insertion Binary Tree to Mirror Image in Data Structure Calculating the Height of a Binary Search Tree in Data Structure Characteristics of Binary Tree in Data Structure Create a Complete Binary Tree from its Linked List Field in Tree Data Structure Find a Specified Element in a binary Search Tree Find Descendant in Tree Data Structure Find Siblings in a Binary Tree Given as an Array Find the Height of a Node in a Binary Tree Find the Second-Largest Element in a Binary Tree Find the Successor Predecessor of a Binary Search Tree Forest of a Tree in Data Structure In Order Traversal of Threaded Binary Tree Introduction to Huffman Coding Limitations of a Binary Search Tree Link State Routing Algorithm in Data Structure Map Reduce Algorithm for Binary Search Tree in Data Structure Non-Binary Tree in Data Structure Quadratic Probing Example in Hashing Scope and Lifetime of Variables in Data Structure Separate Chaining in Data Structure What is Dynamic Data Structure Separate Chaining vs Open Addressing Time and Space Complexity of Linear Data Structures Abstract Data Types in Data Structures Binary Tree to Single Linked List Count the Number of Nodes in the Binary Tree Count Total No. of Ancestors in a Binary Search Tree Elements of Dynamic Programming in Data Structures Find cost of tree with prims algorithm in data structures Find Preorder Successor in a Threaded Binary Tree Find Prime Nodes Sum Count in Non-Binary Tree Find the Right Sibling of a Binary Tree with Parent Pointers Find the Width of the Binary Search Tree Forest trees in Data Structures Free Tree in Data Structures Frequently asked questions in Tree Data Structures Infix, Postfix and Prefix Conversion Time Complexity of Fibonacci Series What is Weighted Graph in Data Structure What is the Advantage of Linear Search?

Linear Queue VS Circular Queue

What is Queue?

A queue is one of the important linear data structures extensively used in various computer applications. It is based on the FIFO (First In First Out) principle. It follows a particular order of execution of data for which operations are performed.  In this data structure, data enters from one end, i.e., REAR end, and next data enters in the queue after the previous one, and deletion operation is performed from another end, .i.e., FRONT end.

As compare with stacks, stacks are also a linear data structure. Although, it is based on LIFO (Last In First Out) principle, which implies that data enters one by one from one end into the stack till it reaches its end limit, and it popped out the data element from the stack from that end itself.

In a stack, only one pointer is needed for performing all operations, which is top, whereas, in the queue, there are two pointers needed, rear and front, for performing all operations.

Types of Queues

The types of queue are as follows:

  • Linear Queue
  • Circular Queue
  • Deque
  • Priority Queue
  • Multiple Queue

Linear queue

A linear queue is said to be the simple queue, and whenever we need to talk about the queue, it is by default set that we are considering a linear queue. A linear queue is a linear data structure based on FIFO (First In First Out) principle, in which data enters from the rear end and is deleted from the front end. We will discuss these ends in more detail further.  

With an example of the Movie Ticket counter, a customer comes first in the queue is served first, and the next customer to that one comes after. This process will continue till all the tickets for that movie have been booked.

Other examples includes:

  • People are waiting for the bus. The first person up standing in the queue will be the first to get on the bus.
  • Cars lined at a toll bridge. The first car to reach out the bridge will be the first to leave.
Difference between Linear Queue and Circular Queue

Operations performed on Linear Queue

There are certain basic operations has performed in the linear queue are as follows->

1. Enqueue

  • For the addition of data elements in the queue, this operation is used.
  • By applying this operation, data is entered in the queue according to the sequence after one another. En queue will be continued till the queue reaches its end limit.
  • After it reaches the endpoint, the data cannot add to the queue, and then such condition is said to be an Overflow condition.
  • En-queue operation is done from the rear end.

2. Dequeue

  • For deletion of a data element from the queue, this operation is used.
  • By Using this operation, that data element is deleted, which is enqueued first in the queue, or the elements are popped in the same order in which they are pushed in the queue.
  • This process will delete the data elements from the queue until the whole queue becomes empty. Once all the elements are deleted, then the deletion operation is unable to execute, and then such condition is said to be an Underflow condition.
  • It is done from the front end.

3. Peek

 This operation is used to find out the very first queue element, which is to be served first without dequeuing it.

Two Ends of Linear Queue

  1. Front end- It refers to the initial or starts position of the queue. The front end is mainly used to delete the data element from the queue or perform a de queue operation.
  2. Rear end- It refers to the last or back position of the queue. The rear end is mainly used to insert the data elements in the queue or to perform the en-queue operation.

Methods of Implementation of Linear queue

There are various methods of implementation of the queue:

  • Queue implementation using an array
  • Queue implementation using stack
  • Queue implementation using linked list

Implementation of Linear queue using an Array

Here we discuss the implementation of queue using an array->

Queues can easily be implemented by using linear arrays. As stated earlier, the queue has front and rear pointers that point to the position where deletion and insertion of data elements can be done.

Steps

  1. Initially, we need to create an array of size 'n' whether statically or dynamically depends on the user.
  2. Then declare two pointers named FRONT and REAR.
  3. Initialize REAR = -1 and FRONT = 0.
  4. Create three functions named Enqueue for adding data elements in the queue, Dequeue for deletion of a data element from the queue, and peek for finding out the first element from the queue without dequeuing it.
Difference between Linear Queue and Circular Queue

                                 Implementation of linear queue

Algorithms

Algorithms of Enqueue operation

Step 1- Check if REAR == FRONT.

Step 2- If the above statement holds, then such a condition is said to be an Overflow, and further insertion of data elements is not possible.

Step 3- If it holds false, then

  • set REAR = REAR + 1 and
  • Add the data element in queue at rear position. 
  • Queue[REAR] = data.

Algorithm of Dequeue operation

Step 1- Check if FRONT = REAR + 1

Step 2- If the above statement holds, then

  • Such condition is said to be Underflow condition.
  • Return -1.

Step 3- If it holds false, then

  • popped out the value from the queue present at the front position
  • Data = Queue[FRONT].
  • Return data.

     Step 4-> Set FRONT = FRONT + 1, it points next data element.

Algorithm of Peek operation

Step 1- Check if FRONT = REAR + 1.

Step 2- If the above statement holds, then display the message; the queue is empty.

Step 3- If it holds false,

  • Return the data element from the queue present at the front position.
  • Data = Queue[FRONT].
  • Return data.

Circular Queue

A circular queue is also one of the important types of a queue. It is similar to the linear queue but has some variations. The end position of a circular queue is connected back to the start position, forming the circular-like structure and making a circle. A circular queue is also based on the First In First Out (FIFO) principle. It is also known as 'Ring Buffer'.

As we have seen previously, in a linear queue, further insertion of data elements is not possible when REAR reaches the end, and FRONT also reaches to end. The queue is still empty, but it shows that the queue is full, so to overcome the above problem concept of circular is introduced. In the circular queue, this problem will not arise. We will further discuss it in more detail in the below section.

Difference between Linear Queue and Circular Queue

                                            Circular queue

Applications of Circular queue

  • Round Robin scheduling is one of the major applications of the circular queue. This algorithm is employed by process and network schedulers in computing.
  • It is also used in computer-controlled Traffic Signal Systems.
  • It is also used in CPU scheduling and memory management.

Operations performed on Circular queue

There are certain basic operations has performed in the linear queue are as follows->

1. Enqueue

  • This operation is used for the insertion of a data element in the queue.
  • In a circular queue, the addition of a data element is always done from the rear position.

2. Dequeue

  • This operation is used for the removal of a data element from the queue.
  • In a circular queue, deletion of a data element is always done from the front position.

Two ends of Circular queue

In a circular queue, there is a circle like structure; hence there are no two ends distinguished but still, to differentiate the insertion and deletion criteria of data elements, we refer to these two ends:

  1. Front end-> it is used to delete the data elements from the queue.
  2. Rear end-> it is used to insert the data elements in the queue.

Implementation of Circular queue using an array

A circular queue can easily be implemented using arrays. It works on the circular increment process. As stated earlier, it has two pointers, front, and rear. From the rear end, insertion of data elements is possible. If the rear pointer reaches the end, it again increments back to the initial position of the queue so that further insertions can also be possible; hence this implies an increment process.

From the front end, deletion of data elements is possible. If the front pointer reaches to end, it returns to the queue's initial position so that further deletions can be possible.   

By using modulo division with the queue size, the circular increment is performed.

Steps

  1. Initially, we need to create an array of size 'n' whether statically or dynamically depends on the user.
  2. Then declare two pointers named FRONT and REAR.
  3. Initialize REAR = -1 and FRONT = -1.
  4. Create two functions named Enqueue for adding data elements in the queue,  Dequeue for the deletion of data elements from the queue.
Difference between Linear Queue and Circular Queue

                                 Implementation of Circular queue

Algorithm of Enqueue operation

Step 1-> Check if FRONT == 0 && REAR == (n-1) || REAR == (FRONT – 1) % (n-1).

Step 2- If the above statement holds, then such condition is said to be an Overflow, and further insertion of data elements is not possible.

Step 3- Else if FRONT == -1 then,

  • set REAR = 0, FRONT = 0 and
  • Add the data element in queue at rear position. 
  • Queue[REAR] = data.

Step 4- Else if REAR == (n-1) &&  FRONT != 0

  • set REAR = 0 and
  • Add the data element in queue at rear position. 
  • Queue[REAR] = data.

      Step 5- Else

  • set REAR = REAR + 1
  • Add the data element in queue at rear position. 
  • Queue[REAR] = data.

Algorithm of Dequeue operation

     Step 1-Check if FRONT == -1

Step 2- If the above statement holds, then

  • Such condition is said to be an Underflow condition.
  • Return -1.

     Step 3- If it holds false, then

  • popped out value from the queue present at the front position
  • Data = Queue[FRONT].
  • Return data.

     Step 4- Set FRONT = FRONT + 1, it points next data element.

      Step 5-If FRONT == REAR then, set FRONT = -1 and REAR = -1.

     Step 6-> Else if FRONT == n-1 then, set FRONT = 0.

Advantages of Circular queue over Linear queue->

  • Linear queue consumes more memory as compared to circular queue.
  • A circular queue uses an efficient way for memory utilization.
  • In a circular queue, new data can be inserted again at a particular position after deleting previous data on that position.
  • In a linear queue, if the rear pointer reaches last and the front pointer deletes all data from the queue, it remains to show the message of Overflow, which is the main drawback of the linear queue.
  •  In a circular queue, an overflow message is shown when the queue is full.
  • Easy to perform dequeue operation and enqueue operation.
On the basis of comparisonLinear QueueCircular queue
 Arrangement It arranges data in linear order.It arranges data in circular order.
DefinitionIt is a linear data structure that contains the data in linear sequential order. Here rear end is not connected with the front end.It is also a linear data structure in which the rear end is connected with the front end.
Insertion and Deletion operationInsertion is done from the rear end, whereas deletion is done from the front end. Hence here it is fixed.     
Difference between Linear Queue and Circular Queue
Due to a circular structure, we can not distinguish the exact position of insertion and deletion. Hence here, it is not fixed.
Difference between Linear Queue and Circular Queue
Peek operationIn a linear queue, we can easily fetch out the peek value.As it is circularly arranged, we cannot fetch out the peek value.
Memory spaceIt requires more memory space.It requires less memory space.
Utilization of memoryIn a linear queue, there is an inefficient way of the utilization of memory.In a circular queue, there is an efficient way of the utilization of memory.