Understanding Queue Data Structure: Operations, Applications, and Implementation
Learn about the queue abstract data type (ADT) that follows the first-in-first-out scheme. Explore queue operations like insertion, deletion, checking size, and emptiness, along with real-world applications and array-based implementation details. Get insights into auxiliary data structures, algorithms, and exception handling with queues.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
The Queue ADT Insertions and deletions follow the first-in first-out scheme Auxiliary queue operations: object front(): returns the element at the front without removing it Insertions are at the rear of the queue and removals are at the front of the queue integer size(): returns the number of elements stored boolean isEmpty(): indicates whether no elements are stored Main queue operations: enqueue(object): inserts an element at the end of the queue Exceptions Attempting the execution of dequeue or front on an empty queue throws an QueueException object dequeue(): removes and returns the element at the front of the queue
Queue Example Operation enqueue(5) enqueue(3) dequeue() enqueue(7) dequeue() front() dequeue() dequeue() isEmpty() Output 5 3 7 7 error true Q (5) (5, 3) (3) (3, 7) (7) (7) () () ()
Applications of Queues Direct applications Waiting lists, bureaucracy Access to shared resources (e.g., printer) Multiprogramming Indirect applications Auxiliary data structure for algorithms Component of other data structures
Array-based Queue Use an array of size N in a circular fashion Two variables keep track of the front and rear f index of the front element r index immediately past the rear element Array location r is kept empty normal configuration Q f r 0 1 2 wrapped-around configuration Q r f 0 1 2
Queue Operations Algorithmsize() return (N f + r) mod N We use the modulo operator (remainder of division) AlgorithmisEmpty() return (f=r) Q f r 0 1 2 Q r f 0 1 2
Queue Operations (cont.) Algorithmenqueue(o) ifsize() = N 1 then throw FullQueueException else Q[r] o r (r + 1) mod N Operation enqueue throws an exception if the array is full This exception is implementation-dependent Q f r 0 1 2 Q r f 0 1 2
Queue Operations (cont.) Algorithmdequeue() ifisEmpty() then throw EmptyQueueException else o Q[f] f (f + 1) mod N returno Operation dequeue throws an exception if the queue is empty This exception is specified in the queue ADT Q f r 0 1 2 Q r f 0 1 2
Queue Interface in Java public interface Queue { Java interface corresponding to our Queue ADT public int size(); public boolean isEmpty(); Requires the definition of class QueueException public Object front() throws QueueException; public void enqueue(Object o); No corresponding built- in Java class public Object dequeue() throws QueueException; }
Application: Round Robin Schedulers We can implement a round robin scheduler using a queue, Q, by repeatedly performing the following steps: e = Q.dequeue() Service element e Q.enqueue(e) 1. 2. 3. The Queue 2. Service the next element 3. Enqueue the serviced element 1. Deque the next element Shared Service
Example: Jospehus Problem Jospehus Problem A group of students passing a hot potato around When the leader rings the bell after potato is passed around k times Whoever has the hot potato loses Process continues until a winner is declared Solving the problem given a list of names and a fixed value for k Refer to JosephusProblem Project
