Last Updated on April 26, 2023 by Prepbytes
In this tutorial, we will be explaining the Application of stack in data structures. The Stack is a major topic that belongs to the realm of computer science. Additionally, you must be familiar with every aspect of the Stack when it comes to competitive exams like the GATE. You will learn comprehensive information about the Application of stack in Data Structure from this post. We think the material in the CSE topic notes will help you comprehend this subject matter more clearly.
What is Stack in Data structures?
A linear data structure called a stack is used to store an ordered, linear sequence of elements. It is a type of abstract data. A stack operates according to the Last In First Out (LIFO) principle, which states that the element that was added last will be deleted first. Because we can only access the elements on the top of the Stack, it is necessary to maintain a pointer to the top of the Stack, which is the last element to be placed, in order to implement the Stack.
Stack Operation:
1. PUSH: The insertion of a new element into a stack is implied by the PUSH operation. The top of the stack is always where a new element is added, so we must always check to see if it is empty by using the formula TOP=Max-1. In the case that this condition is false, the Stack is full and no other elements may be added. Even if we attempt to add the element, a Stack overflow message will be shown.
Algorithm:
Step-1: If TOP = Max-1
Print “Overflow”
Goto Step 4
Step-2: Set TOP= TOP + 1
Step-3: Set Stack[TOP]= ELEMENT
Step-4: END
2. POP: POP denotes removing a stack element. Make sure to verify that the Stack Top is NULL, i.e., TOP=NULL, before deleting an element. In the event that this condition is met, the Stack will be empty, making deletion operations impossible. Even if deletion attempts are made, the Stack Underflow warning will be produced.
Algorithm:
Step-1: If TOP= NULL
Print “Underflow”
Goto Step 4
Step-2: Set VAL= Stack[TOP]
Step-3: Set TOP= TOP-1
Step-4: END
3. PEEK: The Peek operation is employed when it is necessary to return the value of the topmost stack element without erasing it. This operation first determines whether the Stack is empty, i.e., TOP = NULL; if it is, then the value will be returned; otherwise, an appropriate notice will be displayed.
Algorithm:
Step-1: If TOP = NULL
PRINT “Stack is Empty”
Goto Step 3
Step-2: Return Stack[TOP]
Step-3: END
Representation of the Stack
A stack may have a set, predetermined size or it may be dynamic, meaning that the size of the stack may fluctuate over time. Pointer, Array, Structure, and Linked List can all be used to represent it.
Application of Stack in Data Structure are as following:
- Evaluation of Arithmetic Expressions
- Backtracking
- Delimiter Checking
- Reverse a Data
- Processing Function Calls
1. Evaluation of Arithmetic Expressions
In computer languages, a stack is an extremely efficient data structure for evaluating arithmetic statements. Operands and operators are the components of an arithmetic expression.
The arithmetic expression may additionally contain parenthesis such as "left parenthesis" and "right parenthesis," in addition to operands and operators.
Example: A + (B – C)
The normal precedence rules for arithmetic expressions must be understood in order to evaluate the expressions. The following are the five fundamental arithmetic operators’ precedence rules:
| Operators | Associativity | Precedence |
|---|---|---|
| ^ exponentiation | Right to left | Highest followed by *Multiplication and /division |
| *Multiplication, /division | Left to right | Highest followed by + addition and – subtraction |
| + addition, – subtraction | Left to right | lowest |
Evaluation of Arithmetic Expression requires two steps:
- Put the provided expression first in special notation.
- In this new notation, evaluate the expression.
Notations for Arithmetic Expression
There are three notations to represent an arithmetic expression:
- Infix Notation
- Prefix Notation
- Postfix Notation
Infix Notation
Each operator is positioned between the operands in an expression written using the infix notation. Depending on the requirements of the task, infix expressions may be parenthesized or not.
Example: A + B, (C – D) etc.
Because the operator appears between the operands, all of these expressions are written in infix notation.
Prefix Notation
The operator is listed before the operands in the prefix notation. Since the Polish mathematician invented this system, it is frequently referred to as polish notation.
Example: + A B, -CD etc.
Because the operator occurs before the operands in all of these expressions, prefix notation is used.
Postfix Notation
The operator is listed after the operands in postfix notation. Polish notation is simply reversed in this notation, which is also referred to as Reverse Polish notation.
Example: AB +, CD+, etc.
All these expressions are in postfix notation because the operator comes after the operands.
2. Backtracking
Another use for Stack is backtracking. The optimization problem is solved using a recursive technique.
3. Delimiter Checking
Delimiter checking, or parsing, which entails analysing a source program syntactically, is the most prevalent application of Stack in data structures. Additionally known as parenthesis checking. When a source program written in a programming language, such as C or C++, is translated into machine language, the compiler separates the program into several components, such as variable names, keywords, etc. by moving left to right while scanning The mismatched delimiters are the main issue when translating. We employ a variety of delimiters, such as the parenthesis checks (,), curly braces (,), square brackets (,), and the widely used / and / delimiters. Each opening delimiter must be followed by a corresponding closing delimiter, i.e., each opening parenthesis must be followed by a corresponding closing parenthesis. Also, the delimiter can be nested. The opening delimiter that occurs later in the source program should be closed before those occurring earlier.
4. Reverse a Data:
We must reorder the data in such a way that the first and final elements are switched, the second and second-last elements are switched, and so on for all subsequent elements if we want to reverse a given collection of data.
Example: If we were to reverse the string Welcome, we would get Emoclew.
There are different reversing applications:
- Reversing a string
- Converting Decimal to Binary
Reverse a String
A Stack can be used to reverse a string’s characters. This can be done by simply popping each character off of the stack one at a time after pushing them onto the stack one at a time. The initial character of the Stack is at the bottom of the Stack, the last character of the String is at the top, and due to the Stack’s last in first out property, after performing the pop operation in the Stack, the Stack returns the String in reverse order.
Converting Decimal to Binary
Although most business programs employ decimal numbers, some scientific and technical applications need either binary, octal, or hexadecimal numbers. A number can be transformed from decimal to binary, octal, or hexadecimal using a stack. Any decimal number can be converted to a binary number by continually dividing it by two and pushing the residue of each division onto the stack until the result is 0. The binary counterpart of the provided decimal number is then obtained by popping the entire stack.
Example: Converting 14 number Decimal to Binary:
In the example above, we get seven as a quotient and one as the reminder when we divide 14 by 2, and these two values are pushed onto the stack. When we divide seven by two once more, we get three as the quotient and one as the reminder, which is once more added to the Stack. The supplied number is lowered in this manner until it does not reach zero. The comparable binary number 1110 is what we receive after we totally pop off the stack.
5. Processing Function Calls:
In programs that call multiple functions in quick succession, the stack is crucial. Assume we have a program with three A, B, and C functions. Function A calls Function B, and Function B calls Function C.
Function A’s processing won’t be finished until function B’s execution and return have been completed. This is because function A contains a call to function B. The same is true of functions B and C. As a result, we see that function A can only be finished after function B, and function B can only be finished after function C. As a result, function A should be begun first and finished last. In conclusion, utilising Stack makes it simple to handle the function activity described above, which follows the last in first out behaviour.
Consider the addresses of the statements to which control is transferred following the completion of functions A, B, and C as addrA, addrB, and addrC, respectively.
In the Stack, return addresses are displayed in the order that the functions were called, as can be seen in the image above. Each function is finished, followed by the pop operation, which starts execution at the position where the Stack was removed. The stack data structure may thus handle the program that calls multiple functions one after another in the best possible way. Each function receives control in the proper location, which is the calling sequence’s reversal.
Conclusion
So, with this we came to an end of this Application of stack in data structure. In this blog we had completely given the detailed Application of stack in data structures Not just this we had also explained the Stack data structure with their operations and examples.