Page 150 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 9: Stacks

printf(“Stack is empty\n”); Notes
}
return;
}
void showelements()
{
if (top<=0)
printf(“Stack is empty\n”);
else
for(int i=0; i<top; ++i)
printf(“%d\n”, stack[i]);
}
In this program, the size of the stack was declared as 10. So, stack cannot hold more than
10 elements. The main operations that can be performed on a stack are push and pop. However,
in a program, we need to provide two more options, namely, showelements and
exit.showelements will display the elements of the stack. In case, the user is not interested to
perform any operation on the stack and would like to get out of the program, then s/he will
select exit option. It will log the user out of the program. Choice is a variable which will enable
the user to select the option from the push, pop, showelements and exit operations. Top points
to the index of the free location in the stack to where the next element can be pushed. Element is
the variable which accepts the integer that has to be pushed to the stack or will hold the top
element of the stack that has to be popped from the stack. The array stack can hold at most
10 elements. Push and pop will perform the operations of pushing the element to the stack and
popping the element from the stack respectively.

9.3.2 Linked List Representation of Stacks

When a stack is implemented using arrays, it suffers from the basic limitation of an array – that
is, 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 the case of a linked stack, we shall push
and pop nodes from one end of a linked list. The stack, as linked list is represented as a singly
connected list. Each node in the linked list contains the data and a pointer that gives location of
the next node in the list.
Program given below implements a stack using linked lists.
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
/* Definition of the structure node */
typedef struct node
{
int data;
struct node *next;
} ;
/* Definition of push function */

LOVELY PROFESSIONAL UNIVERSITY 143