Data Structures using „C‟ - Overview of Stack

Data Structures using „C‟ Unit 3

Unit 3 Overview of Stack
Structure:
3.0 Introduction
3.1 Operations of Stack
Self Assessment Questions
3.2 Insert / Push operation
3.3 Delete/pop operation
3.4 Display
Self Assessment Questions
3.5 Stack implementation using arrays
3.6 Applications of stack.
Self Assessment Questions
3.7 Stacks using structures.
3.8 Sample C programs to represents the Stack Implementation
3.9 Summary
3.10 Terminal Questions
3.0 Introduction
Definitions and operations:
We know that in a cafeteria the plates are placed one above the other and every new plate is added at the top. When a plate is required, it is taken off from the top and it is used. We call this process as stacking of plates. Thus, the operations that can be performed if plates are stacked are:
 Addition/insertion of plate at one end
 Deletion of plate at the same end
Using this analogy a stack is defined as a special type of data structure where items are inserted from one end called top of stack and items are deleted from the same end. Here, the last item inserted will be on top of
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 65
stack. Since deletion is done from the same end, Last item Inserted is the
First item to be deleted Out from the stack and so, stack is also called Last
In First Out (LIFO) data structure.
Objectives
At the end of this unit, you will be able to understand the:
 Stack Definition and its operations
 POP and PUSH operation implementation in C
 Various stack applications
 Stack implementation using Arrays and Structure
3.1 Operations of Stack
The various operations that can be performed on stacks are:
 Insert an item into the stack
 Delete an item from the stack
 Display the contents of the stack
From the definition of stack it is clear that it is a collection of similar type of
items and naturally we can use an array (An array is a collection of similar
data types) to hold the items of stack. Since array is used, its size is fixed.
So, let us assume that 5 items 30, 20, 25, 10 and 40 are to be placed on the
stack. The items can be inserted one by one as shown in following figure.
It is clear from this figure that initially stack is empty and top points to
bottom of stack. As the items are inserted top pointer is incremented and it
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 66
points to the topmost item. Here, the items 30, 20, 25, 10 and 40 are
inserted one after the other. After inserting 40 the stack is full. In this
situation it is not possible to insert any new item. This situation is called
stack overflow. When an item is to be deleted, it should be deleted from the
top as shown in following figure.
Since items are inserted from one end, in stack deletions should be done
from the same end. So, as the items are deleted, the item below the top
item becomes the new top item and so the position of the top most item is
decremented as shown in above figure The items deleted in order are 40,
10, 25, 20 and 30. Finally, when all items are deleted, top points to bottom
of stack. When the stack is empty, it is not possible to delete any item and
this situation is called under flow of stack.
So, the main operations to be performed on stacks are insertion and
deletion. Inserting an item into the stack when stack is not full is called push
operation and deleting an item from the stack when stack is not empty is
called pop operation. Other operations that can be performed are display
the contents of the stack, check whether the stack is empty or not, etc., Let
us see how push and pop operations are implemented.
Self Assessment Questions
1. Define stack with its different operations.
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 67
2. Discuss the stack Insertion and deletion of element from/to stack with
suitable example.
3.2 Insert/Push operation
To design a C function, to start with let us assume that three items are
already added to the stack and stack is identified by s as shown in figure a.
Here, the index top points to 30 which is the topmost item. Here, the value
of top is 2. Now, if an item 40 is to be inserted, first increment top by 1 and
then insert an item. The corresponding C statements are:
top = top + 1;
s[top] = item;
These two statements can also be written as
s[+ + top] = item
But, as we insert an item we must take tare of the overflow situation i.e.,
when top reaches STACK_SIZE-l, stack results in overflow condition and
appropriate error message has to be returned as shown below:
if (top == STACK_SIZE -1)
{
printf("Stack overflow\n");
return;
}
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 68
Here, ST ACK_SIZE should be #defined and is called symbolic constant the value of which cannot be modified. If the above condition fails, the item has to be inserted. Now, the C code to insert an item into the stack can be written as
if (top == ST ACK_SIZE -1)
{
printf("Stack overflow\n");
return;
}
s[ + + top] = item;
It is clear from this code that as the item is inserted, the contents of the stack identified by s and top are affected and so they should be passed and used as pointers as shown in below example
Example 1: C function to insert an integer item
void push(int item, int *top, int s[])
{
if (*top == STACK_SIZE -1)
{
printf("Stack overflow\n");
return;
}
s[+ +(*top)] = item; /* Increment top and then insert an item */
}
Note: In above Example inserts an item of integer data type into the stack. To insert an item of character data type, the changes done are provided in below example.
Example 2: C function to insert a character item
void push(char item, int *top, char s[])
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 69
{
if (*top == ST ACK_SIZE -1)
{
printf("Stack overflow\n");
return;
}
s[+ +(*top)] = item; /* Insert an item on the stack */
}
3.3 Delete/Pop operation
Deleting an element from the stack is called „pop’ operation. This can be achieved by first accessing the top element s[top] and then decrementing top by one as shown below:
item = s[top--];
Each time, the item is deleted, top is decremented and finally, when the stack is empty the top will be -1 and so, it is not possible to delete any item from the stack. The above statement has be executed only if stack is not empty. Hence, the code to delete an item from stack can be written as
if (top == -1)
{
return -1; /* Indicates empty stack */
}
/* Access the item and delete */
item = s[top--]; .
return item;
As the value of top changes every time the item is deleted, top can be used as a pointer variable. The complete function is shown in below example 1. The example 2 shows how to delete a character item from the stack.
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 70
Example 1: C function to delete an integer item
int pop(int *top, int s[ ] )
{
int item;
if (*top == -1)
{
return 0; /* Indicates empty stack */
}
item = s[(*top)--];/* Access the item and delete */
return item; /* Send the item deleted to the calling function */
}
Example 2: C function to delete a character item
char pop(int *top, chars[])
{
char item;
if(*top= =-1)
{
return 0; /* Indicates empty stack */
}
item = s[(*top)--];/* Access the item and delete */
return item; /* Send the item deleted to the calling function */
}
3.4 Display
Assume that the stack contains three elements as shown below:
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 71
The item 30 is at the top of the stack and item 10 is at the bottom of the stack. Usually, the contents of the stack are displayed from the bottom of the stack till the top of the stack is reached. So, first item to be displayed is 10, next item to be displayed is 20 and final item to be displayed is 30. So, the code corresponding to this can take the following form
for (i = 0; i <= top; i+ +)
{
printf("%d\n", s[i]);
}
But, the above statement should not be executed when stack is empty i.e., when top takes the value -1. So, the modified code can be written as shown in below example.
Example 1: C function to display the contents of the stack
void display(int top, int s[])
{
int i;
if(top= = -1)
{
printf("Stack is empty\n");
return;
}
printf("Contents of the stack\n");
for (i = 0; i <= top; i++)
{
printf("%d\n", s[i]);
}
}
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 72
Self Assessment Questions
1. Explain the POP and PUSH operations with an example.
2. Write steps to display elements from the STACK.
3.5 Stack implementation using arrays
In the previous sections we have seen how the stacks can be implemented using arrays. The complete program to perform operations such as push, pop and display is provided in below example. Two semicolons (i.e.,;;} in the for loop indicates that for loop is an infinite loop.
Example : C Program to implement the stack using arrays
#include <stdio.h>
#include <process.h>
#define ST ACK_SIZE 5
/* Include function push shown in example 3.2 Eg. -1 */
/*Include function pop shown in example 3.3 Eg. -1 */
/* Include function display shown in example 3.4 Eg. -1 */
void main( )
{
int top; /* Points to top of the stack */
int s[10]; /* Holds the stack items */
int item; /* Item to be inserted or deleted item */
int choice; /* user choice for push, pop and display */
top = -1; /* Stack is empty to start with */
for (;;)
{
printf("1: Push 2: Pop\n");
printf("3: Display 4: Exit\n");
printf("Enter the choice\n");
scanf("%d",& choice);
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 73
switch( choice )
{
case 1:
printf("Enter the item to be inserted\n"); scanf("%d",& item);
push(item, & top,s);
break;
case 2:
item = pop(&top,s);
if (item = = 0)
printf("Stack is empty\n");
else
printf("Item deleted = %d\n", item);
break;
case 3:
display( top,s );
break;
default:
exit(0);
}
}
}
Output
1 :Push 2: Pop
3: Display 4: Exit
Enter the choice
1
Enter the item to be inserted
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 74
10
1: Push 2: Pop
3: Display 4: Exit
Enter the choice
1
Enter the item to be inserted
20
1: Push 2: Pop
3: Display 4: Exit
Enter the choice
3
Contents of the stack
10
20
1: Push 2: Pop
3: Display 4: Exit
Enter the choice
2
Item deleted = 20
1: Push 2: Pop
3: Display 4: Exit
Enter the choice
2
Item deleted = 10
1: Push 2: Pop
3: Display 4: Exit
Enter the choice
2
Stack is empty
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 75
1: Push 2: Pop
3: Display 4: Exit
Enter the choice
4
3.6 Applications of stack
A stack is very useful in situations when data have to be stored and then retrieved in the reverse order. Some applications of stack are listed below:
i. Function Calls:
We have already seen the role stacks plays in nested function calls. When the main program calls a function named F, a stack frame for F gets pushed on top of the stack frame for main. If F calls another function G, a new stack frame for G is pushed on top of the frame for F. When G finishes its processing and returns, its frame gets popped off the stack, restoring F to the top of the stack.
ii. Large number Arithmetic:
As another example, consider adding very large numbers. Suppose we wanted to add 353,120,457,764,910,452,008,700 and 234,765,000,129,654,080,277. First of all note that it would be difficult to represent the numbers as integer variables, as they cannot hold such large values. The problem can be solved by treating the numbers as strings of numerals, store them on two stacks, and then perform addition by popping numbers from the stacks.
iii. Evaluation of arithmetic expressions:
Stacks are useful in evaluation of arithmetic expressions. Consider the expression 5 * 3 +2 + 6 * 4
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 76
The expression can be evaluated by first multiplying 5 and 3, storing the result in A, adding 2 and A, saving the result in A. We then multiply 6 and 4 and save the answer in B. We finish off by adding A and B and leaving the final answer in A.
A = 15 2 +
= 17
B = 6 4 *
= 24
A = 17 24 +
= 41
We can write this sequence of operations as follows:
5 3 * 2 + 6 4 * +
This notation is known as postfix notation and is evaluated as described above. We shall shortly show how this form can be generated using a stack.
Basically there are 3 types of notations for expressions. The standard form is known as the infix form. The other two are postfix and prefix forms.
Infix: operator is between operands A + B
Postfix : operator follows operands A B +
Prefix: operator precedes operands + A B
Note that all infix expressions can not be evaluated by using the left to right order of the operators inside the expression. However, the operators in a postfix expression are ALWAYS in the correct evaluation order. Thus evaluation of an infix expression is done in two steps. The first step is to convert it into its equivalent postfix expression. The second step involves evaluation of the postfix expression. We shall see in this section, how stacks are useful in carrying out both the steps. Let us first examine the basic process of infix to postfix conversion. Infix to postfix conversion:
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 77
Example 1:
a + b * c Infix form
(precedence of * is higher than of +)
a + (b * c) convert the multiplication
a + ( b c * ) convert the addition
a (b c * ) + Remove parentheses
a b c * + Postfix form
Note that there is no need of parentheses in postfix forms.
Example 2:
( A + B ) * C Infix form
( A B + ) * C Convert the addition
(A B + ) C * Convert multiplication
A B + C * Postfix form
No need of parenthesis anywhere
Example 3:
a + (( b * c ) / d )
a + ( ( b c * ) /d )
(precedence of * and / are same and they are left associative)
a + ( b c * d / )
a b c * d / +
• More examples
Infix Postfix
(a + b) * (c – d) a b + c d - *
a – b / (c + d * e) a b c d e * + / -
((a + b) * c – (d – e))/(f + g) a b + c * d e - - f g + /
Order of precedence for operators:
multiplication (*) and division (/)
addition (+) and subtraction (-)
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 78
The association is assumed to be left to right.
i.e. a + b + c = (a+b)+c = ab+c+
Evaluating a Postfix Expression
We can evaluate a postfix expression using a stack. Each operator in a
postfix string corresponds to the previous two operands. Each time we read
an operand we push it onto a stack. When we reach an operator its
associated operands (the top two elements on the stack) are popped out
from the stack. We then perform the indicated operation on them and push
the result on top of the stack so that it will be available for use as one of the
operands for the next operator. The following example shows how a
postfix expression can be evaluated using a stack.
Example
6 5 2 3 + 8 * + 3 + *
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 79
The process stops when there are no more operator left in the string. The result of evaluating the expression is obtained just by popping off the single element. More examples will be done in the lecture and recitation labs.
Self Assessment Questions
1. Discuss the various STACK applications with suitable example of each.
2. Explain how Stacks are useful in evaluation of arithmetic expressions with example.
3. Write a suitable example of following arithmetic notations
infix , postfix and prefix forms.
3.7 Stacks using structures
So far we have seen how a stack is implemented using an array and various applications of stacks. In this approach whenever a function push() is called, we have to pass three parameters namely item, top and S, where item is the element to be pushed, top is an integer value which is the index of the top most element in the array S. But, as the number of parameters increases, the overhead of programming also increases and efficiency decreases.
In such cases, we group all related items under a common name using a structure and pass structures as parameters, which eventually reduces the burden and increases the efficiency. In our stack implementation, instead of passing two parameters top and S, we can pass only one parameter if we use a structure. So, a stack can be declared as a structure containing two objects viz., an array to store the elements of the stack and an integer indicating the position of the topmost element in the array. The declaration can take the following form:
#define STACK_SIZE 5
struct stack
{
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 80
int items[STACK_SIZE];
int top;
};
typedef struct stack STACK;
Once this definition is done, we can use a variable s to access the contents of the stack and to obtain the position of the top most element. The declaration for this can take the form
STACK s;
The position of the top most element and the element itself can be accessed (using the „.‟ operator) by specifying?
s. top
and
s. items[s. top];
If the declaration is of the form STACK *s, the position of the top most element and top most element can be accessed by specifying
s->top
and
s->items[s->top];
Let us implement stacks using structures also. We know that the stack is empty, if the position of the top most element is -1. The function is_empty( ) which returns true whenever the stack is empty and returns false whenever the stack is not empty is shown in below example 1.
Example 1. : Function to check whether the stack is empty or not
int is_empty(STACK *s)
{
if (s->top = = -1) return -1; /* Stack empty */
return 0; /* Stack is not empty */
}
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 81
The function is_full( ) returns true if stack is full and returns false if the stack is not full. This function is shown in below example 2.
Example 2: Function to check whether the stack is full or not
int is_full(STACK *s)
{
if ( s->top == STACK _ SlZE -1) return 1; /* Stack is full */
return 0; /* Stack is not full */
}
The function to insert an integer item into the stack is shown in below example 3.
Example 3: Function to insert an integer item into the stack
void push(int item, STACK *s)
{
if ( is_full(s) )
{
printf("Stack Overflow\n");
return;
}
s->top+ +; /* Update top to point to next item */
s->items[s->top] = item; /* Insert the item into the stack*/
}
The function to insert a character item into the stack is shown in below example 4.
Example 4 : Function to insert a character item into the stack
void push(char item. ST ACK *s)
{
if ( is_full(s) )
{
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 82
printf("Stack Overflow\n");
return;
}
s->top++; /* Update top to point to next item */
s->items[s->top] = item; /* Insert the item into the stack*/
}
The function to delete an integer item from the stack is shown in below example 5
Example 5 : Function to delete an integer item from the stack
int pop(ST ACK *s)
{
int item;
if ( is_ empty(s) )
{
printf("Stack Underflow\n");
return 0;
}
item = s->items[s->top]; /* Access the top element */
s->top--; /* Update the pointer to point to previous item
return item; /* Return the top item to the calling function */
}
The function to delete a character item from the stack is shown in below example 6
Example 6 : Function to delete a character item from the stack.
char pop(STACK *s)
{
char item;
if ( is_empty(s) )
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 83
{
printf("Stack Underflow\n");
return 0;
}
item = s->items[s->top]; /* Access the top element */
s->top--; /* Update the pointer to point to previous item */
return item; /* Return the top item to the calling function */
}
The program to display the contents of stack is shown in below example 7.
Example 7 : Function to display the contents of the stack
void display(STACK s)
{
int i;
if ( is_empty(&s) )
{
printf("Stack is empty\n");
return 0;
}
printf("The contents of the stack\n");
for (i = 0; i<= s.top; i + +)
{
printf("%d\n ",s.items[i];
}
}
The C program to simulate the working of a stack using structures is shown in below example.
Example 8 : C program to simulate the stack operations using structures
#include<stdio.h>
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 84
#include <process.h>
#define ST ACK_SIZE 5
struct stack
{
int items[STACK_SIZE];
int top;
} ;
typedef struct stack STACK;
/* Include example 1: Check for empty stack */
/* Include example 2: Check for stack full or not */
/* Include example 3: To insert an item on the stack */
/* Include example 5: To delete an item from the stack */
/* Include example 7: To display the contents of the stack */
void main()
{
int item; /* Item to be inserted */
int choice; /* Push, pop, display or quit */
STACK s; /* To store items */
s.top = -1; /* Stack is empty initially */
for (;;)
{
printf("1: Push 2: Pop\n");
printf("3: Disply 4: Exit\n");
printf("Enter the choice\n");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter the item to be inserted\n");
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 85
scanf("%d",& item);
push(item, & s);
break;
case 2:
item = pop(&s);
if (item != 0)
{
printf("Item deleted = %d\n", item);
}
break;
case 3:
display(s);
break;
default: exit(0);
}
}
}
3.8 Sample C programs to represents the Stack Implementation:
Example 1
// Stack Implementation using arrays to Insert element in the Stack
#include<stdio.h>
#include<conio.h>
#define Max 5
int Staff (Max] , top=-l;
void display( )
{
if ((top= =-l) || (top= =0))
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 86
{
printf{"\n Stack is full \n");
}
else
{
printf{"\n Stack elements are \n”);
for(int i=top-1;i>=0;i--)
printf("%5d", Staff([i]);
}
}
void push ( )
{
int ele;
char ch;
if(top-=-l)
top=0;
do
{ if(top>=5)
{
printf(“\n STACK IS FULL”);
break;
}
else
{ clrscr( );
printf ("\nENTER THE ELEMENT TO BE INSERTED\n") ;
scanf("%d",&ele) ;
Staff(top++]=ele;
display ( ) ;
}
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 87
printf ("\nDO U WANT 2 ADD MORE ELEMENTS:?\n");
scanf ( "\n%c" , &ch);
} while ( (ch= ='y' ) || (ch=='Y' ) );
}
void pop ( )
{
if ( (top= =-l) || (top= =0))
{
printf ("\nstack is under flow\n");
}
else
{
printf{"\n %d is deleed from stack\n",Staff(--top]) ;
display( );
}
}
Example 2
//Stack Implementation using push and pop
void main()
{
clrscr( );
char c;
int choice;
do
{
clrscr() ;
printf("\n Enter the choice\n");
printf ("l->push\n");
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 88
printf ("2->pop\n") ;
scant (" %d ",&choice);
if(choice= =l)
push( );
else if(choice= =2)
pop ( ) ;
else
printf (" \ninvalid choice");
printf ("\ndo u want 2 continue:?";
scanf("\n%c",&c) ;
}while{ (c=='y')||(c=='Y'));
}
Example 3
// Stack Implementation using array
#include<stdio.h>
#include<conio.h>
#define Max 5
int a [Max] , top=-l;-
void push()
{
int ele;
char ch;
if(top= =-l)
top=0;
do
{
if(top>=5)
{
printf("Stack if full");
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 89
break;
else
{
clrscr();
printf ( "Enter element to be inserted\n" ) ;
scanf(“%d”,&ele);
a[top++] =ele;
}
printf ( "Do you want to add more elements: ?\n") ;
scanf ( "\n%c" , &ch);
printf(“%c”,ch)
}while((ch= = „Y‟)||(ch==‟Y‟));
}
void pop( )
{
if(top= =-l)
{
printf ( "stack is underflow\n");
}
else
{
for(int i=top-l;i>=0;i--)
printf ("%d\n", a [i] ) ;
}
}
void main()
{
clrscr ( ) ;
char c;
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 90
int choice;
do
{
clrscr( );
printf ("Enter Your Choice\n");
printf("l -> Push\n");
printf ("2 -> Pop\n");
scanf ("%d", &Choice);
if(choice= =l)
push( );
else if (choice= = 2)
pop( );
else
printf(“invalid choice”);
printf(“Do You Want to continue\n”);
scanf(“\n%c”,&c);
}while((c= = „y‟)||(c= = „Y‟));
}
3.9 Summary
A tack is defined as a special type of data structure where items are inserted from one end called top of stack and items are deleted from the same end. Here, the last item inserted will be on top of stack. Since deletion is done from the same end, Last item Inserted is the First item to be deleted Out from the stack and so, stack is also called Last In First Out (LIFO) data structure. A stack is very useful in situations when data have to be stored and then retrieved in the reverse order. Some applications of stack are : Function Calls, Large number Arithmetic, and Evaluation of arithmetic expressions etc.
Data Structures using „C‟ Unit 3
Sikkim Manipal University Page No.: 91
3.10 Terminal Questions
1. Define Stack with neat diagram ? Discuss the Push and Pop Operation.
2. Write a C Program to implement the stack operations using arrays.
3. Discuss the various STACK applications with suitable example of each.
4. Explain how Stacks are useful in evaluation of arithmetic expressions with example.
5. Explain the Evaluating a Postfix Expression using suitable example.
6. Illustrate the C program to represents the Stack Implementation on POP and PUSH operation.