Bilgisayar Mühendisliği Bölümü
DATA STRUCTURES AND ALGORITHMS Lecture Notes 9 Queues Spring 2008
GIT – Computer Engineering Department
ROAD MAP 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 GIT – Computer Engineering Department
Simulation - Lecture Notes 8
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
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
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 – (Consider multiple queues, priorities, etc., later) – A stack would be inappropriate • 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 GIT – Computer Engineering Department
Simulation - Lecture Notes 8
4
A Print Queue (continued)
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
5
Specification of the Queue ADT Function
Behavior
bool empty() 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.
Item_Type& front(); const Item_Type& front() const void pop() void push(const Item_Type&) size_t size() const
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
6
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 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 ... GIT – Computer Engineering Department
Simulation - Lecture Notes 8
7
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; }
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
8
Maintain_Queue.cpp case 0: // Insert a new customer cout << "Enter new customer name\n"; cin >> name; customers.push(name); break; case 1: // Display the Next Customer cout << "Customer " << customers.front() << " is next in line\n"; break; case 2: // Remove the Next Customer cout << "Customer " << customers.front() << " removed from line\n"; customers.pop(); break; case 3: // Display the Length of the Line cout << "Size of line is " << customers.size() << endl; break; case 4: cout << "Leaving.\n" << "Number of customers in queue is " << customers.size() << endl; break; default: cout << "Invalid selection\n"; break; GIT – Computer Engineering Department
Simulation - Lecture Notes 8
9
ROAD MAP 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 GIT – Computer Engineering Department
Simulation - Lecture Notes 8
10
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 GIT – Computer Engineering Department
Simulation - Lecture Notes 8
11
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; };
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
12
Using a Single-Linked List to Implement a Queue (continued)
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
13
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
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
14
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; } else { back_of_queue->next = new Node(item, NULL); back_of_queue = back_of_queue->next; } num_items++; }
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
15
Implementing Queue: Singly-Linked List (4) template Item_Type& queue::front() { return front_of_queue->data; }
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
16
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--; }
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
17
Analysis of the Space/Time Issues Time efficiency of singly- or doubly-linked list good: O(1) for all Queue operations
Space cost: – Doubly Linked List: ~3 words per item – Singly Linked List: ~2 words per item – Vector: ~1.5 words per item on average • 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
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
18
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)
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
19
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
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
20
Implementing Queue With Circular Array (2)
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
21
Implementing Queue With Circular Array (3)
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
22
Implementing Queue With Circular Array (4)
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
23
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; };
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
24
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]) {}
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
25
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) (amortized)
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
26
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--; }
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
27
Reallocating a Circular Array
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
28
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; }
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
29
Comparing the Three Implementations All three are comparable in time: O(1) operations Linked-lists require more storage – Singly-linked list: ~1 extra words / element – Doubly-linked list: ~2 extra words / element
Circular array: 0-1 extra word / element – On average, ~0.5 extra word / element
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
30
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.
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
31
The deque class Member Function
Behavior
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)
Returns a reference to the element at position index.
iterator erase(iterator pos)
void remove(const Item_Type& item)
GIT – Computer Engineering Department
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.
Simulation - Lecture Notes 8
32
The deque class (2) Member Function
Behavior
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()
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.
const_iterator begin() const
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
33
The deque class (3) Member Function
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
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
34
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]; }
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
35
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.
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
36
The Standard Library Implementation (2)
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
37
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]; }
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
38
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; }
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
39
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--; }
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
40
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
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
41
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
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
42
Simulate Strategies for Airline Check-In
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
43
Simulate Airline Check-In We will maintain a simulated clock – Counts in integer “ticks”, from 0
At each tick, one or more events can happen: 1.Frequent flyer (FF) passenger arrives in line 2.Regular (R) passenger arrives in line 3.Agent finishes, then serves next FF passenger 4.Agent finishes, then serves next R passenger 5.Agent is idle (both lines empty) GIT – Computer Engineering Department
Simulation - Lecture Notes 8
44
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
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
45
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
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
46
Simulate Airline Check-In (4)
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
47
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.
int max_processing_time int total_time bool show_all int clock int frequent_flyers_since_RP
The queue of regular passengers 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.
Function
Behavior
void void void void
Controls the simulation. Reads in the data for the simulation Initiates service for a passenger. Displays the summary statistics.
run_simulation() enter_data() start_serve() show_stats()
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
48
Passenger_Queue Design Data Field
Attribute
queue<Passenger> the_queue int num_served
string queue_name double arrival_rate
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.
Function
Behavior
int total_wait
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
GIT – Computer Engineering Department
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. Simulation - Lecture Notes 8
49
Passenger Design Data Field
Attribute
int passenger_id int processing_time int arrival_time static int max_processing_time static int id_num
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
Function
Behavior
Passenger(int arrival_time)
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.
int get_arrival_time() const int get_processsing_time() const static void set_max_processing_time(int max_process_time)
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
50
The main function int main() { Airline_Checkin_Sim simulation; simulation.enter_data(); simulation.run_simulation(); simulation.show_stats(); }
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
51
The enter_data function Internal variable
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. frequent_flyer_queue.arrival_rate
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
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.
52
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(); } } }
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
53
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"; } }
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
54
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; } } }
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
55
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(); }
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
56
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++; }
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
57
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!
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
58
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 GIT – Computer Engineering Department
Simulation - Lecture Notes 8
59
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; } };
GIT – Computer Engineering Department
Simulation - Lecture Notes 8
60