![]() ![]() The diagrammatic representation above explains insertion at front operation. ![]() But, for further insertions, you will just decrement the value of a front pointer. After that, you can insert a new element at this new location (index 5). Doing this will allow your front pointer to reach the end of a queue. In order to do that, set the front pointer to MAXSIZE - 1. In this example, a front node points to index 0, and now you want to insert elements using it. Let’s deal with the insertion using a front pointer. The image shown above represents how insertion occurs using a rear pointer. Additionally, as you are inserting elements using a rear node, its incrementation will bring you to the empty space for putting in a new element. Hence, both front and rear are pointing to the index 0. Initially, there is only one element inside the queue. Insertion at Rear:įirst, understand insertion using the rear node with the help of an example. Let’s begin with implementing insertion at both ends. To implement deque using a circular queue, you should be able to implement the insertion and deletion at both ends of a queue. Now, moving ahead, you will look into how to implement the deque using a circular queue. You must be clear about the concept of a circular queue. The image given below shows how to achieve circular incrementation. Bringing the rear node to the beginning of a queue is called circular incrementation. If the rear pointer has reached the maxsize of a queue, it will again arrive at the beginning of a queue. The illustration of a circular queue below shows the connectivity between the queue’s first and last node.Īdditionally, a circular queue manages memory efficiently because of its circular link. What Is a Circular Queue?Ī circular queue is an extended version of a linear queue as it follows the First In First Out principle with the exception that it connects the last node of a queue to its first, by forming a circular link. Primarily, understand what a circular queue is. Hence, in this tutorial, you will only focus on the circular queue representation of deque. The circular queue implementation of the deque is the most straightforward approach to implement a double-ended queue. The Deque can be implemented using either a circular queue or a doubly-linked list. ![]() Representation of Deque Using Circular Queue The time required to implement all these functions must be constant, i.e., time-complexity = O(1). But, in this tutorial, you will only implement primary queue operations. These operations are called supportive queue operations. The image below shows how output restricted deque limits removal at one end.įour basic operations are performed on deque, they are as follows:Īlong with these primary operations, you can also perform isEmpty(), isFull() and Peek() operations. In the Output-Restricted Deque, it will perform the insertion at both ends, whereas it performs the deletion of elements at only one end. Output-Restricted Deque: It is a deque with some limitations while performing deletion operations.The image below shows how input restricted deque limits insertion at one end. In the Input-Restricted Deque, it will perform the deletion at both ends, whereas it performs the insertion at only one end. Input-Restricted Deque: It is a deque with some limitations while performing insertion operations.There are two types of deque which are created by restricting certain operations. This is how deque can use the FIFO principle to perform insertion and deletion. Doing this will allow deque to act as a linear queue.Īs shown in the image above, the element which enters at first will also leave the queue first. A Deque can perform insertion and deletion operations using the FIFO (First In First Out) principle.Īs deque can operate on both ends, you can extract queue properties by limiting insertion at the front node and removal at the rear node.This example demonstrates the LIFO principle. You inserted element 2 at last and removed it at first. However, after repeating the removal of an element twice, data elements 2 and 12 get removed from the deque, respectively. Hence, it follows the Last In First Out Principle for insertion and deletion.Īs shown in the image above, initially, there were four elements inside this deque. When you do that, the deque becomes a stack. The insertion and deletion in deque can be limited to one node. A deque can perform both the insertion and deletion using the LIFO (Last In First Out) principle.Now, you will look into the primary properties of deque in a data structure. ![]()
0 Comments
Leave a Reply. |