Profile
Settings
Refer your friends
Sign out
Many daily instances have exposed you to the notion of a stack. You’ve probably seen a stack of books on a desk or a stack of dishes in a café. The highest value is the simplest element to obtain among the elements in the collection, which is a feature shared by these instances. For example, in a stack of plates, the first accessible plate is at the top. That is the only object you are permitted to access under a genuine stack abstraction.
Furthermore, stack operations adhere to the last-in, first-out (LIFO) concept. When a new plate is added to the stack, the previous topmost plate becomes unavailable. Only once the freshly added plate is removed does the prior top of the stack become available again. If you remove all the items from a stack, you will be able to access them in reverse chronological order – the first thing removed will be the most recently placed item on the stack, and the final item removed will be the value that has been stored in the stack for the longest length of time.
Stack
A stack is an Abstract Data Type (ADT) found in almost all computer languages. It is called a stack because it behaves like a real-world stack, such as a deck of cards or a pile of dishes. A real-world stack can only perform operations at one end. For instance, we can only add or take a card or plate from the top of the stack. Similarly, Stack ADT permits all data operations at only one end. We can only access the top element of a stack at any given time. Stacks are utilised in a wide range of computer applications.
Applications of Stacks
Web Browser Back and Forward Buttons
The current web page is kept on a stack each time the user navigates to a new web page. When you press the back button, the topmost member of this stack is opened up, and the related web page is displayed.
However, such explanations only told half of the story. Two stacks are used to allow the user to travel forward and backward. The URL to the current web page is kept on a separate stack for the forward button when the user pushes the back button. As the user navigates backwards through previous pages, the link to each page is shifted from the back to the forward stack in turn. When a user presses the forward button, the action is the opposite of pressing the back button. The forward stack item is now popped and becomes the current web page. The preceding web page gets moved to the bottom of the stack.
Character Input with Buffering
A stack is used by an operating system to appropriately interpret backspace keys in lines of input entered at a keyboard. Assume you type numerous keys and then uncover a typo. To travel backwards over a previously input character, hit the backspace key. To remove more than one character, use several backspaces in succession.
If we use < to represent the backspace character, assume that correcktw<<<<t tw<ext. is typed . Because it keeps the characters as they are read in a stack-like form, the operating system function that handles character input will arrive at the right text. Every non-backspace character is simply moved to the top of the stack. When a backspace is typed, the topmost character in the stack is popped and deleted.
Expression Handling
Conversion of Infix to Postfix or Infix to Prefix –
The stack may be used to transform an infix expression into its postfix or prefix counterpart. In computers, these postfix or prefix notations are used to represent certain phrases. These expressions are not as well known as the infix expression, but they offer some significant advantages. We don’t need to keep operator ordering or parenthesis.
Postfix or Prefix Evaluation –
After translating the expression into prefix or postfix notations, we must evaluate it to obtain the result. We also require the assistance of the stack data structure for this reason.
Backtracking Procedure
Backtracking is a technique used in algorithm creation. For that, we plunge into some path; if that path is inefficient, we return to the prior state and pursue alternative pathways. To return from the present state, we must first save the prior state. Stack is required for this purpose. Finding a solution to the Knight Tour issue or the N-Queen problem, for example, is an example of backtracking.
Examining the Balanced Parenthesis
A program to check for balanced parentheses and brackets is a basic application that will demonstrate the usage of stack operations. By balanced, we mean that every open parenthesis has a matching close parenthesis and that the parenthesis is appropriately nested. We’ll make the situation a little more challenging by considering both parenthesis and brackets. The rest of the cast is just disregarded.
Thus, the inputs (x(y)(z)) and a((b)c) are balanced, but the inputs w)(x) and p((q)r) are not. To determine if a string is balanced, each character is read one at a time. The character is classified as an opening or a closing parenthesis, or as another character. The third category’s values are disregarded. When a value from the first category is found, the close parenthesis corresponding to it is put on the stack. When a “(” is read, for example, the character “)” is placed into the stack. When a “{” appears, the character pushed is “}”.
Processing Function Calls
The stack is very significant in programmes that call for numerous functions in a row. Assume we have a programme with three functions: A, B, and C. Function A calls function B, which calls function C.
When we execute function A, which involves a call to function B, its processing will be delayed until function B has completed its execution and returned. The same is true for functions B and C. As a result, we may conclude that function A will be finished only after function B is done, and function B will be completed only after function C is completed. As a result, function A is the first to begin and the last to finish.
Conclusion
Stack is one of the most effective techniques to instil discipline in a system. Stack is a strong tool for storing and managing data in the desired manner, thanks to a basic data structure. It may be thought of as a route with an entry that allows for both insertion and removal operations. Because of the stack’s architecture, insertion and deletion operations are LIFO-based. Stack has many applications like expression handling, processing functional calls, backtracking procedures, etc.
