What is a Stack?
A Stack is a commonly utilized abstract data type and data structure that obeys the LIFO (Last in First out) strategy. This ensures that the last added item will be removed first. A stack allows for push and pop operations. The push function adds another item to the stack whereas the pop operation removes an item from the top position.
A stack can be fixed in size or dynamically implemented if the size of the stack is allowed to change during runtime. In fixed capacity stacks, attempting to add an item to a full stack causes a stack overflow exception. Likewise, when a pop operation removes an item from an already empty stack, a stack underflow exception will be thrown.
You can use arrays and linked lists to implement a stack where the top position must be tracked using a header pointer or variable.
Some examples of how the stack is being used in programming can be found below.
Examples that use Stacks
Sorting Algorithms
A Stack can be used for Sorting Algorithms like Quicksort, a fast, recursive, unstable sorting algorithm that works on the principle of divide and conquer.
Backtracking
Backtracking is a technique for finding solutions to "Constraint satisfaction problems" It lists all possible solutions and then discards those that do not meet the constraints.
The classical technique consists of exploring the tree structures and keeping track of all the nodes and branches previously visited, in order to be able to return to the nearest node containing the path still unexplored if the search in the current branch has not been successful - This can be done with the help of a stack.
One application of backtracking is playing chess - the program will generate all possible moves for a depth of N moves starting from the current one, and then it examines the different backtracking alternatives, selecting the best one at the end.
Syntax Parsing
A Parser is a program that compilers typically use, which gets as input data: program blocks, expressions, etc., and divides them into parts that other compiler components can then manage.
The parser will also test if all inputs are provided.
Managing an undo Function
Stacks are also used to keep information for Undo Functions, which are implemented in a number of programs. It erases the last change made to a document, an image, etc. by reverting it to an older version, so people can edit something without the fear of making mistakes, because they can be reversed easily.
Parenthesis Checking
Writing a Program to check if Parenthesis like () {} [] are closed is a very popular question for an interview - this is often used in a compiler to check if the Syntax is correct. This task can be done easily by using Stacks and saving the openings and closing Parenthesis in it.
String Reversal
A stack can be used to reverse a string. We just push all the characters of the string one by one into the stack and then pop the characters out of the stack - since the stack obeys the strategy of LIFO (Last in First Out), the first character we pop will be the last of the string.
What is a Queue?
A queue is a collection that obeys the FIFO (First-in First-out) strategy. It is similar to a line of people at the grocery Store - the first Person who got there will be served first and the last person last. If another person goes to the cash register he will be "added" to the back of the queue.
A queue allows only two operations which are enqueue and dequeue. Enqueue means inserting an item at the back of the queue while dequeue means removing the first item. This graphic visualizes the first-in first-out (FIFO) strategy.
The only difference between a stack and a queue is the removing part. In a stack we remove the item that was most recently added - in a queue, we remove the item the least recently added.
Examples that use Queues
Resource Scheduling
If Multiple processes / users have to use the same system (CPU, Hard-drive, etc.) the different tasks have to be scheduled so everyone gets the shortest possible response times while not blocking another process / user.
This is used on a low level by the CPU when working on different Applications (Web Browser, Games, Music Player and so on) at the same time - but also on a higher level when doing Asynchronous Data Transfers with an API where the Data first has to be calculated before it will be given back to the user.
Waiting for slow External Devices
Queues are also used for slow external devices, such as printers that are decoupled from program execution. After a print job is placed in the queue, the job is signaled to the program as "printed", but the job is actually executed only later when the device is available.
Order Taking
This is a very "High-level" example. The queue can be used for incoming orders in a Pizza Shop Computer System. For example, if someone orders a Pizza through a website, his order will be added to the Queue while the Pizza Shop removes Orders from the Queue when the Pizza was delivered.