Stack Data Structure – Best Guide 2021
A stack is a basic data structure that can be logically thought as linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack.
The basic implementation of a stack is also called a LIFO (Last In First Out).
Stack Data Structure Definition:
A stack data structure is a list of elements in which an element may be inserted or deleted only at one end, called me top of the stack. This means, in particular, that elements are removed from a stack in the reverse order of that in which they were inserted into the stack.
Special terminology is used for two basic operations associated with stacks:
(a) “Push” is the term used to insert an element into a stack.
(b) “Pop” is the term used to delete an element from a stack.
- There are basically three operations that can be performed on stacks.
1) Inserting an item into a stack (push).
2) Deleting an item from the stack (pop).
3) Displaying the contents of the stack(pip).
Below are some of operations a stack data type supports:
Stack<item-type> Operations push (new-item :item-type) Adds an item onto the stack. top ():item-type Returns the last item pushed onto the stack. pop () Removes the most-recently-pushed item from the stack. is-empty ():Boolean True if no more items can be popped and there is no top item. is-full ():Boolean True if no more items can be pushed. get-size ():Integer Returns the number of elements on the stack.
- All operations except get-size() can be performed in O(1) time. get-size() runs in at worst O(N).
Array Implementation of a Stack Data Structure:
When an array is used to implement a stack, the push and pop operations are realized by using the operations available on an array. The limitation of an array implementation is that the stack cannot grow and shrink dynamically as per the requirement.
C program to implement a stack using an array.
#include <stdio.h>
#define MAX 10 /* The maximum size of the stack */
#include <stdlib.h>
void push(int stack[], int *top, int value)
{
if(*top < MAX )
{
*top = *top + 1;
stack[*top] = value;
}
else
{
printf("The stack is full can not push a value\n");
exit(0);
}
}
void pop(int stack[], int *top, int * value)
{
if(*top >= 0 )
{
*value = stack[*top];
*top = *top - 1;
}
else
{
printf("The stack is empty can not pop a value\n");
exit(0);
}
}
void main()
{
int stack[MAX];
int top = -1;
int n,value;
do
{
do
{
printf("Enter the element to be pushed\n");
scanf("%d",&value);
push(stack,&top,value);
printf("Enter 1 to continue\n");
scanf("%d",&n);
} while(n == 1);
printf("Enter 1 to pop an element\n");
scanf("%d",&n);
while( n == 1)
{
pop(stack,&top,&value);
printf("The value poped is %d\n",value);
printf("Enter 1 to pop an element\n");
scanf("%d",&n);
}
printf("Enter 1 to continue\n");
scanf("%d",&n);
} while(n == 1);
}
Example Output:
Enter the element to be pushed 10 Enter 1 to continue 1 Enter the element to be pushed 20 Enter 1 to continue 0 Enter 1 to pop an element 1 The value popped is 20 Enter 1 to pop an element 0 Enter 1 to continue 1 Enter the element to be pushed 40 Enter 1 to continue 1 Enter the element to be pushed 50 Enter 1 to continue 0 Enter 1 to pop an element 1 The value popped is 50 Enter 1 to pop an element 1 The value popped is 40 Enter 1 to pop an element 1 The value popped is 10 Enter 1 to pop an element 0 Enter 1 to continue 0
Linked List Implementation
type Stack<item_type> data list:Singly Linked List<item_type> constructor() list := new Singly-Linked-List() end constructor
When you want to push something onto the list, you simply add it to the front of the linked list. The previous top is then ”next” from the item being added and the list’s front pointer points to the new item.
method push(new_item:item_type) list.prepend(new_item) end method
To look at the top item, you just examine the first item in the linked list
method top():item_type return list.get-begin().get-value() end method
When you want to pop something off the list, simply remove the first item from the linked list.
method pop()
list.remove-first()
end method
A check for emptiness is easy. Just check if the list is empty
method is-empty():Boolean return list.is-empty() end method
A check for full is simple. Linked lists are considered to be limitless in size.
method is-full():Boolean return False end method
A check for the size is again passed through to the list.
method get-size():Integer return list.get-size() end method end type
- In a linked list, accessing the first element is an O(1) operation because the list contains a pointer that checks for empty as done here are also O(1). Most of the time, users of a Stack do not use the getSize() operation, and so a bit of space can be saved by not optimizing it.
Complexity:
All operations are O(1) with exception of occasional push and clear, which should replace all entries by null in order to let them be garbage-collected. Array implementation does not replace null entries. The Vector implementation does.
Program for implementation of a stack using the linked list.
# include <stdio.h>
# include <stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *push(struct node *p, int value)
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
/* creates new node
using data value
passed as parameter */
if(temp==NULL)
{
printf("No Memory available Error\n");
exit(0);
}
temp->data = value;
temp->link = p;
p = temp;
return(p);
}
struct node *pop(struct node *p, int *value)
{
struct node *temp;
if(p==NULL)
{
printf(" The stack is empty can not pop Error\n");
exit(0);
}
*value = p->data;
temp = p;
p = p->link;
free(temp);
return(p);
}
void main()
{
struct node *top = NULL;
int n,value;
do
{
do
{
printf("Enter the element to be pushed\n");
scanf("%d",&value);
top = push(top,value);
printf("Enter 1 to continue\n");
scanf("%d",&n);
} while(n == 1);
printf("Enter 1 to pop an element\n");
scanf("%d",&n);
while( n == 1)
{
top = pop(top,&value);
printf("The value poped is %d\n",value);
printf("Enter 1 to pop an element\n");
scanf("%d",&n);
}
printf("Enter 1 to continue\n");
scanf("%d",&n);
} while(n == 1);
}
Example Output:
Input and Output Enter the element to be pushed 10 Enter 1 to continue 1 Enter the element to be pushed 20 Enter 1 to continue 0 Enter 1 to pop an element 1 The value popped is 20 Enter 1 to pop an element 1 The value poped is 10 Enter 1 to pop an element 0 Enter 1 to continue 1 Enter the element to be pushed 30 Enter 1 to continue 1 Enter the element to be pushed 40 Enter 1 to continue 0 Enter 1 to pop an element 1 The value popped is 40 Enter 1 to pop an element 0 Enter 1 to continue 1 Enter the element to be pushed 50 Enter 1 to continue 0 Enter 1 to pop an element 1 The value popped is 50 Enter 1 to pop an element 1 The value popped is 30 Enter 1 to pop an element 0 Enter 1 to continue 0
Applications of Stack Data Structure
- Evaluation of Arithmetic Expressions
- Backtracking
- Delimiter Checking
- Reverse a Data
- Processing Function Calls.