Stacks and queues are two important data structures which are used to arrange, store and manage collections of data in programming. Both of these structures are capable of storing more than one element, but there are primary differences in how elements are added and removed from the structures. There is a distinction between them, which is important for programmers because they sometimes have to control the order of the tasks, the values, the requests, or the operations. A stack is a data structure that follows the Last in First Out (LIFO) principle, which is to say that the last element inserted into the stack is the first one to be removed. The “first in, first out” (FIFO) principle applies to a queue: the first element put in the queue is the first one to come out. These ideas might be technical at first, but are easier to understand when related to a set of books, people queuing, the history of the browser, printing out a job, work waiting to be done on a computer system, etc.
What Is a Stack?
Stacks are linear data structures where the latest added element is the first one to be removed. This is referred to as Last in, First Out or LIFO. A common real world application is a stack of plates in a kitchen. When a number of plates are stacked one on top of another, the most recent one on the top is typically the easiest plate to remove.
A plate is not normally removed from the middle as this will disrupt the other plates above the plate being removed. Programming stacks are similar. push is a common operation used to add an element to the top of the stack, and pop is a common operation used to remove an element from the top of the stack. A stack can also have an operation called peek, which lets a program view the top element without taking it out.
LIFO Principle
A stack is based on the concept of LIFO. Suppose that the program pushes 10, 20, and 30 onto an empty stack, pushing the numbers in that order onto the stack. Following these operations, 30 is on top, 20 is on the bottom, and 10 is underneath. If the program does a pop operation, then 30 is removed first. The second pop takes 20 and the third pop takes 10.
The values are thus removed from the last to the first position, in reverse order from which they were inserted. A commonly used scenario is one that requires a program to temporarily store data and then retrieve the last data stored so that older data can be processed. Stacks are then appropriate for use when the most recent action, request or piece of information must be processed first.
How to Program a Simple Stack.
In many programming languages the stack may be implemented as an array, a list, or a specific stack class. For instance, in Python, there is a list and operations are possible to add and remove elements from the end of it. An example conceptually would be to create an empty list, add the value 10, then add 20, and then add 30. The program could then delete the last element (30), then the next (20), then the next (10).
This is an example of LIFO without any complex implementation! The same can be done in a larger software system with many different types of data, such as actions performed by users, navigation states, temporary calculations, program execution data, etc. The key is that the order of the management of stack elements is controlled, not the programming language.
Applications of Stacks in the Real World and in Programming.
The usefulness of stacks is that many operations of a computer are naturally intended to be performed in the reverse direction, that is, the most recent data is processed first. A good example is the handling of function calls in a program. The computer must store data about the currently active function to return to it when the new function returns. This information is generally linked to a call stack. Every time a function is called it pushes a new frame onto the stack with the information needed to execute the function. The end of the function causes an exit from the function frame which puts the execution back in the previous frame. Nesting of function calls is an example of LIFO behavior, as a function can call another function which can call another function, and so on. This is the reason why a stack is a suitable structure for keeping track of nesting.
Stacks are also often related to browser browsing history and navigation. If a user moves to other pages, software can keep track of what pages he or she has previously visited, and provide the ability to roll back and visit a previous page. While real browser implementations might be more complicated than a simple stack, the concept of a stack is a great approach to understanding how a history system can work. If a user walks through a number of states and then chooses an operation that returns him to the latest previous state, the latest stored state might be processed first. This broader notion can also be applied to software functionality that requires retaining past states and undoing operations. Learning about stacks enables novices to grasp why “Last In First Out” is more than just a classroom description and indeed a workable way of handling varying information.
A common application of stacks is the undo operation that is available in many computer programs. Imagine a text editor in which a user types multiple sentences, removes a word and then changes the formatting of another part of the text. The application can store data on these actions to allow for the undoing of the most recent action. Pressing Undo once will undo the most recent action. If the user presses it again, the action before that is reversed. This is of course similar to LIFO, as the most recent operation is taken care of prior to older operations. For more sophisticated applications, one might want to use special structures and other rules, but the stack serves as a convenient example for understanding undo systems and how they can be used to record a series of changes. The concept can be used in drawing applications, code editors, design tools, spreadsheets and other interactive software.
What Is a Queue?
Another linear data structure is the queue which typically operates on the First In First Out (FIFO) principle, unlike a stack. FIFO means “first in first out,” which means that the first element placed into the queue must be the first element to be removed. The simplest real world example is a line of people waiting at a service counter. Normally Person A will get service first, followed by Person B and then Person C, if Person A arrives before Person B and Person C.
The same is true for a programming queue. New elements are typically added to one end (the rear), and elements are removed from the other end (the front). This way software can respond to requests in the order they are received. Queues are especially helpful if the need is for a fair, sequential, and orderly processing of elements.
Importance of the Concept of FIFO
If the queue is empty, what are the values that will be placed in it in order, 10, 20, or 30? The value 10 comes first because it has the highest value, but 30 is the last value because it has the lowest value. If an element is deleted from the program, 10 is deleted first. The third removal yields 20, the fourth removal yields 30. Thus, the order of removal is the same as the order of insertion.
This is the main “FIFOing” factor. The following are typical terms used to describe queue operations: enqueue: add an element to the queue, dequeue: remove an element from the front. A queue can also be used to examine the current element of the queue without removing it. The operations of these queues are useful for managing tasks that are generally meant to be done in the order in which they are received.
Using Queues in Data Processing Systems
The systems can be flooded with a lot of records, messages, requests or other information that must be systematically processed. When the flow rate into a system exceeds the flow rate out, a queue may temporarily buffer items that enter the system. The system can queue the requests rather than lose them or process them in an uncontrolled way and delegate them to available resources based on set rules.
Queue-based processing can be used to decouple the information that is added to a queue from the processing that is done on that information in large software environments. The concept is especially useful in cases where workloads come in at different speeds or when processing resources must process information over time as opposed to all at once.
Queues in Real World and Programming Applications
Examples of FIFO behavior can be easily understood in the context of printer queues. Suppose there are multiple employees in an office that print documents to the same printer. When the first employee sends a document, the second employee sends another document, and the third employee sends a third document, the printer can put these jobs in a queue. The jobs can then be processed according to their position in the queue. This avoids that the printer would arbitrarily select documents and also gives a structured approach to handle multiple requests. Printing systems can be simple FIFO, or advanced such as prioritization, cancellation and more. Still, the core printer queue is a wonderful illustration of the use of a queue to coordinate jobs waiting for a common resource.
Another interesting use of queues is task scheduling. Computers often need to perform more tasks than they can do concurrently, especially if many requests come in around the same time. Tasks may be stored in a queue until a processing resource is ready to process them. For instance, several user requests could come into a web application, and a processing system could sort these requests and process them. Queues are also utilized in operating systems, background processing services, messaging systems and server applications. A system can employ a simple FIFO queue, or implement a more sophisticated scheduling algorithm depending on the needs, which may take into account priority, deadlines, or available resources. The knowledge of the basic queue model provides a basis for understanding the more advanced scheduling systems.
Queues are also significant in communication between different components of a software system. One component can produce information at a rate faster than the other component can process. The speed of the components need not be the same, as a queue can temporarily hold the information between the components. For instance, one segment of an application may generate messages, whereas another segment of an application may handle messages. The producer can enqueue new messages and the consumer can dequeue them when it is ready to do so. This can be used to make software systems more flexible as temporary differences between workload does not mean that the system as a whole has to come to a halt. For larger applications, reliability, scaling, monitoring, and error handling mechanisms can be added to the queue-based communication.
Difference between Stacks and Queues
Stacks and Queues are really quite similar with the exception that they remove elements in different orders. A stack is LIFO, that is, the last element inserted is the first element to be removed. A queue is based on FIFO, which means that the first item added to the queue is typically the first one to be removed. This difference dictates the structure of the program to a specific problem. A stack like approach might be appropriate if a program must undo an action, if it must work with the latest stored item, or if it must repeatedly work with the newest stored item and it must be doing several actions at the same time.
A queue-like approach may be more suitable if a program requires processing requests in order of arrival, to have to deal with waiting tasks or to have to use jobs that compete for a shared resource. Both are not inherently superior, since they are geared towards addressing different organizational issues.
Why Stacks and Queues Matter in Software Development
Stacks and Queues are important because they help the programmer to think of a way to organize and move information around. Programming isn’t just about storing values; it’s also about making decisions about when to access, process, remove, or temporarily store information. Stacks give controlled access to the most recently added element and queues give controlled access according to arrival order.
These basic ideas are used in many large-scale programming ideas such as algorithms, operating systems, networking, application development and information processing. When novices know these structures, they will be better able to discern when one way of organizing information is necessary rather than another for a given problem. The concepts also serve as a stepping stone to further advanced data structures and algorithms.
The decision between a stack and a queue is based on the order that information must be processed. A programmer should query to see if the newest item should be dealt with first or if the oldest waiting item should be dealt with first. A stack could match a problem quite naturally, if the most recent one has to be the most important. Generally, the oldest item should be dealt with first, but a queue might be better.
Additional factors should also be taken into account when developing a program, such as if items must be accessed from the middle, if priorities must be supported, the amount of memory available, and the performance characteristics of the program. In real software, specializations of stacks and queues can offer other features, but it is important to be familiar with the basic LIFO and FIFO models.
Conclusion
Stacks and queues are simple but powerful data structures which are used to control information storage and processing by the programmers. The Last In First Out principle is applicable to a stack that can be used when there is a need to deal with recently performed actions, nested operations, function calls and undo behavior. A queue is implemented in First In First Out manner and it is useful for waiting tasks, printer jobs, requests, messages and other processes that are, in general, required to be executed in the order in which they are received.
These concepts are made easy to visualize through examples from the real world, including examples of piles of plates, as well as examples of lines of people, and programming examples demonstrate how the concepts can be used to solve real-world software problems. Knowing the difference between LIFO and FIFO, and knowing when to use either, helps beginners to lay a foundation for learning more about data structures, algorithms, and software development.
