Scribd
Upload
198 views3 pages

Types and Implementation of Queues

A queue is a linear data structure that follows the first-in, first-out (FIFO) principle. Elements are inserted at the rear of the queue and deleted from the front. There are two main implementations: using an array, which can be circular to avoid rebuffering issues, or using linked nodes. Priority queues order elements by priority and remove the highest priority element first, and can be implemented with heaps or unsorted arrays. Dequeues allow insertion and removal from both ends, behaving as a queue from one end and a stack from the other.

Uploaded by

Rajendranbehappy
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
198 views3 pages

Types and Implementation of Queues

A queue is a linear data structure that follows the first-in, first-out (FIFO) principle. Elements are inserted at the rear of the queue and deleted from the front. There are two main implementations: using an array, which can be circular to avoid rebuffering issues, or using linked nodes. Priority queues order elements by priority and remove the highest priority element first, and can be implemented with heaps or unsorted arrays. Dequeues allow insertion and removal from both ends, behaving as a queue from one end and a stack from the other.

Uploaded by

Rajendranbehappy
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

QUEUE

A queue is a linear list of elements in which deletion can take place only at one

end, called the front, and insertions can take place only at the other end, called the rear.
The term front and rear are used in describing a linear list only when it is
implemented as a queue.
Queue is also called first-in-first-out (FIFO) lists. Since the first element in a

queue will be the first element out of the queue. In other words, the order in which
elements enters a queue is the order in which they leave.
There are main two ways to implement a queue :
1. Circular queue using array
2. Linked Structures (Pointers)

Primary queue operations:


Enqueue : insert an element at the rear of the queue
Dequeue : remove an element from the front of the queue Following is the algorithm
which describes the implementation of Queue using an Array.
DEQUEUE (OR) DEQUE (DOUBLE ENDED QUEUE)
DeQueue is a data structure in which elements may be added to or deleted from
the front or the rear.
Like an ordinary queue, a double-ended queue is a data structure it supports the
following operations: enq_front, enq_back, deq_front, deq_back, and empty.
Dequeue can be behave like a queue by using only enq_front and deq_front , and
behaves like a stack by using only enq_front and deq_rear.

The DeQueue is represented as follows.

DeQueue can be represented in two ways they are,


1) Input restricted DeQueue 2) output restricted DeQueue
The out put restricted Dequeue allows deletions from only one end and input restricted
Dequeue allow insertions at only one end.
PRIORITY QUEUE
Priority queue is a linear data structure. It is having a list of items in which each
item has associated priority. It works on a principle add an element to the queue with
an associated priority and remove the element from the queue that has the highest
priority. In general different items may have different priorities. In this queue highest or
the lowest priority item are inserted in random order. It is possible to delete an element
from a priority queue in order of their priorities starting with the highest priority.
While priority queues are often implemented with heaps, they are conceptually
distinct from heaps. A priority queue is an abstract concept like "a list" or "a map"; just as
a list can be implemented with a linked list or an array, a priority queue can be
implemented with a heap or a variety of other methods such as an unordered array.
CIRCULAR QUEUE :
In a standard queue data structure re-buffering problem occurs for each dequeue
operation. To solve this problem by joining the front and rear ends of a queue to make
the queue as a circular queue
Circular queue is a linear data structure. It follows FIFO principle.

In
a

circular queue the last node is connected back to the first node to make
circle.

Circular

linked list fallow the First In First Out principle.

Elements

are added at the rear end and the elements are deleted at front

end of the
Both
It

queue.

the front and the rear pointers points to the beginning of the array.
is also called as Ring buffer.

Items

can inserted and deleted from a queue in O(1) time.

You might also like