UNIT-2
STACKS:
A stack is an Abstract Data Type (ADT). It is an ordered group of homogeneous items of elements. Elements are
added to and removed from the top of the stack (the most recently added items are at the top of the stack). The last
element to be added is the first to be removed (LIFO: Last In, First Out). A stack is a list of elements in which an
element may be inserted or deleted only at one end, called TOP of the stack. The elements are removed in reverse
order of that in which they were inserted into the stack.
Difference between Stack and Array
Basis of Stacks Array
Comparison
Definition Stack is a linear data structure An array is a collection of related data values
represented by a sequential collection called elements each identified by an indexed
of elements in a fixed order. array.
Principle Stacks are based on the LIFO In the array the elements belong to indexes, i.e.,
principle, i.e., the element inserted at if you want to get into the fourth element you
the last, is the first element to come have to write the variable name with its index or
out of the list. location within the square bracket eg arr[4].
Operations Insertion and deletion in stacks take Insertion and deletion in the array can be done at
place only from one end of the list any index in the array.
called the top.
Storage The stack has a dynamic size. The array has a fixed size.
Data Types The stack can contain elements of The array contains elements of the same data
different data types. type.
Methods We can do only a linear search. We can do both linear and Binary search.
Data Access Random access to elements is not Random access to elements is allowed in arrays.
allowed in stacks.
Implementation We can implement a stack using the We cannot implement an array using stack.
array.
Methods There are limited number of It is rich in methods or operations that can be
operations can be performed on a perform on it like sorting, traversing, reverse,
stack: push, pop, etc. push, pop, etc.
Pointers It has only one pointer- the top. This In arrays, memory can be allocated in compile-
pointer indicates the address of the time and is also known as static memory
topmost element or the last inserted allocation.
one of the stack.
Array representation of stacks:
➢ Stacks may be represented as a one way list or a linear array
➢ Each stack will be maintained by linear array stack, a pointer variable top, which contains the location of
the top element of stack and a variable STACKSIZE. Which gives the maximum number of elements that
can be held by the stack.
➢ The condition top is equal to zero, or top is equal to null. Will indicate that the stack is empty.
➢ The operation of adding (pushing) an item on a stack and removing (poping) an item may be implemented as.
• First test weather there is a space in stack for the new element if not then this condition is known as
“overflow”.
• First test weather there is an element in the stack to be deleted if not then we have the condition known as
the “underflow”.
Basic operations:
These are two basic operations associated with stack:
• Push() is the term used to insert/add an element into a stack.
• Pop() is the term used to delete/remove an element from a stack. Other names for stacks are piles and push-
down lists.
There are two ways to represent Stack in memory. One is using array and other is using linked list.
/*Program demonstrate the operations performed on stack*/
#include<stdio.h>
#include<conio.h>
Program:
#include<stdlib.h>
#define MAXSIZE 10
void push();
int pop();
void display ();
int top=-1;
int stack[MAXSIZE];
void main()
{
int choice;
clrscr();
do
{
printf("\[Link]");
printf("\[Link]");
printf("\[Link]");
printf("\[Link]");
printf("\n Enter your choice");
scanf("\n%d",&choice);
switch(choice)
{
case 1:push();
break;
case 2:printf("\n Deleted item is %d",pop());
break;
case 3:display();
break;
case 4:printf("\n Exit");
exit(0);
break;
}
}while(choice!=4);
}
void push()
{
int item;
if(top==MAXSIZE-1)
{
printf("\nSTACK IS FULL");
return(0);
}
else
{
printf("\nenter element");
scanf("%d",&item);
top=top+1;
stack[top]=item;
}
}
int pop()
{
int item;
if(top==-1)
{
printf("\nSTACK EMPTY");
return;
}
else
{
item=stack[top];
top=top-1;
return(item);
}
}
void display()
{
int i;
if(top==-1)
{
printf("\nstack is empty");
}
else
{
printf("\nthe elements are:");
for(i=top;i>=0;i--)
{
printf("\t %d",stack[i]);
}
}
}
Linked list implementation of stack
In linked list implementation of stack, the nodes are maintained non-contiguously in the memory. Each node
contains a pointer to its immediate successor node in the stack. Stack is said to be overflow if the space left in the
memory heap is not enough to create a node.
The top most node in the stack always contains the address of the next node and the last node contains the null
value in address part. Lets discuss the way in which, each operation is performed in linked list implementation of
stack.
Adding a node to the stack (Push operation)
Adding a node to the stack is referred to as push operation. Pushing an element to a stack in linked list
implementation is different from that of an array implementation. In order to push an element onto the stack, the
following steps are involved.
1. Create a node first and allocate memory to it.
2. If the list is empty then the item is to be pushed as the start node of the list.
3. If there are some nodes in the list already, then we have to add the new element in the beginning of the list
(to not violate the property of the stack).
Deleting a node from the stack (POP operation)
Deleting a node from the top of stack is referred to as pop operation. Deleting a node from the linked list
implementation of stack is different from that in the array implementation. In order to pop an element from
the stack, we need to follow the following steps :
Check for the underflow condition: The underflow condition occurs when we try to pop from an
already empty stack. The stack will be empty if the head pointer of the list points to null.
Adjust the head pointer accordingly: In stack, the elements are popped only from one end,
therefore, the value stored in the head pointer must be deleted and the node must be freed. The next
node of the head node now becomes the head node.
Display the nodes (Traversing)
Displaying all the nodes of a stack needs traversing all the nodes of the linked list organized in the form of
stack. For this purpose, we need to follow the following steps.
Copy the head pointer into a temporary pointer.
Move the temporary pointer through all the nodes of the list and print the value field attached to every node.
The stack operations using linked list :
#include <stdio.h>
#include <stdlib.h>
void push();
void pop();
void display();
struct node
{
int val;
struct node *next;
};
struct node *head;
void main ()
{
int choice=0;
printf("\n*********Stack operations using linked list*********\n");
printf("\n----------------------------------------------\n");
while(choice != 4)
{
printf("\n\nChose one from the below options...\n");
printf("\[Link]\[Link]\[Link]\[Link]");
printf("\n Enter your choice \n");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("Exiting....");
break;
}
default:
{
printf("Please Enter valid choice ");
}
};
}
}
void push ()
{
int val;
struct node *ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("not able to push the element");
}
else
{
printf("Enter the value");
scanf("%d",&val);
if(head==NULL)
{
ptr->val = val;
ptr -> next = NULL;
head=ptr;
}
else
{
ptr->val = val;
ptr->next = head;
head=ptr;
}
printf("Item pushed");
}
}
void pop()
{
int item;
struct node *ptr;
if (head == NULL)
{
printf("Underflow");
}
else
{
item = head->val;
ptr = head;
head = head->next;
free(ptr);
printf("Item popped");
}
}
void display()
{
int i;
struct node *ptr;
ptr=head;
if(ptr == NULL)
{
printf("Stack is empty\n");
}
else
{
printf("Printing Stack elements \n");
while(ptr!=NULL)
{
printf("%d\n",ptr->val);
ptr = ptr->next;
}
}
}
Application Of Stack: Polish Notation & Reverse Polish Notation:
An arithmetic expression consists of operands and operators . The operands can be numeric values or numeric
variable s. The operators used in an arithmetic expression represent the operations like addition, subtraction,
multiplication, division and exponentiation.
The arithmetic expression expressed in its normal form is said to be Infix notation, as shown:
A+B
Polish notation, named after the Polish mathematician. Jan Lukasiewicz, refers to the notation in which the
operators symbol is placed before its two operates. Example; +AB
Polish notation is also known as a prefix notation
Reverse Polish notation refers to the analogous notation in which the operator symbol is placed after the two
operands, It is also known as a postfix or suffix notation. Example: AB+
Evaluation of Postfix Expression Algorithm:
If P is an arithmetic expression written in postfix notation. This algorithm uses STACK to hold operands, and
evaluate P.
Algorithm: This algorithm finds the VALUE of P written in postfix notation.
1. Add a right parenthesis “)” at the end of P.
2. Scan P from left to right and repeat Steps 3 and 4 for each element of P until the sentinel “)” is encountered.
3. If an operand is encountered, put it on STACK.
4. If an operator Ꚛ is encountered, then:
a) Remove the two top elements of STACK, where A is the top element and B is the next-to—top-element.
b) Evaluate B Ꚛ A.
c) Place the result of (b) back on STACK.
[End of If structure.]
[End of Step 2 loop.]
5. Set VALUE equal to the top element on STACK.
6. Exit
Example: P: 5,6,2,+,*,12,4,/,- evaluate it
Solution: Add “)” at the end of P,
S. No, Scanned Symbol stack
1 5 5
2 6 5,6
3 2 5,6,2
4 + 5,8
5 * 40
6 12 40,12
7 4 40,12,4
8 / 40,3
9 - 37
10 )
EX. 1. Evaluate P: 6 5 2 3 + 8 * + 3 + * = 288
2 P: 5 2 + 3 * 9 3 / – =19
3 P: 12 7 3 - / 2 1 5 + * + =15
Transforming Infix Expression into Postfix Expression:
The following algorithm transform the infix expression Q into its equivalent postfix expression P. It uses a stack
to temporary hold the operators and left parenthesis. The postfix expression will be constructed from left to right
using operands from Q and operators popped from STACK:
Algorithm: Infix_to_PostFix(Q, P)
Suppose Q is an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix
expression P.
1. Push “(“ onto STACK, and add “)” to the end of Q.
2. Scan Q from left to right and repeat Steps 3 to 6 for each element of Q until the STACK is empty.
3. If an operand is encountered, add it to P.
4. If a left parenthesis is encountered, push it onto STACK.
5. If an operator Ꚛ is encountered, then:
a) Repeatedly pop from STACK and add to P each operator (on the top of STACK) which has the same or higher
precedence/priority than Ꚛ.
b) Add Ꚛ to STACK.
[End of If structure.]
6. If a right parenthesis is encountered, then:
a) Repeatedly pop from STACK and add to P each operator (on the top of STACK) until a left parenthesis is
encountered.
b) Remove the left parenthesis. [Do not add the left parenthesis to P.]
[End of If structure.]
[End of Step 2 loop.]
7. Exit.
Example: Convert Q: A+( B * C – ( D / E ^ F ) * G ) * H into postfix expression.
Solution: add “)” at the end of expression A+( B * C – ( D / E ^ F ) * G ) * H ) and also Push a “(“ on Stack.
Symbol Scanned Stack Expression(P)
(
A ( A
+ (+ A
( (+( A
B (+( AB
* (+(* AB
C (+(* ABC
- (+(- ABC*
( (+(-( ABC*
D (+(-( ABC*D
/ (+(-(/ ABC*D
E (+(-(/ ABC*DE
^ (+(-(/^ ABC*DE
F (+(-(/^ ABC*DEF
) (+(- ABC*DEF^/
* (+(-* ABC*DEF^/
G (+(-* ABC*DEF^/G
) (+ ABC*DEF^/G*-
* (+* ABC*DEF^/G*-
H (+* ABC*DEF^/G*-H
) empty ABC*DEF^/G*-H*+
Example: A. Convert following infix expression into postfix expression A + (B * C + D)/E.
(ANS:- ABC*D+E/+)
B. Consider the following infix expression and convert into reverse polish notation using stack. A + (B * C – (D/E
^ F) * H) (ANS:- ABC*DEF ^/ H)
Example:-Consider the following arithmetic expression written in infix notation :
a) E = (A + B) * C + D / (B + A * C) + D
b) E = A/B C + D * E – A * C
Convert the above expression into postfix and prefix notation.
Answer a). E = (A + B) * C + D / (B + A * C) + D
Postfix : E = (A + B) * C + D / (B + T1 ) + D T1 = AC *
= (A + B) * C + D / T2 + D T2 = BT1 +
= T3 * C + D / T2 + D T3 = AB +
= T3 * C + T4 + D T4 = DT2 /
= T5 + T4 + D T5 = T3 C *
= T6 + D T6 = T5 T4 +
= T7 T7 = T6D +
Putting the values of T’s
= T6D +
= T5 T4 + D +
= T3 C * DT2 / + D +
= AB + C * DBT1 + / + D +
= AB + C * DBAC * + / + D +
Prefix : E = (A + B) * C + D / (B + A * C) + D
= (A + B) * C + D / (B + T1 ) + D T1 = * AC
= (A + B) * C + D / T2 + D T2 = + BT1
= T3 * C + D / T2 + D T3 = + AB
= T3 * C + T4 + D T4 = / DT2
= T5 + T4 + D T5 = * T3C
= T6 + D T6 = + T5 T4
= T7 T7 = + T6D
Putting the values of T’s
= + T6D
= + + T5 T4D
= + + * T3C / DT2D
= + + * + ABC / D + B T1D
= + + * + ABC / D + B * ACD
b). E = A /B C + D * E – A * C
Postfix : E = A / T1 + D * E – A * C T1 = BC ^
= T2 + D * E – A * C T2 = AT1 /
= T2 + T3 – A * C T3 = DE *
= T2 + T3 – T4 T4 = AC *
= T5 – T4 T5 = T2 T3 +
= T6 T6 = T5 T4 –
Putting the values of T’s
= T5 T4 –
= T2 T3 + AC *
= AT1 /DE * + AC *
= ABC /DE * + AC *
Prefix : E = A /B C + D * E – A * C
= A / T1 + D * E – A * C T1 = BC
= T2 + D * E – A * C T2 = /AT1
= T2 + T3 – A * C T3 = * DE
= T2 + T3 – T4 T4 = * AC
= T5 – T4 T5 = + T2 T3
= T6 T6 = – T5 T4
putting the values of T’s
= – T5 T4
= – + T2 T3 * AC
= – + / AT1 * DE * AC
= – + / A ^ BC * DE * AC
Example:. Solve the following :
a. ((A – (B + C) * D) / (E + F)) [Infix to postfix]
b. (A + B) + *C – (D – E) F [Infix to prefix]
c. 7 5 2 + * 4 1 5 – / – [Evaluate the given postfix expression]
Answer a. ((A – (B + C)*D)/(E + F))
=((A – (B + C)*D)/ (EF + ))
=((A – (B + C)*D)/X)
= ((A – (BC +) * D) / X)
= ((A – (Y * D)) / X )
= ((A – (YD *)) / X)
=((A – Z) / X)
= ((AZ –) / X)
=(T / X)
=T X /
Now put the values,
= AZ – EF + /
=AYD * – EF + /
=ABC + D * – EF + /
This is the required postfix form.
b. (A + B) + *C – (D – E) F
= (+ AB) + * C – (D – E) F
=X + * C – (D – E) F
=X + * C – (– DE) F
=X + * C – (Y F)
=X + * C – (Y F)
= X + *(C – Z)
=X + * (– CZ)
=X + * T
=* + XT
Now put the values,
= * + + AB – CZ
=* + + AB – C YF
= * + + AB – C – DEF
This is the required prefix form
Conversion From Infix to Prefix
Algorithm to convert infix to prefix expression
1. Reverse the input string.
2. apply conversion from infix to postfix.
3. Reverse the resultant string, and getting the prefix expression.
.
Example:
Convert (A+B^C)*D+E^5 into prefix.
Step I: Reverse the infix expression 5^E+D*(C^B+A)
Now reverse the expression
+*+A^BCD^E5 which is in prefix form.