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. JavaScript uses arrays to create a stack, with push() used for insert (push), and pop() used for remove (pop, return the element that has been removed).
Let's explore this using a pile of plates.
JavaScript1class StackOfPlates { 2 constructor() { 3 this.stack = []; 4 } 5 6 // Inserts a plate at the top of the stack 7 addPlate(plate) { 8 this.stack.push(plate); 9 } 10 11 // Removes the top plate from the stack 12 removePlate() { 13 if (this.stack.length === 0) { 14 return "No plates left to remove!"; 15 } 16 return this.stack.pop(); 17 } 18} 19 20// Create a stack of plates 21const plates = new StackOfPlates(); 22plates.addPlate('Plate'); // Pushing a plate 23plates.addPlate('Another Plate'); // Pushing another plate 24// Let's remove a plate; it should be the last one we added. 25console.log('Removed:', plates.removePlate()); // Outputs: Removed: Another Plate
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. In JavaScript, we can use arrays to achieve this behavior, using push() for enqueue (insert at the end) and shift() for dequeue (remove from the front, return the element that has been removed).
Let's examine this through a queue of people.
JavaScript1class QueueOfPeople { 2 constructor() { 3 this.queue = []; 4 } 5 6 // Add a person to the end of the queue 7 enqueuePerson(person) { 8 this.queue.push(person); 9 } 10 11 // Remove the first person from the queue (who has been waiting the longest) 12 dequeuePerson() { 13 if (this.queue.length === 0) { 14 return "No people left to dequeue!"; 15 } 16 return this.queue.shift(); 17 } 18} 19 20// Create a queue of people 21const people = new QueueOfPeople(); 22people.enqueuePerson('Person 1'); // Person 1 enters the queue 23people.enqueuePerson('Person 2'); // Person 2 arrives after Person 1 24// Who's next in line? It must be Person 1! 25console.log('Removed:', people.dequeuePerson()); // Outputs: Removed: Person 1
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.
JavaScript1class TextEditor { 2 constructor() { 3 this.stack = []; 4 this.queue = []; 5 } 6 7 // Make a change (e.g., edit text, insert image, change font) 8 makeChange(action) { 9 this.stack.push(action); // Add to the stack of actions 10 } 11 12 // Undo the most recent change 13 undoChange() { 14 if (this.stack.length === 0) { 15 return "No changes to undo!"; 16 } 17 return this.stack.pop(); // Remove the last action from the stack 18 } 19 20 // Add a document to the queue for printing 21 addToPrint(doc) { 22 this.queue.push(doc); 23 } 24 25 // Print the document that has been waiting the longest 26 printDoc() { 27 if (this.queue.length === 0) { 28 return "No documents in print queue!"; 29 } 30 return this.queue.shift(); // Remove the first document from the queue 31 } 32} 33 34// Use our text editor! 35const editor = new TextEditor(); 36editor.makeChange("Changed font size"); // Make a change 37editor.makeChange("Inserted image"); // Make another change 38// Let's undo a change. It should be the last change we made. 39console.log('Undo:', editor.undoChange()); // Undo: Inserted image 40 41editor.addToPrint("Proposal.docx"); // Queue a document for printing 42editor.addToPrint("Report.xlsx"); // Queue another document 43// Let's print a document. It should be the document that has been waiting the longest. 44console.log('Print:', editor.printDoc()); // Print: Proposal.docx
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!