Stacks
Stack is a linear data structure. It follows LIFO (Last-in, First-out) policy. It has two main operations - push (insert element onto stack) and pop (delete element from stack). Stack has two exceptions - underflows (if we attempt to pop an empty stack) and overflows (trying to push an element on a full stack).
The concept of data structures have been taken from the real world. So, let’s dive into an instance from the physical world: the picture shows a stack of books. There are n (n is 6) books (elements) in total. Let’s index the books with numbers starting from 0 to n-1. The first book placed on the table is “Rain in the Mountains” whose index is 0 and the latest book placed is “The Da Vinci Code” with index 5. Now, if we remove the last placed book (executing pop) then the topmost element becomes the book with index 4. Now, if we place the previously removed book (executing push) on top of the stack then the topmost element will have index 5. This is how it follows LIFO policy, every time the last inserted element gets removed first from the stack. We cannot remove or insert a book from otherwise positions, doing so would break the rule of sequential access.
Suppose, you have a box with size limit of keeping only 6 books. When the box is full and you try to insert another book, as there is no space, this would be an exception (overflows). Likewise, when the box is empty and you think of fetching a book from the box, as it has nothing, this would also be an exception (underflows).
That’s all about how stacks work :)
The most interesting application of stack to me is the support it provides for recursion. It is also used for undo sequence in text editors, matching tags in HTML and XML, etc.
There are two common ways in which stacks are implemented:-
- With simple array - here the size of the stack must be predefined. Resizing is not allowed.
- With linked list - resizing is allowed here and this is the advantage over simple array implementation.
Stack implementation in C #
#include<stdio.h>
#include<stdlib.h>
#define MAX 3
typedef struct stack //globally declared structure
{
int array[MAX];
int top;
}stack;
stack s; //s is a global variable of datatype stack
//function signatures below
full();
isempty();
int push();
int pop();
void display();
void main()
{
int choice, data, reply;
s.top=-1; //Empty stack created
do
{
printf("\n1. Push an element onto stack.\n");
printf("2. Pop an element from stack.\n");
printf("3. Display current stack contents.\n");
printf("4. Exit.\n");
printf("\nEnter your choice:- ");
scanf("%d", &choice);
switch(choice)
{
case 1:
{
printf("\nEnter an integer element:- ");
scanf("%d", &data);
reply=push(data);
if(reply==1)
printf("\nValue Pushed.\n");
else
printf("\nStack Overflows.\n");
break;
}
case 2:
{
reply=pop();
if(reply==0)
printf("\nStack Underflows.\n");
else
printf("\nPopped Value is %d.\n", reply);
break;
}
case 3:
{
if(isempty())
{
printf("\nThe stack is empty\n");
break;
}
else if(full())
{
printf("\nThe stack is full.\n");
display();
break;
}
else
{
display();
printf("\nEmpty room(s) in stack:- %d\n", (MAX-1)-s.top);
break;
}
}
case 4:
exit(1);
default:
{
printf("\nInvalid Input. Try Again.\n");
break;
}
}
}while(1);
}
//full() and isempty() are functions that carry out auxilliary stack operations
full()
{
return (s.top==(MAX-1)); //True if position of topmost element is equal to position of last entered element
}
isempty()
{
return (s.top==-1); //In main(), s.top initialized to -1, creating empty stack
}
int push(int data)
{
if(!full())
{
s.top=s.top+1;
s.array[s.top]=data;
return 1;
}
else
return 0; //stack overflows
}
int pop()
{
if(isempty())
return 0; //stack underflows
else
{
s.top=s.top-1;
return (s.array[s.top+1]); //returns the popped value
}
}
void display()
{
int i=s.top;
printf("\nThe stack contents are:- \n");
while(i!=-1)
{
printf("Element %d - %d\n", i--, s.array[i]);
//i-- serves two purpose here
}
}
Linked list implementation of stack in C #
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *next;
}node;
int count=-1; //to count elements in stack
void main()
{
int choice, data, reply;
node *top;
top=NULL; //Empty Stack created
do
{
printf("\n1. Push an element onto stack.\n");
printf("2. Pop an element from stack.\n");
printf("3. Display current stack contents.\n");
printf("4. Exit.\n");
printf("\nEnter your choice:- ");
scanf("%d", &choice);
switch(choice)
{
case 1:
{
printf("\nEnter an integer element:- ");
scanf("%d", &data);
reply=push(data, &top);
if(reply==1)
printf("\nValue Pushed.\n");
else
printf("\nMemory Allocation Failed.\n");
break;
}
case 2:
{
reply=pop(&top);
if(reply==0)
printf("\nStack Underflows.\n");
else
printf("\nPopped Value is %d.\n", reply);
break;
}
case 3:
{
if(top==NULL)
{
printf("\nThe stack is empty\n");
break;
}
else
{
display(top);
break;
}
}
case 4:
exit(0);
default:
{
printf("\nInvalid Input. Try Again.\n");
break;
}
}
}while(1);
}
int push(int data, node **top)
{
node *temp;
temp=(node*)malloc(sizeof(node)); //to create a new room in stack
if(!temp)
return 0; //memory allocation failed
temp->data=data; //pushing given data
temp->next=*top;
*top=temp; //storing the address of the latest element in top
count++;
return 1; //value pushed
}
int pop(node **top)
{
node *temp;
int data;
if(*top==NULL)
return 0; //stack underflows
else
{
temp=*top;
*top=(*top)->next;
data=temp->data; //to show the popped value
free(temp); //deleting the node
count--;
return data;
}
}
void display(node *element)
{
int i=count;
while(element!=NULL)
{
printf("Element %d - %d\n", i--, element->data);
element=element->next;
}
}