Queues

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

similar documents