Welcome to an exciting exploration of two fundamental data structures: Stacks and Queues! Remember, data structures store and organize data in a manner that is structured and efficient. Stacks and Queues are akin to stacking plates and standing in a line, respectively. Intriguing, isn't it? Let's dive in!
A Stack adheres to the "Last In, First Out" or LIFO principle. It's like a pile of plates where the last plate added is the first one to be removed. C++ provides the std::stack container from the Standard Library to work with stacks. The primary methods used with stacks are push, pop, empty, and top:
- push: Adds an element to the top of the stack.
- pop: Removes the top element from the stack.
- empty: Checks whether the stack is empty.
- top: Returns the top element of the stack without removing it.
Let's explore this using a pile of plates.
C++1#include <iostream> 2#include <stack> 3 4class StackOfPlates { 5public: 6 // Inserts a plate at the top of the stack 7 void add_plate(const std::string &plate) { 8 stack.push(plate); // Using push to add a plate 9 } 10 11 // Removes the top plate from the stack 12 std::string remove_plate() { 13 if (stack.empty()) { // Using empty to check if stack is empty 14 return "No plates left to remove!"; 15 } 16 std::string topPlate = stack.top(); // Using top to access the top plate 17 stack.pop(); // Using pop to remove the top plate 18 return topPlate; 19 } 20 21private: 22 std::stack<std::string> stack; 23}; 24 25// Main function to demonstrate stack usage 26int main() { 27 StackOfPlates plates; 28 plates.add_plate("Plate"); // Pushes a plate 29 plates.add_plate("Another Plate"); // Pushes another plate 30 31 // Let's remove a plate; it should be the last one we added. 32 std::cout << "Removed: " << plates.remove_plate() << std::endl; // Outputs: Removed: Another Plate 33 34 return 0; 35}
The last plate added was removed first, demonstrating the LIFO property of a stack.
A Queue represents the "First In, First Out" or FIFO principle, much like waiting in line at the grocery store. C++ provides the std::queue container from the Standard Library to work with queues. The primary methods used with queues are push, pop, empty, and front:
- push: Adds an element to the end of the queue.
- pop: Removes the first element from the queue.
- empty: Checks whether the queue is empty.
- front: Returns the first element of the queue without removing it.
Let's examine this through a queue of people.
C++1#include <iostream> 2#include <queue> 3 4class QueueOfPeople { 5public: 6 // Adds a person to the end of the queue 7 void enqueue_person(const std::string &person) { 8 queue.push(person); // Using push to add a person 9 } 10 11 // Removes the first person from the queue (who has been waiting the longest) 12 std::string dequeue_person() { 13 if (queue.empty()) { // Using empty to check if queue is empty 14 return "No people left to dequeue!"; 15 } 16 std::string frontPerson = queue.front(); // Using front to access the first person 17 queue.pop(); // Using pop to remove the first person 18 return frontPerson; 19 } 20 21private: 22 std::queue<std::string> queue; 23}; 24 25// Main function to demonstrate queue usage 26int main() { 27 QueueOfPeople people; 28 people.enqueue_person("Person 1"); // Person 1 enters the queue 29 people.enqueue_person("Person 2"); // Person 2 arrives after Person 1 30 31 // Who's next in line? It must be Person 1! 32 std::cout << "Removed: " << people.dequeue_person() << std::endl; // Outputs: Removed: Person 1 33 34 return 0; 35}
Here, Person 1, the first to join the queue, left before Person 2, demonstrating the FIFO property of a queue.
Stacks handle ordered data efficiently, much like your web browser's history. Queues, on the other hand, are optimal when the order of arrival is essential, such as in a store queue.
Let's depict the two structures in a text editor that features an Undo mechanism (a Stack) and a Print Queue.
C++1#include <iostream> 2#include <stack> 3#include <queue> 4 5class TextEditor { 6public: 7 // Makes a change (e.g., edits text, inserts image, changes font) 8 void make_change(const std::string &action) { 9 stack.push(action); // Adds to the stack of actions 10 } 11 12 // Undoes the most recent change 13 std::string undo_change() { 14 if (stack.empty()) { 15 return "No changes to undo!"; 16 } 17 std::string lastAction = stack.top(); 18 stack.pop(); 19 return lastAction; 20 } 21 22 // Adds a document to the queue for printing 23 void add_to_print(const std::string &doc) { 24 queue.push(doc); 25 } 26 27 // Prints the document that has been waiting the longest 28 std::string print_doc() { 29 if (queue.empty()) { 30 return "No documents in the print queue!"; 31 } 32 std::string nextDocument = queue.front(); 33 queue.pop(); 34 return nextDocument; 35 } 36 37private: 38 std::stack<std::string> stack; 39 std::queue<std::string> queue; 40}; 41 42// Main function to demonstrate TextEditor usage 43int main() { 44 TextEditor editor; 45 editor.make_change("Changed font size"); // Makes a change 46 editor.make_change("Inserted image"); // Makes another change 47 48 // Let's undo a change. It should be the last change we made. 49 std::cout << "Undo: " << editor.undo_change() << std::endl; // Outputs: Undo: Inserted image 50 51 editor.add_to_print("Proposal.docx"); // Queues a document for printing 52 editor.add_to_print("Report.xlsx"); // Queues another document 53 54 // Let's print a document. It should be the document that has been waiting the longest. 55 std::cout << "Print: " << editor.print_doc() << std::endl; // Outputs: Print: Proposal.docx 56 57 return 0; 58}
This code reintroduces the concepts of a Stack (Undo feature) and Queue (Print queue) in the context of a real-life scenario.
Great work! You have examined the mechanics of Stacks and Queues, both integral data structures. Remember to practice what you've learned. Happy coding!