STACKS & QUEUES
STACK: Introduction to Stacks, Basic Stack operations, Representation of a Stack using Array, Linked list representation of stacks, operations on linked stack, stack applications: Reversing list, Factorial calculation, infix to post fix transformations, evaluating arithmetic expressions.
QUEUES: Introduction to Queues, Basic queue operations, Representation of a queue using Arrays and using Linked List, Implementation of queue operations using stack, applications of queues — circular queues, dequeues, priority queues, Multiple Queues.
A Stack is an ordered collection of data items, into which new items may be inserted and from which items may be deleted at one end called Top of the Stack.
Unlike an array stack provides the insertion and deletion of items. So a stack is a dynamic, constantly changing object.
New items may be put on top of the stack or items which are at the top of the stack may be removed.
The two changes which can be made to a stack are given special names, those are PUSH and POP. When an item is added to a stack it is pushed onto the stack and when an item is removed it is popped from the stack.
Although an array cannot be a stack it can be the home of the stack i.e., an array can be declared with a range that is large enough for the maximum size of the stack. During the course of program execution the stack will grow and shrink within the space reserved for it. One end of the array will be fixed bottom of the stack while the top of the stack will constantly shift as items are popped and pushed. Thus another field is needed to keep track of the current position of the top of the stack.
A Stack in “C” may be declared as a structure containing two members. An array to hold the elements of the stack and an integer to indicate the position of the current stack top within the array.
#define MAXSTACK 50 Type declaration
struct stack{
int entry[MAXSTACK];
int top;
};
typedef struct stack stacktype;
stacktype s; Variable Declaration
int x;Given a stack s and an item x, performing the operation push(s,x) adds the item x to the top of the stack S. Similarly the operation pop(s) removes the top element and returns it as a function value.
X = pop(s);
This assignment operation removes the element from the top of the stack S and assigns its value to x.
At each point, the top element is removed, since a deletion can be made at only from the top. The most important thing is that the last element inserted into the stack is the first element deleted. For this reason a stack is some times called as LIFO (Last In First Out) list.
A helpful analogy is to think of a stack of trays or of plates sitting on a counter in a busy cafeteria. Though out the lunch hour customers take trays off the top of the stack, and the employees place returned trays back on top of the stack. The tray most recently put on the stack is the first one taken off. The bottom tray is the first one put on, and the last one to be used.
Function to push an element into a stack.
void push (s,x)
stacktype *s;
int x;{
if ( s->top == MAXSTACK — 1)
printf ("Error — Stack Overflow \n");
else{
s->top = s->top+1;
s->entry[s->top] = x;
}
}Function to pop an element from a stack.
int pop(s)
stacktype *s;
{
int x;
if (s->top == -1)
printf("Error — Stack Underflow\n");
else{
x = s->entry[s->top];
s->top = s->top — 1;
return(x);
}
}Function to display the elements of stack.
void liststack(s)
stacktype s;{
int i;
for (i=0; i<=s.top; i++)
printf( "%d\n", s.entry[i]);
printf ("\n");
}Function to determine whether a stack is empty or not.
int empty(s)
stacktype s;{
if (s.top == -1)
return(1);
else
return(0);
}/*****************************************************
Program to implement a stack using Arrays
******************************************************/
#include<stdio.h>
#define MAX 50int top=-1,stack[MAX];void push(int ele){
top++;
stack[top]=ele;
}void pop(){
printf("Element deleted is %d\n",stack[top]);
top--;
}void display(){
int i;
printf("Elements in the stack are \n");
for(i=0;i<=top;i++)
printf("%d ",stack[i]);printf("\n");
}
void main(){int ch,ele;
printf("1.Push 2.Pop 3.Display \n");while(1){printf("Enter Choice\n");
scanf("%d",&ch);
switch(ch){
case 1:
printf("Enter element to be inserted\n");
scanf("%d",&ele);
push(ele);
break;
case 2:
pop();
break;
case 3:
display();
break;
default:
exit(0);
}}}
Output
1.Push 2.Pop 3.Display
Enter Choice
1
Enter element to be inserted
12
Enter Choice
1
Enter element to be inserted
13
Enter Choice
1
Enter element to be inserted
14
Enter Choice
1
Enter element to be inserted
15
Enter Choice
3
Elements in the stack are
12 13 14 15
Enter Choice
2
Element deleted is 15
Enter Choice
3
Elements in the stack are
12 13 14While calling functions push() and pop() we are using call by reference technique. Usually a function returns only one value through return statement.
While pushing an element top value will changes and one element will be added to stack.
If we use reference parameter as formal parameter, whatever the changes that occurred to the stack in the function they reflect in the calling function also. In push and pop functions stack parameter is taken as reference parameter, because we are modifying the contents of stack.
In display() function we are just displaying the contents of the stack. We are not modifying the content of stack. So we have taken the parameter as a value parameter.
POLISH NOTATION
A + B * C Infix A * B Infix
ABC *+ Postfix * AB Prefix
+A*BC Prefix AB * PostfixThe method of writing all operators either before their operands, or after them is called Polish Notation. When the operators are written before their operands. It is called prefix form. When the operators come after their operands, it is called the postfix form or some times reverse polish form or suffix form. Writing operators between operands is called the usual infix form.
Infix, Postfix and Prefix:
Consider the sum of A and B. We think of applying the operator “+” to the operands A and B and write the sum as A+B. This particular representation is called Infix. There are two alternate notations for expressing the sum of A and B, using the symbols A, B and +. These are
+AB Prefix
AB+ Postfix.The prefix, infix and postfix refer to the relative position of the operator with respect to the two operands. In prefix notation the operator precedes the two operands, in postfix notation the operator follows the two operands, and in infix notation the operator is in between the two operands.
Let us now consider some additional example. The evaluation of example A+B*C, as written in standard infix notation, requires knowledge of which of the two operations, + or * we know that multiplication is to be done before addition. We say that multiplication takes precedence over addition. Suppose we want to rewrite A+B*C in postfix. Applying the rules of precedence, we first convert the portion of the expression that is evaluated first, namely the multiplication. By doing this conversion in stages we obtain
A + (B * C)
A + (BC *)
ABC * + à Postfix form.The only rules to remember during the conversion process are that operations with highest precedence are converted first and that after a portion of the expression has been converted to postfix it is to be treated as a single operand. Consider the same example with parentheses as shown.
( A + B ) * C ->Infix
(A B + ) * C
(A B + ) C *
A B + C * ->PostfixIn this example the addition is converted before the multiplication because of the parentheses.
We consider five binary operations : addition, subtraction, multiplication, division and exponentiation. The order precedence highest to lowest.
Exponentiation
Multiplication / Division
Addition / Subtraction.
When unparenthesized operators of the same precedence are scanned, the order is assumed to be left to right except in the case of exponentiation where the oder is assumed to be from right to left. Thus
A + B + C means (A + B ) + C where as A$ B$ C means A$ ( B$C)
The precedence rules for converting an expression from infix to prefix are identical. The only change from postfix conversion is that the operator is placed before the operands rather than after them.
Evaluation of an expression in prefix form:
The first symbol is an operator, and the remainder of the expression comprises the operands of this operator ( one for unary operator, two for binary operator).
Algorithm evaluate (expression)
{
value x,y;
Let token be the first symbol in the expression and
remove token from the expression.
if ( token is a unary operator)
{
x = evaluate (expression);
return result of applying operator token to x;
}
else
if (token is a binary expression)
{
x = evaluate(expression)
y = evaluate(expression)
return result of applying operator token to x and y;
}
else
{
return token;
}
}/*************************************************************
Program to evaluate a POSTFIX expression
*************************************************************/
#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <stdlib.h>
#define MAXCOL 80
#define TRUE 1
#define FALSE 0struct stack
{
int top;
double item[MAXCOL];
};
push(s,x)
struct stack *s;
double x;
{
s->top=s->top+1;
s->item[s->top]=x;
}double pop(s)
struct stack *s;
{
double x;
x=s->item[s->top];
s->top=s->top-1;
return(x);
}int isdigit( char symb)
{
return(symb>=’0’ && symb<=’9’);
}double oper( char symb, double op1, double op2)
{
switch(symb)
{
case ‘+’ : return(op1 + op2);
case ‘-’ : return(op1 - op2);
case ‘*’ : return(op1 * op2);
case ‘/’ : return(op1 / op2);
case ‘$’ : return( pow(op1,op2));
default : printf(“%s”,”illegal operation”);
exit(1);
} /*---------------------------------------------end of switch*/
} /*-----------------------------------------end of oper function*/double eval (char expr[])
{
int c, position;
double opnd1, opnd 2, value;
struct stack opndstk;
opndstk.top = -1;
for (position = 0; (c = expr[position]) != ‘\0’;position++)
if (isdigit(c))
push(&opndstk,(double)(c-‘0’);
else
{
opnd2 = pop(&opndstk);
opnd1 = pop(&opndstk);
value = oper(c,opnd1,opnd2);
push(&opndstk,value);
}
return(pop(&opndstk));
}void main()
{
char expr[MAXCOL];
int position = 0;clrscr();
printf(“enter a postfix expression \n”);
while (( expr [position ++] = getchar()) != ‘\n’);
expr (-- position) = ‘\0’;printf(“The original string = %s \n”, expr);
printf( “\n %f \n”, eval(expr));
} /* end of main */
CONVERTING AN EXPRESSION FROM INFIX TO POSTFIX
In our previous discussion we mentioned that expressions within innermost parentheses must first be converted to postfix so that they can then be treated as single operands. In this fashion parentheses can be successively eliminated until the entire expression is converted.
Consider the two infix expressions
A+B*C and (A+B)*C
and their respective postfix versions ABC*+ and AB+C*. In each case the order of the operands is the same as the order of the operands in the original infix expressions.
In scanning the first operation, A+B*C, the first operand, A can be inserted immediately into the postfix expression. Clearly the first symbol cannot be inserted until after its second operand, which has not yet been scanned, is inserted. Therefore it must be stored away to be retrieved and inserted in its proper position. When the operand B is scanned it is inserted immediately after A. The next symbol * has precedence over +. In the case of the second expression the closing parenthesis indicates that the + operation should be performed first.
Remember that in postfix, unlike infix, the operator that appears earlier in the string is the one that is applied first.
Since precedence plays an important plays an important role in transforming infix to postfix, let us assume the existence of a function prcd(op1,op2) where op1 and op2 are characters representing operators. This function returns true if op1 has precedence over op2 when op1 appears to the left of op2 in an infix expression without parentheses.
Priority of operators or precedence of the operators are as follows
The function prcd() returns true i.e. 1 when the first operand has higher precedence over the second operand otherwise it returns false i.e. 0.
prcd( ‘*’, ‘+’ ) — trueprcd( ‘+’, ‘+’ ) — trueprcd( ‘+’, ‘*’ ) — falseprcd( ‘$’, ‘$’ ) — falseprcd( ‘(’, ‘op’ ) — falseprcd( op, ‘(’ ) — falseprcd( op, ‘)’ ) — trueprcd( ‘)’, op ) — undefined
Algorithm to convert an infix string without parentheses into a postfix string.
Algorithm infixtopostfix(infix,postfix)
{
opstk = empty stack;
While (not end of input)
{
symb = next input character.
if (symb is an operand)
Add symb to postfix string;
else
{
while (!empty(opstk) && prcd(stacktop(opstk),symb))
{
topsymb = pop(opstk);
add topsymb to the postfix srting;
}
push (opstk, symb);
}
}
while (!empty(opstk))
{
topsymb = pop (opstk);
add topsymb to the postfix string;
}
}
What modifications must be made to this algorithm to accommodate parenthesis?
The answer is little when an opening parenthesis is read, it must be pushed onto the stack. This ensures that an operator symbol appearing after a left parenthesis is pushed onto the stack. When a closing parenthesis is read, all operators up to the first opening parenthesis must be popped from the stack into the postfix string.
Program to convert an infix expression to postfix expression
For simplicity, we assume all the operands are single character letters or digits. The output is a character string. In transforming the conversion algorithm into a program, we make use of several routines. Among those are empty, pop, push and popandtest. We also make use of a function isoperand that returns true if ita argument ia an operand and false otherwise.
/**********************************************************
Program to convert an Infix expr to postfix expr
**********************************************************/
#include <stdio.h> #include <stdlib.h> #include <conio.h>
#define MAXCOL 80 #define TRUE 1 #define FALSE 0
struct stack { char entry[MAXCOL]; int top; }; typedef struct stack stacktype; push(s,x)
stacktype *s;
char x;
{
s->top++;
s->entry[s->top]=x;
}
char pop(s) stacktype *s; { char x; x=s->entry[s->top];
s->top--;
return(x);
}
int empty(stacktype s)
{ if (s.top==-1)
return(1);
else
return(0);
}char stacktop(stacktype s)
{
return(s.entry[s.top]);
}
/* this function returns 1 if the symbol is an operand*/ int isoperand(char symb) { if (symb=='+'||symb=='-'|| symb=='*'|| symb=='/'
||symb=='$'||symb=='('||symb==')')
return(0);
else
return(1);
}/*This function returns 1 if the first argument
Has precedence over the second argument */
int prcd(char opr1, char opr2) { int pr1,pr2;
switch(opr1) { case '$': pr1=3; break; case '*': pr1=2; break;
case '/': pr1=2; break;
case '+': pr1=1; break;
case '-': pr1=1; break;
}
switch(opr2)
{
case '$': pr2=3; break;
case '*': pr2=2; break;
case '/': pr2=2; break;
case '+': pr2=1; break;
case '-': pr2=1; break;
}
if(pr1>pr2)
return(1);
else
return(0);
}
/* function converts infix expr to postfix expr. */
in2postfix(char ifix[], char pfix[]) { int pos, opos=0; char symb,topsymb; stacktype s; s.top = -1; for( pos=0;(symb=ifix[pos])!='\0';pos++) { if(isoperand(symb)) pfix[opos++]=symb;
else
{
while(!empty(s) && prcd(stacktop(s),symb))
{
topsymb=pop(&s);
pfix[opos++]=topsymb;
}
push(&s,symb);
}
}
while(!empty(s))
{
topsymb=pop(&s);
pfix[opos++]=topsymb;
}
pfix[pos]='\0';
}void main()
{
char infix[MAXCOL],pfix[MAXCOL];
int pos=0;
clrscr();
printf("enter your infix string \n");
while((infix[pos++]=getchar())!='\n');
infix[--pos]='\0';
printf("the infix string = %s\n",infix);
in2postfix(infix,pfix);
printf("the postfix string = %s\n",pfix);
getch();
}
QUEUE
A Queue is a ordered collection of items from which items may be deleted at one end called the front of the Queue and into which items may be inserted at the other end called the rear of the queue.
The first element inserted into the queue is the first element to be removed. For this reason a queue is some times called a FIFO (First In First Out) list.
In ordinary English a queue is defined as a waiting line, like a line of people waiting to purchase tickets, where the first person in the queue is the first person served.
There are 3 primitive operations that can be applied to a queue.
INSERT, DELETE, EMPTY
The operation insert inserts an element at the rear of the queue.
The operation delete deletes the front element from the queue.
The operation empty returns 1 or 0 (true or false) depending on whether or not the queue contains any elements.
Queue can be implemented in C as follows:
#define MAXQ 50
struct queue
{
int entry[MAXQ];
int front, rear;
}
typedef struct queue qtype;Variable Definition:
qtype q;Function to insert an element into a queue.void insert (q,x)
qtype *q;
int x;
{
if (q->rear = = maxQ –1)
printf(“Error – Q overflow\n”);
else
{
q->rear = q->rear +1;
q->entry[q->rear] = x;
}
}Function to remove / delete an item from a queue.
int delete(q)
qtype *q;
{
int x;
x = q->entry[q->front];
q->front = q->front +1;
return (x);
}Function to find whether the queue is empty or not.
int empty(q)
qtype q;
{
if (q.front -> q.rear)
return (1);
else
return (0);
}Function to display the elements of a queue.
void listqueue (q)
qtype q;
{
int i;
for ( i = q.front; i <= q.rear; i++)
printf(“%d”, q.entry[i]);
printf(“\n”);
}
Program:
/***********************************************************
Program to implement a queue
***************************************************************/
# include <stdio.h>
#include <conio.h>
# define MAXQ 50
struct queue
{
int entry[MAXQ];
int front, rear;
};
typedef struct queue qtype;void insert (q,x)
qtype *q;
int x;
{
if (q->rear = = maxQ –1)
printf("Error – Q overflow\n");
else
{
q-> rear = q-> rear +1;
q ->entry[q->rear] = x;
}
}
int delete(q)
qtype *q;
{
int x;
x = q->entry[q-> front];
q-> front = q ->front +1;
return (x);
}
int empty(q)
qtype q;
{
if (q.front -> q.rear)
return (1);
else
return (0);
}
void listqueue (q)
qtype q;
{
int i;
for ( i = q.front; i <= q.rear; i++)
printf(“%d”, q.entry[i]);
printf(“\n”);
}void main()
{
qtype q;
int x,opt;initialise(&q); /*----------- this function initialises the queue */
do
{
printf("Operations of Queue \n");
printf("1. Insert 2. Delete 3. List 4. Exit \n");
printf("Enter your option \n");
scanf("%d", &opt);switch (opt)
{
case 1 : printf("Enter x \n");
scanf("%d",&x);
insert(&q,x);
break;case 2 : if (empty(q) = = 1)
printf(“ Q is empty \n”);
else
{
x = delete (&q);
printf( “The deleted item = %d \n”, x);
}
break;
case 3 : printf( “The elements of Queue \n”);
listqueue(q);
break;
} /*-------------------------------- End of Switch */
} while (opt <= 3); /*----------- End of do loop */
} /*-------------------------------- End of main */
Wherever we need to modify the queue we passed reference parameter. For example
initialise (&q)
insert (&q,x)
delete (&q)
In all the above cases the queue changes its values. So we pass q as a reference parameter.
The following functions will not change the contents of q.
empty (q)
listqueue(q)
because we are not modifying any values here we pass queue as a value parameter.
Let us observe the following linear queue containing a maximum space for 5 elements. The front is at 3 and rear is at 4.
The programs of stacks using Linked lists, Queues usig Linked Lists, Circular Linked Lists check the below post.
