Disclaimer
The solution of question or notes are written by either student or taken from some publications , so it is the responsibility of viewer to check whether answers are correct or incorrect.
STACKS:-
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). Which element inserted last on to the stack that element
deleted first from the stack.
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
Real life examples of stacks are:-
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".
All insertions and deletions take place at the same end, so the last element
added to the stack will be the first element removed from the stack. When a stack is
created, the stack base remains fixed while the stack top changes as elements are
added and removed. The most accessible element is the top and the least
accessible element is the bottom of 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. Stack using array:-
Let us consider a stack with 6 elements capacity. This is called as the size of the
stack. The number of elements to be added should not exceed the maximum size of
the stack. If we attempt to add new element beyond the maximum size, we will
encounter a stack overflow condition. Similarly, you cannot remove elements
beyond the base of the stack. If such is the case, we will reach a stack underflow
condition.
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 in to 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.
void push()
{
int x;
if(top >= n-1)
{
printf("\n\nStack Overflow..");
return;
}
else
{
printf("\n\nEnter data:");
scanf("%d", &x);
stack[top] = x;
top = top + 1;
printf("\n\nData Pushed into the stack");
}
}
Algorithm: Procedure for push():
Step 1: START
Step 2: if top>=size-1 then Write โ Stack is Overflowโ
Step 3: Otherwise
3.1: read data value โxโ
3.2: top=top+1;
3.3: stack[top]=x;
Step 4: END
2.Pop():- When an element is taken off from the stack, the operation is performed by
pop(). Below figure shows a stack initially with three elements and shows the
deletion of elements using pop().
We can insert an element from the stack, 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
Void pop()
{
If(top==-1)
{
Printf(โStack is Underflowโ);
}
else
{
printf(โDelete data %dโ,stack[top]); top=top-1;
}
}
Algorithm: procedure pop():-
Step 1: START
Step 2: if top==-1 then Write โStack is Underflowโ
Step 3: otherwise 3.1: print โdeleted elementโ 3.2: top=top-1;
Step 4: END
3.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
void display()
{
If(top==-1)
{
Printf(โStack is Underflowโ);
}
else
{
printf(โDisplay elementsare:);
for(i=top;i>=0;i--)
printf(โ%dโ,stack[i]);
}
}
Algorithm: procedure pop():
Step 1: START
Step 2: if top==-1 then
Write โStack is Underflowโ
Step 3: otherwise
3.1: print โDisplay elements areโ
3.2: for top to 0 Print โstack[i]โ
Step 4: END
Source code for stack operations, using array:-
#include<stdio.h>
#inlcude<conio.h>
int
stack[100],choice,n,top,x,i;
void push(void);
void pop(void);
void
display(void); int
main()
{
//clrscr();
top=-1;
printf("\n Enter the size of STACK[MAX=100]:");
scanf("%d",&n);
printf("\n\t STACK OPERATIONS USING ARRAY");
printf("\n\t ");
printf("\n\t 1.PUSH\n\t 2.POP\n\t 3.DISPLAY\n\t 4.EXIT");
do
{
printf("\n Enter the Choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push()
;
break;
}
case 2:
{
pop();
break
12
;
}
case 3:
{
display()
; break;
}
case 4:
{
printf("\n\t EXIT POINT");
break;
}
default:
{
printf ("\n\t Please Enter a Valid Choice(1/2/3/4)");
}
}
}
while(choice!=4);
return 0;
}
void push()
{
if(top>=n-1)
{
printf("\n\tSTACK is over flow");
}
else
{
printf(" Enter a value to be pushed:");
scanf("%d",&x);
top++;
stack[top]=x;
}
}
void pop()
{
if(top<=-1)
{
printf("\n\t Stack is under flow");
}
else
{
printf("\n\t The popped elements is %d",stack[top]);
top--;
}
}
void display()
13
{
if(top>=0)
{
printf("\n The elements in STACK\n");
for(i=top; i>=0; i--)
printf("\n%d",stack[i]);
printf("\n Press Next
Choice");
}
else
{
printf("\n The STACK is empty");
}
}
2. Stack using Linked List:-
We can represent a stack as a linked list. In a stack push and pop operations are
performed at one end called top. We can perform similar operations at one end of list
using top pointer. The linked stack looks as shown in figure.
Applications of stack:
1. Stack is used by compilers to check for balancing of parentheses, brackets and braces.
2. Stack is used to evaluate a postfix expression.
3. Stack is used to convert an infix expression into postfix/prefix form.
4. In recursion, all intermediate arguments and return values are stored on theprocessorโs stack.
5. During a function call the return address and arguments are pushed onto a stack
and on return they are popped off.
Converting and evaluating Algebraic expressions:
An algebraic expression is a legal combination of operators and operands.
Operand is the quantity on which a mathematical operation is performed. Operand
may be a variable like x, y, z or a constant like 5, 4, 6 etc. Operator is a symbol
which signifies a mathematical or logical operation between the operands. Examples
Kommentare