A stack is ordered collection of homogeneous data elements where the insertion and deletion operations only occurs at one end. The end is often known as Top Of the Stack (TOS).
As stack is not provided by any programming language we need to create our own stak. Use of control + Z (undo) is done through the use of Stack, Reversing of the string and checking the validation and matching the parentheses in programming language in compiler are done using programming language.
How Stack Works?
Stack is a one ended operation system. There are only two operations permitted in stack, Push and pop. Push to insert in the stack where as pop to delete the element form the stack. The TOS (Top Of the Stack) always point to the top position where the next can be popped off. We can add another element on the (TOS + 1).When ever we try to push to the stack when the stack is full then we get the error which is known as Stack Overflow. Whenever we try to pop out from the empty stack then we get an error which is known as stack underflow.
When the stack is empty TOS = -1 When we insert the first element the TOS will be on 0. When we add another element again the TOS will be 1 and so on. So when new element is inserted the TOS will be incremented. When we pop the element the TOS will reduced by one. Let say TOS is on 5 now. when we pop a element, New TOS will be 4 then when we pop again the TOS will be 3 and so on. As we will get an error when we try push to the stack which is full and try to pop from the empty stack so we should always check whether we can pop and push or not.
Stack Implementation
we can implement stack using these two ways:Static implementation: Using array
Dynamic Implementation: Using linked list
Static Implementation
Here we use array to realize the principle of stack. In array we can insert the data and access the data. Here we use the array in a such a way that we will insert the element in the TOS and access the element from TOS. So by default when the stack is empty TOS is -1. (As array begins with 0, we make TOS to -1 for easiness). Then we insert the element in the TOS+1 location of the array. So we pass element to be added, array and the TOS when ever we want to insert data in the Stack. And in the same way we will remove a data from the stack and reduce the TOS by one, thus we pass array and TOS during pop.Algorithm:
#define MAX=5
push(s[MAX],element,TOS)
if TOS == MAX - 1
display "Stack is full"
else
TOS = TOS+1
s[TOS] = element
return;
pop(s[MAX],TOS)
if TOS == -1
display "Stack is Empty"
return 0
else
element = s[TOS]
TOS = TOS -1
return element
Application of Stack
It is used in recursive function calling. Function calling and returing process are in reverse order.It is used to reverse a string.
It is used to evalutate and check the correction ness of the mathematical operation.
Implementation by word processors to perform UNDO REDO operations.
Used in parenthesis matching by compilers.
Details of the examples
How Parenthesis matching by compiler using Stack?
In every programming language there must be even numbers of parenthesis in the program. Here we will discuss how stack helps on parenthesis matching. So when we open a parenthesis the program will save that on the stack and search for next parenthesis. If it find another opening parenthesis it will add that on the stack again. And again keep looking for the parenthesis. When a closing parenthesis is found it will remove the pair (Opening and Closing) together and keep looking for parenthesis. If at the end The stack is empty there is not error in parenthesis else of the stack is not empty, there must error in parenthesis.
Stack for UNDO and REDO
Every actions will be stored in stack. so when we undo it the last command will be removed. if undo again the second last command and third last and going on..... In the same way the poped commands will be stored in another stack in case of REDO. so when we press redo we will get the last undo and the undo then after and then after.
0 comments:
Post a Comment