Site pages
Current course
Lesson- 15 Pointers, Stacks, Push/Pop operations.
15.1 Introduction
Be it items in store, books in a library, or notes in a bank, the moment they become more then handful man starts stacking them neatly. It was natural, that when man started programming data, stack was one of the first structures that he thought of when faced with the problem of maintaining data in an orderly fashion. There is a small difference however, data in a stack is consumed in an orderly fashion; same may not be true in case of wads of nodes. Some of the examples of stack is shown in figure 15.1
Figure 15.1 Stack Examples
A Stack is a data structure in which addition of new element or deletion of an existing element always takes place at the same end. This end is often known as top of the stack. This situation can be compared to a stack of plates in a cafeteria where every new plate added to the stack is always added at the top of the stack. The two changes that can be made to a stack are given special names. When an item is added to a stack, the operation is called push, and when an item is removed from the stack, the operation is called pop. Stack is also called last-in-first-out (LIFO) list. If the elements are added at continuously to the stack it grows at one end. This is shown in Figure 15.2.
Figure 15.2 Simple Stack with push operation
On deletion of elements the stack shrinks at the same end, as the elements at the top get removed the stack shrinks. This is shown in Figure 15.3.
Figure 15.3 Simple Stack with Pop operation
15.2 Operation on Stack
A Stack Generally implements with two basic operations i.e. Push and Pop.
· Push – Allows adding an element t the top of the stack.
· Pop – Allows removing an element t the top of the stack.
Before making the use of stack in program, it is very important to decide how to represent a stack. There are several ways of representing a stack. Let us see how efficient it is to use an array to represent a stack.
15.3 Stack as an array
Stack contains an ordered collection of elements. An array is used to store ordered list of elements. Hence it would be very easy to manage stack if represent it using an array. However, the problem with an array is that we are required to declare the size of an array before using it in our program. This means the size of an array should be fixed. Stack on other hand does not have any fixed size. It keeps on changing, as the elements in the stack are popped or pushed.
Though an array and a stack are totally different data structures, an array can be used to store the elements of a stack. We can declare an array with a maximum size large enough to manage a stack. As a result the stack can grow or shrink within the space reserved for it. Let us see a program to implements a stack using an array.
#include <stdio.h>
#include <conio.h>
#define MAX 10
struct stack
{
int arr[MAX] ;
int top ;
} ;
void initstack ( struct stack * ) ;
void push ( struct stack *, int item ) ;
int pop ( struct stack * ) ;
void main( )
{
struct stack s ;
int i ;
clrscr( ) ;
initstack ( &s ) ;
push ( &s, 11 ) ;
push ( &s, 23 ) ;
push ( &s, -8 ) ;
push ( &s, 16 ) ;
push ( &s, 27 ) ;
push ( &s, 14 ) ;
push ( &s, 20 ) ;
push ( &s, 39 ) ;
push ( &s, 2 ) ;
push ( &s, 15 ) ;
push ( &s, 7 ) ;
i = pop ( &s ) ;
printf ( "\n\nItem popped: %d", i ) ;
i = pop ( &s ) ;
printf ( "\nItem popped: %d", i ) ;
i = pop ( &s ) ;
printf ( "\nItem popped: %d", i ) ;
i = pop ( &s ) ;
printf ( "\nItem popped: %d", i ) ;
i = pop ( &s ) ;
printf ( "\nItem popped: %d", i ) ;
getch( ) ;
}
/* intializes the stack */
void initstack ( struct stack *s )
{
s -> top = -1 ;
}
/* adds an element to the stack */
void push ( struct stack *s, int item )
{
if ( s -> top == MAX - 1 )
{
printf ( "\nStack is full." ) ;
return ;
}
s -> top++ ;
s -> arr[s ->top] = item ;
}
/* removes an element from the stack */
int pop ( struct stack *s )
{
int data ;
if ( s -> top == -1 )
{
printf ( "\nStack is empty." ) ;
return NULL ;
}
data = s -> arr[s -> top] ;
s -> top-- ;
return data ;
}
Output:
Stack is full
Item popped: 15
Item popped: 2
Item popped: 39
Item popped: 20
Item popped: 14
Here to begin with we have defined structure called stack. The push() and pop() functions are used respectively to add and delete items from the stack. The actual storage of stack elements is done in an array arr. The variable top is an index into that array. It contains a value where addition or deletion is going to take place in the array, and thereby in the stack. To indicate that the stack is empty to begin with, the variable top is set with value -1 calling the function initstack().
Every time an element is added to the stack, it is verified whether such an addition is possible at all. If it is not then the message “ Stack is full” is reported. Since w have declared the array to hold 10 elements, the stack would be considered full if the value of top becomes equal to 9.
In main() we called push() function to add 11 elements to the stack. The value of top would become 9 after adding the 10 elements. As a result, the 11th element 7 would not get added to the stack. Lastly, we have removed few elements from the stack by calling the pop() function.
15.4 Stack as a Linked list
In the earlier section we had used arrays to store the elements that get added to the stack. However, when implemented as an array, that its size cannot be increased or decreased once it is declared, As a result, one ends up reserving either too much space or too less space for an array and in turn for a stack. This problem can be overcome if we implement a stack using a linked list. In case of linked stack we shall push and pop nodes from one end of a linked list.
The stack as linked list is represented as a single connected list. Each node in the linked list contains the data nada pointer that gives address of the next node in the list. The node in the list is a structure as shown below:
struct node
{
<data type> data;
node *link;
};
Where <data type> indicates that the data can be any type like int, float, char etc, and link, is a pointer to the next node in the list. The pointer to beginning of the list serves the purpose of the top of the stack. Figure 15.4 shows the linked list representation of the stack.
Figure 15.4 Linked list representation of stack.
Let us now see a program that implements stack as a linked list:
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
/* structure containing data part and linkpart */
struct node
{
int data ;
struct node *link ;
} ;
void push ( struct node **, int ) ;
int pop ( struct node ** ) ;
void delstack ( struct node ** ) ;
void main( )
{
struct node *s = NULL ;
int i ;
clrscr( ) ;
push ( &s, 14 ) ;
push ( &s, -3 ) ;
push ( &s, 18 ) ;
push ( &s, 29 ) ;
push ( &s, 31 ) ;
push ( &s, 16 ) ;
i = pop ( &s ) ;
printf ( "\nItem popped: %d", i ) ;
i = pop ( &s ) ;
printf ( "\nItem popped: %d", i ) ;
i = pop ( &s ) ;
printf ( "\nItem popped: %d", i ) ;
delstack ( &s ) ;
getch( ) ;
}
/* adds a new node to the stack as linked list */
void push ( struct node **top, int item )
{
struct node *temp ;
temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
if ( temp == NULL )
printf ( "\nStack is full." ) ;
temp -> data = item ;
temp -> link = *top ;
*top = temp ;
}
/* pops an element from the stack */
int pop ( struct node **top )
{
struct node *temp ;
int item ;
if ( *top == NULL )
{
printf ( "\nStack is empty." ) ;
return NULL ;
}
temp = *top ;
item = temp -> data ;
*top = ( *top ) -> link ;
free ( temp ) ;
return item ;
}
/* deallocates memory */
void delstack ( struct node **top )
{
struct node *temp ;
if ( *top == NULL )
return ;
while ( *top != NULL )
{
temp = *top ;
*top = ( *top ) -> link ;
free ( temp ) ;
}
}
Output:
Item popped: 16
Item popped: 31
Item popped: 29
Here we designed a structure called node. The variables s is a pointer to the structure node. Initially s is set to NULL to indicate that the stack is empty. In every call to the function push() we are creating a new node dynamically. As long as there is enough space for dynamic memory allocation temp would never become NULL. If the value if temp happens to be NULL then that would be the stage when the stack would become full.
After, creating a new node, the pointer s should point to the newly created item of the list. Hence, we have assigned the address of this new node to s using the pointer top. The stack as a linked list would grow as shown in figure 15.5.
Figure 15.5 – Stack as a linked list after insertion of elements
In the pop() function, first we are checking whether or not a stack is empty. If the stack is empty the the message “Stack is empty” gets displayed. If the stack is nit empty then the topmost item gets removed from the the list. The stack after removing three items from the list would be shown in figure 15.6.
Figure 15.6 – Stack as a linked list after deletion of elements
Last modified: Monday, 28 October 2013, 8:35 AM