Ch06 Queues

Queues

Chapter Outline • Representing a waiting line, i.e., queue • The methods of the queue ADT: push, front, pop, empty, and size • Implement the queue ADT: • As an adapter of a the std::list • Singly-linked list • Circular array (a.k.a., circular buffer) • The deque • Applications of queues: • Simulating physical systems with waiting lines ... • Using Queues and random number generators Chapter 6: Queues

2

The Queue Abstract Data Type • Visualization: queue = line of customers waiting for some service • In Britain, it is the common word for this • Next person served is one who has waited longest: • First-in, First-out = FIFO • New elements are placed at the end of the line • Next served is one at the front of the line

Chapter 6: Queues

3

A Print Queue • Operating systems use queues to • Track tasks waiting for a scarce resource • Ensure tasks carried out in order generated • Print queue: • Printing slower than selecting pages to print • So use a queue, for fairness • A stack would be inappropriate (more in a moment) • (Consider multiple queues, priorities, etc., later) Chapter 6: Queues

4

A Print Queue (continued)

Chapter 6: Queues

5

Unsuitability of a Print Stack • Stacks are last-in, first-out (LIFO) • Most recently selected document would print next • Unless queue is empty, your job may never execute • ... if others keep issuing print jobs

Chapter 6: Queues

6

Specification of the Queue ADT

Function

Behavior

Item_Type& front(); const Item_Type& front() const void pop() void push(const Item_Type&) size_t size() const

Returns true if the queue is empty; otherwise returns false. Returns the object that is at the front of the queue without removing it. Removes the object at the front of the queue. Pushes an item onto the rear of the queue. Returns the number of items in the queue.

bool empty() const

Chapter 6: Queues

7

Maintaining a Queue of Customers Problem: Write a menu-driven program that: • Maintains a list of customers waiting for service • Can add a new customer at the end • Can display name of next customer to serve • Can display the length of the line

Chapter 6: Queues

8

Maintaining a Queue of Customers (2) Analysis: Because service is in FIFO order, a queue is the appropriate data structure • Top level algorithm: while user not finished, • Display menu and obtain choice, then • Perform the selected operation • The operations are all basic queue operations ...

Chapter 6: Queues

9

Maintain_Queue.cpp int main() { queue<string> customers; string name; int choice_num = 0; string choices[] = {"push", "front", "pop", "size", "quit"}; const int NUM_CHOICES = 5; // Perform all operations selected by user. while (choice_num < NUM_CHOICES - 1) { // Select the next operation. cout << "Select an operation on customer queue\n"; for (int i = 0; i < NUM_CHOICES; i++) { cout << i << ": " << choices[i] << endl; } cin >> choice_num; switch (choice_num) { . . . } // End while. return 0; } Chapter 6: Queues

10

Insert a new customer case 0: cout << "Enter new customer name\n"; cin >> name; customers.push(name); break;

Chapter 6: Queues

11

Display the Next Customer case 1: cout << "Customer " << customers.front() << " is next in line\n"; break;

Chapter 6: Queues

12

Remove the Next Customer case 2: cout << "Customer " << customers.front() << " removed from line\n"; customers.pop(); break;

Chapter 6: Queues

13

Display the Length of the Line case 3: cout << "Size of line is " << customers.size() << endl; break;

Chapter 6: Queues

14

Exit the Program case 4: cout << << << break; default: cout << break;

"Leaving customer queue.\n" "Number of customers in queue is " << customers.size() endl; "Invalid selection\n";

Chapter 6: Queues

15

Implementing Queue: adapter of std::list • This is a simple adapter class, with following mappings: • Queue push maps to push_back • Queue front maps front • Queue pop maps to pop_front • ... • This is the approach taken by the C++ standard library. • Any sequential container that supports push_back, front, and pop_front can be used. • The list • The deque Chapter 6: Queues

16

Implementing Queue: Singly-Linked List This requires front and rear Node pointers: template class queue { . . . private: // Insert implementation-specific data fields // Insert definition of Node here #include "Node.h" // Data fields Node* front_of_queue; Node* back_of_queue; size_t num_items; }; Chapter 6: Queues

17

Using a Single-Linked List to Implement a Queue (continued)

Chapter 6: Queues

18

Implementing Queue: Singly-Linked List (2) • Insert at tail, using back_of_queue for speed • Remove using front_of_queue • Adjust size when adding/removing • No need to iterate through to determine size

Chapter 6: Queues

19

Implementing Queue: Singly-Linked List (3) template void queue::push(const Item_Type& item) { if (front_of_queue == NULL) { back_of_queue = new Node(item, NULL); front_of_queue = back_of_queue; back_of_queue = new Node(item, NULL); front_of_queue = back_of_queue; } else { back_of_queue->next = new Node(item, NULL); back_of_queue = back_of_queue->next; } num_items++; } Chapter 6: Queues

20

Implementing Queue: Singly-Linked List (4) template Item_Type& queue::front() { return front_of_queue->data; }

Chapter 6: Queues

21

Implementing Queue: Singly-Linked List (4) template void queue::pop() { Node* old_front = front_of_queue; front_of_queue = front_of_queue->next; if (front_of_queue == NULL) { back_of_queue = NULL; } delete old_front; num_items--; }

Chapter 6: Queues

22

Analysis of the Space/Time Issues • Time efficiency of singly- or doubly-linked list good: O(1) for all Queue operations • Space cost: ~3 extra words per item • vector uses 1 word per item when fully packed • 2 words per item when just grown • On average ~1.5 words per item, for larger lists

Chapter 6: Queues

23

Analysis of the Space/Time Issues (2) • vector Implementation • Insertion at end of vector is O(1), on average • Removal from the front is linear time: O(n) • Removal from rear of vector is O(1) • Insertion at the front is linear time: O(n)

Chapter 6: Queues

24

Implementing queue With a Circular Array Basic idea: Maintain two integer indices into an array • front: index of first element in the queue • rear: index of the last element in the queue • Elements thus fall at front through rear Key innovation: • If you hit the end of the array wrap around to slot 0 • This prevents our needing to shift elements around • Still have to deal with overflow of space Chapter 6: Queues

25

Implementing Queue With Circular Array (2)

Chapter 6: Queues

26

Implementing Queue With Circular Array (3)

Chapter 6: Queues

27

Implementing Queue With Circular Array (4)

Chapter 6: Queues

28

Implementing queue with a circular array template class queue { public: . . . private: // Insert implementation-specific data fields void reallocate(); // Data fields static const size_t DEFAULT_CAPACITY = 10; size_t capacity; size_t num_items; size_t front_index; size_t rear_index; Item_Type* the_data; };

Chapter 6: Queues

29

Implementing queue with a circular array(2) template queue::queue() : capacity(DEFAULT_CAPACITY), num_items(0), front_index(0), rear_index(DEFAULT_CAPACITY - 1), the_data(new Item_Type[DEFAULT_CAPACITY]) {}

Chapter 6: Queues

30

Implementing queue with a circular array(3) template void queue::push(const Item_Type& item) { if (num_items == capacity) { reallocate(); } num_items++; rear_index = (rear_index + 1) % capacity; the_data[rear_index] = item; }

// Cost: O(1) (even on average when grows)

Chapter 6: Queues

31

Implementing queue with a circular array(4) template Item_Type& queue::front() { return the_data[front_index]; } template void queue::pop() { front_index = (front_index + 1) % capacity; num_items--; }

Chapter 6: Queues

32

Reallocating a Circular Array

Chapter 6: Queues

33

Implementing queue::reallocate void queue::reallocate() { size_t new_capacity = 2 * capacity; Item_Type* new_data = new Item_Type[new_capacity]; /*<snippet id="4" omit="false">*/ size_t j = front_index; for (size_t i = 0; i < num_items; i++) { new_data[i] = the_data[j]; j = (j + 1) % capacity; } /**/ front_index = 0; rear_index = num_items - 1; capacity = new_capacity; std::swap(the_data, new_data); delete[] new_data; } Chapter 6: Queues

34

Comparing the Three Implementations • All three are comparable in time: O(1) operations • Linked-lists require more storage • Singly-linked list: ~3 extra words / element • Doubly-linked list: ~4 extra words / element • Circular array: 0-1 extra word / element • On average, ~0.5 extra word / element

Chapter 6: Queues

35

The deque • The deque is an abstract data type that combines the features of a stack and a queue. • The name deque is an abbreviation for doubleended queue. • The C++ standard defines the deque as a fullfledged sequential container that supports random access.

Chapter 6: Queues

36

The deque class Member Function

const Item_Type& operator[](size_t index)const; Item_Type& operator[](size_t index) const Item_Type& at(size_t index) const; Item_Type& at(size_t index) iterator insert(iterator pos, const Item_Type& item) iterator erase(iterator pos) void remove(const Item_Type& item)

Behavior Returns a reference to the element at position index. Returns a reference to the element at position index. If index is not valid, the out_of_range exception is thrown. Inserts a copy of item into the deque at position pos. Returns an iterator that references the newly inserted item. Removes the item from the deque at position pos. Returns an iterator that references the item following the one erased. Removes all occurrences of item from the deque.

Chapter 6: Queues

37

The deque class (2) Member Function

void push_front(const Item_Type& item) void push_back(const Item_Type& item) void pop_front() void pop_back() Item_Type& front(); const Item_Type& front() const Item_Type& back(); const Item_Type& back() const iterator begin() const_iterator begin() const

Behavior

Inserts a copy of item as the first element of the deque Inserts a copy of item as the last element of the deque. Removes the first item from the deque. Removes the last item from the deque. Returns a reference to the first item in the deque. Returns a reference to the last item in the deque. Returns an iterator that references the first item of the deque. Returns a const_iterator that references the first item of the deque.

Chapter 6: Queues

38

The deque class (3) Member Function iterator end()

Behavior

Returns an iterator that references one past the last item of the deque. const_iterator end() const Returns a const_iterator that references one past the last item of the deque. void swap(deque
Chapter 6: Queues

39

Implementing the Deque Using a Circular Array • We can add the additional functions to the circular array based queue. • queue::push is the same as deque::push_back • queue::pop is the same as deque::pop_front. • Implementing deque::push_front and deque::pop_back are left as exercises. • Operator[] is implemented as follows: Item_Type& operator[](size_t index){ return the_data[(index + front_index) % capacity]; }

Chapter 6: Queues

40

The Standard Library Implementation • The standard library uses a randomly accessible circular array. • Each item in the circular array points to a fixed size, dynamically allocated array that contains the data. • The advantage of this implementation is that when reallocation is required, only the pointers need to be copied into the new circular array. Chapter 6: Queues

41

The Standard Library Implementation (2)

Chapter 6: Queues

42

The index operator template Item_Type& deque::operator[](size_t i) { if (i >= num_items) throw std::out_of_range ("Invalid index to deque::operator[]"); int block_index = (offset + i) / BLOCK_SIZE; int data_index = (offset + i) % BLOCK_SIZE; return the_data[block_index][data_index]; }

Chapter 6: Queues

43

The push_back functions template void deque::push_back(const Item_Type& item) { int capacity = the_data.size() * BLOCK_SIZE; if ((num_items + offset) == capacity) { the_data.push_back(new Item_Type[BLOCK_SIZE]); } num_items++; (*this)[num_items - 1] = item; }

Chapter 6: Queues

44

The pop_front function template void deque::pop_front() { offset++; if (offset == BLOCK_SIZE) { delete[] the_data.front(); the_data.pop_front(); offset = 0; } num_items--; }

Chapter 6: Queues

45

Simulating Waiting Lines Using Queues • Simulation is used to study the performance: • Of a physical (“real”) system • By using a physical, mathematical, or computer model of the system • Simulation allows designers to estimate performance • Before building a system • Simulation can lead to design improvements • Giving better expected performance of the system Chapter 6: Queues

46

Simulating Waiting Lines Using Queues (2) • Simulation is particular useful when: • Building/changing the system is expensive • Changing the system later may be dangerous • Often use computer models to simulate “real” systems • Airline check-in counter, for example • Special branch of mathematics for these problems: Queuing Theory

Chapter 6: Queues

47

Simulate Strategies for Airline Check-In

Chapter 6: Queues

48

Simulate Airline Check-In • • 3. 4. 5. 6. 7.

We will maintain a simulated clock • Counts in integer “ticks”, from 0 At each tick, one or more events can happen: Frequent flyer (FF) passenger arrives in line Regular (R) passenger arrives in line Agent finishes, then serves next FF passenger Agent finishes, then serves next R passenger Agent is idle (both lines empty) Chapter 6: Queues

49

Simulate Airline Check-In (2) •

Simulation uses some parameters: • Max # FF served between regular passengers • Arrival rate of FF passengers • Arrival rate of R passengers • Service time • Desired output: • Statistics on waiting times, agent idle time, etc. • Optionally, a detailed trace Chapter 6: Queues

50

Simulate Airline Check-In (3) •

Design approach: • Agent data type models airline agent • Passenger data type models passengers • 2 queue<Passenger>, 1 for FF, 1 for R • Overall Airline_Checkin_Sim class

Chapter 6: Queues

51

Simulate Airline Check-In (4)

Chapter 6: Queues

52

Airline_Checkin_Sim Design Data Field

Attribute

Passenger_Queue frequent_flyer_queue Passenger_Queue regular_passenger_queue int frequent_flyer_max

The queue of frequent flyers. The queue of regular passengers

int max_processing_time int total_time bool show_all int clock int frequent_flyers_since_RP

Function void void void void

run_simulation() enter_data() start_serve() show_stats()

The maximum number of frequent flyers to serve between regular passengers. The maximum time to serve a passenger. The total time to run the simulation. A flag indicating whether to trace the simulation. The current clock time The number of frequent flyers served since the last regular passenger.

Behavior

Controls the simulation. Reads in the data for the simulation Initiates service for a passenger. Displays the summary statistics. Chapter 6: Queues

53

Passenger_Queue Design Data Field

Attribute

int total_wait

The queue of passengers The number from this queue that were served. The total time spent waiting by passengers that were in this queue. The name of this queue. The arrival rate for this queue.

queue<Passenger> the_queue int num_served

string queue_name double arrival_rate

Function

Behavior

Passenger_Queue(string Constructs a new queue with the specified queue_name) name. void check_new_arrival(int clock, Checks whether there was a new arrival for bool show_all) this queue and, if so, inserts a passenger int update(int clock, bool show_all) int get_total_wait() const int get_num_served() const

into the queue. Updates the total waiting time and number of passengers served when a passenger from this queue is served. Returns the total waiting time. Returns the number of passengers served. Chapter 6: Queues

54

Passenger Design Data Field

int passenger_id int processing_time int arrival_time static int max_processing_time static int id_num

Function

Passenger(int arrival_time)

int get_arrival_time() const int get_processsing_time() const static void set_max_processing_time(int max_process_time)

Attribute The ID number for this passenger The time needed to process this passenger The time this passenger arrives The maximum time to process a passenger The sequence number for passengers

Behavior

Constructs a new passenger, assigns a unique ID and the specified arrival time. Computes a random processing time in the range 1 to max_processing_time. Returns arrival_time Returns processing_time Sets the max_processing_time.

Chapter 6: Queues

55

The main function int main() { Airline_Checkin_Sim simulation; simulation.enter_data(); simulation.run_simulation(); simulation.show_stats(); }

Chapter 6: Queues

56

The enter_data function Internal variable

frequent_flyer_queue.arrival_rate

Attribute

Expected number of frequent flyer arrivals per hour. regular_passenger_queue.arrival_rate Expected number of regular passenger arrivals per hour. max_processing_time Maximum service time in minutes. total_time Total simulation time. show_all Flag, if true display minuteby-minute trace of simulation. Chapter 6: Queues

Conversion Divide input by 60 to obtain arrivals per minute. Divide input by 60 to obtain arrivals per minute. None None. If input begins with 'y' or 'Y' set to true.

57

The run_simulation function void Airline_Checkin_Sim::run_simulation() { for (clock = 0; clock < total_time; clock++) { frequent_flyer_queue.check_new_arrival(clock, show_all); regular_passenger_queue.check_new_arrival(clock, show_all); if (clock >= time_done) { start_serve(); } } }

Chapter 6: Queues

58

The start_serve function void Airline_Checkin_Sim::start_serve() { if (!frequent_flyer_queue.empty() && ( (frequent_flyers_since_RP <= frequent_flyer_max) || regular_passenger_queue.empty())) { // Serve the next frequent flyer. frequent_flyers_since_RP++; time_done = frequent_flyer_queue.update(clock, show_all); } else if (!regular_passenger_queue.empty()) { // Serve the next regular passenger. frequent_flyers_since_RP = 0; time_done = regular_passenger_queue.update(clock, show_all); } else if (show_all) { cout << "Time is " << clock << ": Server is idle\n"; } } Chapter 6: Queues

59

Passenger_Queue::check_arrival void Passenger_Queue::check_new_arrival(int clock, bool show_all) { if (my_random.next_double() < arrival_rate) { the_queue.push(Passenger(clock)); if (show_all) { cout << "Time is " << clock << ": " << queue_name << " arrival, new queue size is " << the_queue.size() << endl; } } }

Chapter 6: Queues

60

Passenger_Queue::update int Passenger_Queue::update(int clock, bool show_all) { Passenger next_passenger = the_queue.front(); the_queue.pop(); int time_stamp = next_passenger.get_arrival_time(); int wait = clock - time_stamp; total_wait += wait; num_served++; if (show_all) { cout << "Time is " << clock << ": Serving " << queue_name << " with time stamp " << time_stamp << endl; } return clock + next_passenger.get_processing_time(); }

Chapter 6: Queues

61

Passenger Implementation Passenger::Passenger(int arrive_time) { arrival_time = arrive_time; processing_time = 1 + my_random.next_int(max_processing_time); passenger_id = id_num++; }

Chapter 6: Queues

62

Concerning “Random” Numbers • Not really random, but pseudo-random • Generated by a definite algorithm • Next produced from the last • Thus, sequence determined by starting value • Starting value is called the seed • Seed usually set from date/time, but can set directly to get same sequence on each occasion • Good for testing!

Chapter 6: Queues

63

Concerning “Random” Numbers (2) • The C++ standard library contains the functions rand and srand. • These are declared in and are the same as used by C. • The function rand generates an integer between 0 and RAND_MAX. • The function srand sets the starting value (known as the seed). • If the same seed is used, the same sequence of random numbers is generated. Chapter 6: Queues

64

The Random class

/** Class to encapsulate the standard random number generator. */ class Random { public: Random() { std::srand(std::time(0)); } Random(int seed) { std::srand(seed); } int next_int(int n) { return int(next_double() * n); } double next_double() { return double(std::rand()) / RAND_MAX; } };

Chapter 6: Queues

65