Understanding Queues and Stacks in C++
Explore the concepts of queues and stacks in the context of programming in C++ with insights on their differences, applications like event queues, and a fun puzzle involving queues. Learn about FIFO and LIFO structures, and how they are used in various scenarios like hospital queues and boarding processes.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Creative Commons License CS2 in C++ Peer Instruction Materials by Cynthia Bailey Lee is licensed under a Creative Commons Attribution-NonCommercial- ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at http://peerinstruction4cs.org. CS 106X Programming Abstractions in C++ Cynthia Bailey Lee
2 Today s Topics 1. Queues contrasted with Stacks 2. Queues example: Mouse events 3. Queue example: Josephus Survivor Puzzle 4. Iterating using range-based for loop
Stacks vs. Queues Stack is referred to as a LIFO data structure Last in, first out Queue is referred to as a FIFO data structure First in, first out How many of these operate as FIFO/Queue? Patients waiting in a hospital Emergency Room Passengers boarding and exiting an airplane Passengers boarding and exiting an elevator (assume all board on ground floor and exit at the same destination) People waiting in line for an amusement park ride (A) None (B) 1 (C) 2 (D) All 3
LIFO: FIFO: Image is modified by Cynthia Lee based on original from Wikimedia Commons A seatmap over the Airbus A380 Source=self- made |Date=24 September 2007 |Author= S. Solberg J. Used under Creative Commons License
Queue Applications Mouse events
Event queues While your code executes, a separate program is constantly listening for events and recording them Mouse moved, mouse clicked, mouse dragged, keyboard key pressed, etc Every once in a while, your code can call getNextEvent() to see what has happened getNextEvent returns the events one at a time in the same order they happened In other words, returns them in FIFO order! When it is recording events, it is enqueuing events in an event QUEUE Very common use of the Queue ADT
Queue Applications Josephus Survivor Puzzle
Josephus Survivor Puzzle N people seated in a circle Skip M living people and kill the (M+1)th, repeatedly around the circle, until two remain Question: Where do you sit? 1 12 2 3 11 4 10 5 9 6 8 7
Josephus Survivor Puzzle Question: (you will need paper & pencil) N = 12, M = 3 Where do you sit? 1 or 2 1 or 6 C. 5 or 10 5 or 6 Other/none/more 1 12 2 A. 3 11 B. 4 10 D. 5 9 E. 6 8 7
Queues and Josephus Puzzle Enqueue everybody Dequeue and immediately re-enqueue M people. Dequeue somebody forever. If more than two alive, repeat steps 2&3 1. 2. 3. N = 5, M = 2 1. 2. 3. 2. 3. 2. 3. ?
Queues and Josephus Puzzle Enqueue everybody Dequeue and immediately re-enqueue M people. Dequeue somebody forever. If more than two alive, repeat steps 2&3 1. 2. 3. 4. N = 5, M = 2 Contents of the queue, reading from top down: 1, 2, 4 2, 4, 5 2, 4, 5, 1 4, 5, 1, 2 Other 1. 2. 3. 2. 3. 2. 3. A. 1 2 3 4 5 3 4 5 1 2 4 5 1 2 1 2 4 5 B. ? C. D. E.
Queues and Josephus Puzzle: What does that look like in code? Enqueue everybody Dequeue and immediately re-enqueue Mpeople. Dequeue somebody forever If more than two alive, repeat steps 2&3 1. 2. 3. 4.
C++11 has a nice for loop just for collections ADTs Range-based for loop gives you each item in a collection, one at a time For ADTs with a clear linear order (Vector, Stack, Queue), they are given to you in that order [Spoiler for Wednesday!] Some ADTs are not linear. In theory, we often consider the ordering of iteration on these to be undefined, but in practice some implementations allow you to rely on a certain order
C++11 range-based for loop One way to iterate over a Vector: for (int i=0; i<classlist.size(); i++){ cout << classlist[i] << endl; } Range-based for loop makes the code cleaner: for (string name : classlist){ cout << name << endl; }
Other iteration techniques in C++ (NOT recommended for this class) STL vector and iterators for (vector<int>::iterator it = classlist.begin(); it != classlist.end(); ++it){ cout << *it << endl; } Stanford library foreach loop (obsoleted by range- based for loop in C++11): foreach (string name in classlist){ cout << name << endl; }
