STACK
A Stack is linear data structure. A stack is a list of elements in which an element may be inserted or deleted only at one end, called the top of the stack. Stack principle is LIFO (last in, first out).
As the items can be added or removed only from the top i.e. the last item to be added to a stack is the first item to be removed.
Operations on stack:
The two basic operations associated with stacks are: 1. Push 2. Pop
While performing push and pop operations the following test must be conducted on the stack. a) Stack is empty or not b) stack is full or not
1. Push: Push operation is used to add new elements in to the stack. At the time of addition first check the stack is full or not. If the stack is full it generates an error message "stack overflow".
2. Pop: Pop operation is used to delete elements from the stack. At the time of deletion first check the stack is empty or not. If the stack is empty it generates an error message "stack underflow".
3.Peek Operation:Peek is an operation that returns the value of the topmost element of the stack without deleting it from the stack.
Representation of Stack (or) Implementation of stack:
The stack should be represented in two ways:
1. Stack using array
2. Stack using linked list
1. push(): When an element is added to a stack, the operation is performed by push(). Below Figure shows the creation of a stack and addition of elements using push().
Initially top=-1, we can insert an element into the stack, increment the top value i.e top=top+1. We can insert an element in to the stack first check the condition is stack is full or not. i.e top>=size-1. Otherwise add the element in to the stack.
Algorithm: Procedure for push():
We can insert an element from the stack, and decrement the top value i.e top=top-1.
We can delete an element from the stack first check the condition is stack is empty or not. i.e top== -1. Otherwise remove the element from the stack.
3.Peek Operation:
Peek is an operation that returns the value of the topmost element of the stack without deleting it from the stack.
However, the Peek operation first checks if the stack is empty, i.e., if TOP = NULL, then an appropriate message is printed, else the value is returned
Here, the Peek operation will return 5, as it is the value of the topmost element of the stack
4. display(): This operation performed display the elements in the stack. We display the element in the stack check the condition is stack is empty or not i.e top==-1.Otherwise display the list of elements in the stack.
example code:
https://www.programiz.com/c-programming/online-compiler/
// Online C compiler to run C program perform stack operation
#include<stdio.h>
#include<stdlib.h>
#define size 5
int stack[size];
int top = -1;
int main()
{
printf("Stack Implementation:\n");
while(1)
{
int option;
printf("Choose option : 1) push 2) pop 3) peek 4)display 5)exit\nEnter option :");
scanf("%d",&option);
if(option == 1)
printf("push operation:\n");
else if(option == 2)
printf("pop operation:\n");
else if(option == 3)
printf("peek operation:\n");
else if(option == 4)
printf("display operation:\n");
else
break;
}
return 0;
}
// Online C compiler to run C program perform stack operation with sample data
#include<stdlib.h>
#define size 5
int stack[size];
int top = -1;
void push()
{
if(top == size-1)
printf("Stack is Full!");
else
{
int value;
printf("Enter value :");
scanf("%d",&value);
top++;
stack[top] = value;
printf("Value is pushed successfully!\n");
}
}
void pop()
{
if(top == -1)
printf("Stack is Empty!");
else
{
top--;
printf("Value is removed Successfully!\n");
}
}
void peek()
{
if(top == -1)
printf("stack is empty!\n");
else
{
printf("Peek Value : %d\n",stack[top]);
}
}
void display()
{
if(top == -1)
printf("Stack is Empty!\n");
else
{
int i;
for(i=0;i<=top;i++)
printf("%d\n",stack[i]);
}
}
int main()
{
printf("Stack Implementation:\n");
while(1)
{
int option;
printf("Choose option : 1) push 2) pop 3) peek 4)display 5)exit\nEnter option :");
scanf("%d",&option);
if(option == 1)
push();
else if(option == 2)
pop();
else if(option == 3)
peek();
else if(option == 4)
display();
else
break;
}
return 0;
}
Applications of STACK: Application of Stack :
• Recursive Function. • Expression Evaluation.
• Expression Conversion.
➢ Infix to postfix ➢ Infix to prefix ➢ Postfix to infix
➢ Postfix to prefix ➢ Prefix to infix ➢ Prefix to postfix
• Reverse a Data • Processing Function Calls
Expressions:
• An expression is a collection of operators and operands that represents a specific value.
• Operator is a symbol which performs a particular task like arithmetic operation or logical operation or conditional operation etc.,
• Operands are the values on which the operators can perform the task. Here operand can be a direct value or variable or address of memory location
Expression types:
Based on the operator position, expressions are divided into THREE types. They are as follows.
• Infix Expression
• In infix expression, operator is used in between operands.
• Syntax : operand1 operator operand2
• Example
• Postfix Expression
• In postfix expression, operator is used after operands. We can say that "Operator
follows the Operands".
• Syntax : operand1 operand2 operator
• Example:
• Prefix Expression
• In prefix expression, operator is used before operands. We can say that "Operands follows the Operator".
• Syntax : operator operand1 operand2
• Example:
Algorithm for Conversion of Infix to Postfix using Stack in C
Here are the steps of the algorithm to convert Infix to postfix using stack in C:
- Scan all the symbols one by one from left to right in the given Infix Expression.
- If the reading symbol is an operand, then immediately append it to the Postfix Expression.
- If the reading symbol is left parenthesis ‘( ‘, then Push it onto the Stack.
- If the reading symbol is right parenthesis ‘)’, then Pop all the contents of the stack until the respective left parenthesis is popped and append each popped symbol to Postfix Expression.
- If the reading symbol is an operator (+, –, *, /), then Push it onto the Stack. However, first, pop the operators which are already on the stack that have higher or equal precedence than the current operator and append them to the postfix. If an open parenthesis is there on top of the stack then push the operator into the stack.
- If the input is over, pop all the remaining symbols from the stack and append them to the postfix.
Example-1:
( A+B)*(C-D)
Example-3:
Evaluation of postfix expression:
The postfix expression is evaluated easily by the use of a stack.
• When a number is seen, it is pushed onto the stack;
• when an operator is seen, the operator is applied to the two numbers that are popped from
the stack and the result is pushed onto the stack.
• When an expression is given in postfix notation, there is no need to know any precedence rules.
Example 1: Evaluate the postfix expression: 6 5 2 3 + 8 * + 3 + *
Reverse a Data:
To reverse a given set of data, we need to reorder the data so that the first and last elements are exchanged, the second and second last element are exchanged, and so on for all other elements.
Example: Suppose we have a string Welcome, then on reversing it would be Emoclew. There are different reversing applications:
Reversing a string
A Stack can be used to reverse the characters of a string. This can be achieved by simply pushing one by one each character onto the Stack, which later can be popped from the Stack one by one.
Because of the last in first out property of the Stack, the first character of the Stack is on the bottom of the Stack and the last character of the String is on the Top of the Stack and after performing the pop operation in the Stack, the Stack returns the String in Reverse order.
A
No comments:
Post a Comment