A stack data structure is a versatile data structure which is useful whenever we want output to be reverse of input, or we want a LIFO - last in first out behavior
.
A function call in most languages employs a stack. The parameters and local variables are pushed to call stack. And a return statement pops out most recent call stack.
Similarly when we want to check if an expression has balanced brackets, we can use a stack to store brackets.
Top of stack:
Unlike a linked list where elements can be added to the end of list or beginning of a list, values are always added to the top of the stack. Just like a plate is added to the top of a stack of plates.
And a value is always removed from top of the stack - similar to a stack of plates again.
A stack abstract data type should define three functions
A stack can be implemented using an array or a linked list. In both these implementations, all of the 4 functions will have O(1) time complexity. In array implementation top will be the index in array.
Let us look at linked list implementation of a stack
Linked List implementation:
In linked list implementation of stack, top of stack can be a node pointer just like head. And to push a value to stack, a node should be added to beginning of list.
To pop a value from stack, a node must be deleted from beginning of linked list.
And checking whether the stack is empty is just checking if top is NULL.
Here is the driver program.
Image from Wikipedia |
A function call in most languages employs a stack. The parameters and local variables are pushed to call stack. And a return statement pops out most recent call stack.
Similarly when we want to check if an expression has balanced brackets, we can use a stack to store brackets.
Top of stack:
Unlike a linked list where elements can be added to the end of list or beginning of a list, values are always added to the top of the stack. Just like a plate is added to the top of a stack of plates.
And a value is always removed from top of the stack - similar to a stack of plates again.
A stack abstract data type should define three functions
- push - push function inserts a value at the top of stack
- pop - pop function removes a value from top of stack
- isempty - isempty function checks if the stack is empty
- peek or top - this gives the value at the top of stack
A stack can be implemented using an array or a linked list. In both these implementations, all of the 4 functions will have O(1) time complexity. In array implementation top will be the index in array.
Let us look at linked list implementation of a stack
Linked List implementation:
In linked list implementation of stack, top of stack can be a node pointer just like head. And to push a value to stack, a node should be added to beginning of list.
NODEPTR push(NODEPTR top,NODEPTR newnode)
{
newnode->next = top;
top = newnode;
return top;
}
To pop a value from stack, a node must be deleted from beginning of linked list.
int pop(NODEPTR *topPtr)
{
if(isempty(*topPtr))
return ERROR;
int num = (*topPtr)->n;
NODEPTR temp = *topPtr;
*topPtr = (*topPtr)->next;
free(temp);
return num;
}
And checking whether the stack is empty is just checking if top is NULL.
int isempty(NODEPTR top)
{
return top==NULL;
}
Here is the driver program.
#include<stdio.h>
#include<stdlib.h>
#define ERROR -1000
struct node
{
int n;
struct node *next;
};
typedef struct node * NODEPTR;
NODEPTR create_node(int value)
{
NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));
temp->next = NULL;
temp->n = value;
return temp;
}
NODEPTR push(NODEPTR top,NODEPTR newnode)
{
newnode->next = top;
top = newnode;
return top;
}
int isempty(NODEPTR top)
{
return top==NULL;
}
int pop(NODEPTR *topPtr)
{
if(isempty(*topPtr))
return ERROR;
int num = (*topPtr)->n;
NODEPTR temp = *topPtr;
*topPtr = (*topPtr)->next;
free(temp);
return num;
}
int main()
{
NODEPTR top = NULL;
NODEPTR nd;
while(1)
{
int option,value;
printf("Enter 1- push 2- pop 3 - exit");
scanf("%d",&option);
if(option==3)
break;
switch(option)
{
case 1: printf("new value to push=");
scanf("%d",&value);
nd = create_node(value);
top = push(top,nd);
break;
case 2: value = pop(&top);
if(value==ERROR)
printf("Stack empty\n");
else
printf("Value popped is %d\n",value);
break;
}
}
}
Comments
Post a Comment