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. TypeScript uses arrays to create a stack, leveraging the push() method to add an element to the end of the array and the pop() method to remove the last element. These methods help implement the LIFO behavior, with type safety enforced through type annotations.
Let's explore this using a pile of plates.
TypeScript1class StackOfPlates { 2 private stack: string[]; 3 4 constructor() { 5 this.stack = []; 6 } 7 8 // Inserts a plate at the top of the stack 9 push(plate: string): void { 10 this.stack.push(plate); 11 } 12 13 // Removes the top plate from the stack 14 pop(): string { 15 if (this.stack.length === 0) { 16 return "No plates left to remove!"; 17 } 18 return this.stack.pop()!; 19 } 20} 21 22// Create a stack of plates 23const plates = new StackOfPlates(); 24plates.push('Plate'); // Pushing a plate 25plates.push('Another Plate'); // Pushing another plate 26// Let's remove a plate; it should be the last one we added. 27console.log('Removed:', plates.pop()); // 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, similar to waiting in line at the grocery store where the first person to arrive is the first to be served. In TypeScript, we can use arrays to achieve this behavior, using enqueue() for enqueueing (insertion at the end) and dequeue() for dequeueing (removal from the front).
Let's examine this through a queue of people.
TypeScript1class QueueOfPeople { 2 private queue: string[]; 3 4 constructor() { 5 this.queue = []; 6 } 7 8 // Add a person to the end of the queue 9 enqueue(person: string): void { 10 this.queue.push(person); 11 } 12 13 // Remove the first person from the queue (who has been waiting the longest) 14 dequeue(): string { 15 if (this.queue.length === 0) { 16 return "No people left to dequeue!"; 17 } 18 return this.queue.shift()!; 19 } 20} 21 22// Create a queue of people 23const people = new QueueOfPeople(); 24people.enqueue('Person 1'); // Person 1 enters the queue 25people.enqueue('Person 2'); // Person 2 arrives after Person 1 26// Who's next in line? It must be Person 1! 27console.log('Removed:', people.dequeue()); // 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, where the most recent pages are accessed first, allowing for quick reversal of actions. They are ideal for scenarios requiring last-in operations to be executed first, like undo mechanisms in text editors or depth-first search algorithms in graph traversals. On the other hand, Queues are optimal when the order of arrival is essential, such as in processing tasks or requests, where fairness is required so that each task or request is handled sequentially. This structure is well-suited for use cases like printer spool management or breadth-first search algorithms, where the first element needs to be processed ahead of the others.
Let's illustrate these two structures within a text editor that incorporates an Undo mechanism, represented by a Stack, and a Print Queue, exemplified by a Queue.
TypeScript1class TextEditor { 2 private stack: string[]; 3 private queue: string[]; 4 5 constructor() { 6 this.stack = []; 7 this.queue = []; 8 } 9 10 // Make a change (e.g., edit text, insert image, change font) 11 makeChange(action: string): void { 12 this.stack.push(action); // Add to the stack of actions 13 } 14 15 // Undo the most recent change 16 undoChange(): string { 17 if (this.stack.length === 0) { 18 return "No changes to undo!"; 19 } 20 return this.stack.pop()!; 21 } 22 23 // Add a document to the queue for printing 24 addToPrint(doc: string): void { 25 this.queue.push(doc); 26 } 27 28 // Print the document that has been waiting the longest 29 printDoc(): string { 30 if (this.queue.length === 0) { 31 return "No documents in print queue!"; 32 } 33 return this.queue.shift()!; 34 } 35} 36 37// Use our text editor! 38const editor = new TextEditor(); 39editor.makeChange("Changed font size"); // Make a change 40editor.makeChange("Inserted image"); // Make another change 41// Let's undo a change. It should be the last change we made. 42console.log('Undo:', editor.undoChange()); // Undo: Inserted image 43 44editor.addToPrint("Proposal.docx"); // Queue a document for printing 45editor.addToPrint("Report.xlsx"); // Queue another document 46// Let's print a document. It should be the document that has been waiting the longest. 47console.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!