Report

Queues CS-2301 System Programming Concepts Hugh C. Lauer (Slides include materials from The C Programming Language, 2nd edition, by Kernighan and Ritchie, and from C: How to Program, 5th and 6th editions, by Deitel and Deitel) CS-2301, D-Term 2011 Queues 1 Definition – Linked List • A linear data structure in which each element contains a pointer to the next element • (Usually) has a beginning and an end • Items can (sometimes) be added anywhere • Beginning • Middle • End • Items can be removed from anywhere CS-2301, D-Term 2011 Queues 2 Note • Array is also a linear data structure with a beginning and an end • No pointers to next item • Implicit in ++ and -- operators • Very difficult to add items to beginning or middle! CS-2301, D-Term 2011 Queues 3 More Definitions • Queue:– a linear data structure in which items are always added to end and removed from beginning • FIFO:– First-in, First-out • Stack:– a linear data structure in which items are always added to the beginning and also removed from beginning • LIFO:– Last-in, First-out • Neither stacks nor queues need to be implemented via linked lists CS-2301, D-Term 2011 Queues 4 Programming Assignment #5 (CS2301, B-term 11) • Provide two different implementations of a queue • Linked list • Fixed-size array • Note that fixed-size array cannot hold an arbitrarily long queue CS-2301, D-Term 2011 Queues 5 Queue.h #ifndef QUEUE_H #define QUEUE_H #include "Simulation.h" #if defined QUEUE_ELEMENT /* The actual interface definition for the queue begins here and uses QUEUE_ELEMENT as a type */ int queueEmpty(void); /* returns TRUE if the queue is empty, FALSE if not */ int dequeue(QUEUE_ELEMENT *e); /* Removes the first element from the queue and stores it into the location pointed to by e. Returns TRUE if successful, FALSE if not */ int maxQueueLength(void); /* Returns the maximum number of elements that have been stored in the queue at one time */ int currentQueueLength(void); /* Returns the number of elements currently in the queue */ //End of interface definition int enqueue(QUEUE_ELEMENT e); /* Adds a copy of the argument to the tail of the queue. Returns TRUE if successful, FALSE if not */ CS-2301, D-Term 2011 #endif #endif Queues 6 QUEUE_ELEMENT is defined in Simulation.h as typedef struct customer Customer; #define QUEUE_ELEMENT Customer Queue.h #ifndef QUEUE_H #define QUEUE_H #include "Simulation.h" #if defined QUEUE_ELEMENT /* The actual interface definition for the queue begins here and uses QUEUE_ELEMENT as a type */ int queueEmpty(void); /* returns TRUE if the queue is empty, FALSE if not */ int dequeue(QUEUE_ELEMENT *e); /* Removes the first element from the queue and stores it into the location pointed to by e. Returns TRUE if successful, FALSE if not */ int maxQueueLength(void); /* Returns the maximum number of elements that have been stored in the queue at one time */ int currentQueueLength(void); /* Returns the number of elements currently in the queue */ //End of interface definition int enqueue(QUEUE_ELEMENT e); /* Adds a copy of the argument to the tail of the queue. Returns TRUE if successful, FALSE if not */ CS-2301, D-Term 2011 #endif #endif Queues 7 Linked List Implementation Classroom exercise:– struct listItem { type QUEUE_ELEMENT; Add an item to tail of struct listItem *next; non-empty queue }; Classroom exercise:– struct listItem *head, *tail; Add an item to tail of empty queue QUEUE_ ELEMENT QUEUE_ ELEMENT next next QUEUE_ ELEMENT QUEUE_ ELEMENT next next CS-2301, D-Term 2011 Lists and Trees 8 Linked List Implementation Classroom exercise:– struct listItem { type QUEUE_ELEMENT; Remove an item from struct listItem *next; non-empty queue }; struct listItem *head, *tail; QUEUE_ ELEMENT QUEUE_ ELEMENT next next QUEUE_ ELEMENT QUEUE_ ELEMENT next next CS-2301, D-Term 2011 Lists and Trees 9 Questions about Linked List Implementation? CS-2301, D-Term 2011 Queues 10 Fixed Array Implementation • If maximum queue length is always less than N, then we can implement the queue with an array of size N • How? CS-2301, D-Term 2011 Queues 11 Fixed Array Implementation (continued) QUEUE_ QUEUE_ QUEUE_ QUEUE_ QUEUE_ QUEUE_ QUEUE_ ELEMENTELEMENT ELEMENT ELEMENT ELEMENT ELEMENT ELEMENT QUEUE_ …ELEMENT N • Classroom exercises:– – How to represent head of queue? – How to represent tail of queue? CS-2301, D-Term 2011 Queues 12 Fixed Array Implementation (continued) QUEUE_ QUEUE_ QUEUE_ QUEUE_ QUEUE_ QUEUE_ QUEUE_ ELEMENTELEMENT ELEMENT ELEMENT ELEMENT ELEMENT ELEMENT QUEUE_ …ELEMENT N • Classroom exercises (continued):– – How to add an item to the queue? – How to remove an item from the queue? – What error checking is needed? CS-2301, D-Term 2011 Queues 13 Questions? CS-2301, D-Term 2011 Queues 14