FIFO Queues: Examples and Implementations
FIFO queues, a fundamental concept in algorithms and data structures, follow a first-in-first-out model. Explore the uses of FIFO queues in program execution, resource allocation, and search algorithms. Learn about implementing FIFO queues using lists and understand the differences between queue and stack implementations.
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
FIFO Queues CSE 2320 Algorithms and Data Structures Vassilis Athitsos University of Texas at Arlington 1
FIFO Queues Stacks are last-in first-outqueues. Another widely used model is first-in first-out (FIFO) queues. Examples of uses of FIFO queues: 2
FIFO Queues Stacks are last-in first-outqueues. Another widely used model is first-in first-out (FIFO) queues. Examples of uses of FIFO queues: Program execution: Requests for access to memory, disk, network... Resource allocation: Forwarding network traffic in network switches and routers. Search algorithms. More details later in the course 3
Put and Get The FIFO queue supports insert and delete as follows: insert, push, put: This is what we call the insert operation when we talk about FIFO queues. It puts an item "at the end of the line". delete, pop, get: This is what we call the delete operation when we talk about FIFO queues. It removes the item that is "at the head of the line". How can we implement FIFO queues? 4
FIFO Queues Using Lists A FIFO queue is essentially a list. put(queue, item) inserts that item at the END of the list. get(queue) removes (and returns) the item at the beginning of the list. What is the running time of these operations? 5
FIFO Queues Using Lists A FIFO queue is essentially a list. put(queue, item) inserts that item at the END of the list. get(queue) removes (and returns) the item at the beginning of the list. Both operations take O(1) time. Assumption: the list data type contains a pointer to the last element. Our new implementation at lists.c satisfies that assumption. 6
Queue Versus Stack Implementation Implementation-wise, compare: list-based queue implementation. list-based stack implementation. What are the key differences? 7
Queue Versus Stack Implementation Implementation-wise, compare: list-based queue implementation. list-based stack implementation. The only difference is in insertions. Queues insert at the end of the list. Stacks insert at the beginning of the list. It is very easy to implement queues starting from our list-based stack implementation. Rename push to put. Rename pop to get. Change the get function to insert at the end. 8
FIFO Queues Using Arrays How do we implement queues using arrays? The stack definition looked like this: typedef struct stack_struct * Stack; struct stack_struct { int max_size; int top_index; void ** items; }; What changes do we need to accommodate queues? 9
FIFO Queues Using Arrays How do we implement queues using arrays? A queue can be defined like this: typedef struct queue_struct * queue; struct queue_struct { int max_size; int start_index; int end_index; void ** items; }; end_index tells us where to put a new item. start_index tells us where to remove an item from. 10
Examples of Put and Get put(15) put(20) get() put(30) put(7) put(25) get() put(12) get() get() queue position - 3 - 2 - 1 end_index - 0 start_index 11
Examples of Put and Get put(15) put(20) get() put(30) put(7) put(25) get() put(12) get() get() queue position - 3 - 2 - 1 end_index 15 0 start_index 12
Examples of Put and Get put(15) put(20) get() put(30) put(7) put(25) get() put(12) get() get() queue position - 3 - 2 end_index 20 1 15 0 start_index 13
Examples of Put and Get put(15) put(20) get(): returns 15 put(30) put(7) put(25) get() put(12) get() get() queue position - 3 - 2 end_index start_index 20 1 - 0 14
Examples of Put and Get put(15) put(20) get() put(30) put(7) put(25) get() put(12) get() get() queue position - 3 end_index 30 2 start_index 20 1 - 0 15
Examples of Put and Get put(15) put(20) get() put(30) put(7) put(25) get() put(12) get() get() queue position 7 3 30 2 start_index 20 1 - 0 end_index 16
Examples of Put and Get put(15) put(20) get() put(30) put(7) put(25) get() put(12) get() get() queue position 7 3 30 2 start_index 20 1 25 0 end_index 17
Examples of Put and Get put(15) put(20) get() put(30) put(7) put(25) get(): returns 20 put(12) get() get() queue position 7 3 start_index 30 2 - 1 end_index 25 0 18
Examples of Put and Get put(15) put(20) get() put(30) put(7) put(25) get() put(12) get() get() queue position 7 3 start_index 30 2 12 1 end_index 25 0 19
Examples of Put and Get put(15) put(20) get() put(30) put(7) put(25) get() put(12) get(): returns 30 get() queue position start_index 7 3 - 2 end_index 12 1 25 0 20
Examples of Put and Get put(15) put(20) get() put(30) put(7) put(25) get() put(12) get() get(): returns 7 queue position - 3 - 2 end_index 12 1 start_index 25 0 21
Book Implementation (Array-Based) static Item *q; static int N, head, tail; void QUEUEinit(int maxN) { q = malloc((maxN+1)*sizeof(Item)); N = maxN+1; head = N; tail = 0; } int QUEUEempty() { return head % N == tail; } void QUEUEput(Item item) { q[tail++] = item; tail = tail % N; } Item QUEUEget() { head = head % N; return q[head++]; } 22
Limitations of This Implementation Same as for stacks. Only one queue object can be used in the entire code. Queues can only store objects of a single data type: Specified in Item.h, where type Item is defined using a typedef. It is easy to adapt the stacks_arrays.c code to obtain an array-based implementation of queues that does not have these two limitations. Possible homework... 24
More on Queues Later Done with queues for now. We will see queues and queue-related topics quite a bit more in this course. 25
