What is Stack?
- Stack is an ordered list of the same type of elements.
- It is a linear list where all insertions and deletions are permitted only at one end of the list.
- Stack is a LIFO (Last In First Out) structure.
- In a stack, when an element is added, it goes to the top of the stack.
Definition
“Stack is a collection of similar data items in which both insertion and deletion operations are performed based on LIFO principle”.
There are two basic operations performed in a Stack:
1. Push()
2. Pop()
1. Push() function is used to add or insert new elements into the stack.
2. Pop() function is used to delete or remove an element from the stack.
- When a stack is completely full, it is said to be Overflow state and if stack is completely empty, it is said to be Underflow state.
- Stack allows operations at one end only. Stack behaves like a real life stack, for example, in a real life, we can remove a plate or dish from the top of the stack only or while playing a deck of cards, we can place or remove a card from top of the stack only.
Similarly, here also, we can only access the top element of a stack. - According to its LIFO structure, the element which is inserted last, is accessed first.
Implementation of Stack
The above diagram represents a stack insertion operation. In a stack, inserting and deleting of elements are performed at a single position which is known as,
Top.
Insertion operation can be performed using Push() function. New element is added at top of the stack and removed from top of the stack, as shown in the diagram below:
An element is removed from top of the stack. Delete operation is based on LIFO principle. This operation is performed using a Pop() function. It means that the insertion and deletion operations are performed at one end i.e at Top.
Following table shows the Position of Top which indicates the status of stack:
| Position of Top | Status of Stack |
|---|
| -1 | Stack is empty. |
| 0 | Only one element in a stack. |
| N - 1 | Stack is full. |
| N | Stack is overflow. (Overflow state) |
Stack using Array
Stack can be implemented using one-dimensional array. One-dimensional array is used to hold elements of a stack. Implementing a stack using array can store fixed number of data values. In a stack, initially top is set to -1. Top is used to keep track of the index of the top most element.
Stack can be defined using array as follows:
typedef struct stack
{
int element [MAX];
int top;
}stack;
In the above code snippet, MAX is a constant and can store defined number of elements. When the value of top becomes MAX – 1 after a series of insertion, it means that stack is full.
Example: Program to implement a stack using Array
#include <stdio.h>
#include <conio.h>
#define MAX 50
void insert();
void delet();
void display();
int stack[MAX], top=-1, element;
void main()
{
int ch;
do
{
printf("\n\n\n\n 1. Insert\n 2. Delete\n 3. Display\n 4. Exit\n");
printf("\n Enter Your Choice: ");
scanf("%d", &ch);
switch(ch)
{
case 1:
insert();
break;
case 2:
delet();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("\n\n Invalid entry. Please try again...\n");
}
}
while(ch!=4);
getch();
}
void insert()
{
if(top == MAX-1)
printf("\n\n Stack is Full.");
else
{
printf("\n\n Enter Element: ");
scanf("%d", &element);
top++;
stack[top] = element;
printf("\n\n Element Inserted = %d", element);
}
}
void delet()
{
if(top == -1)
printf("\n\n Stack is Empty.");
else
{
element = stack[top];
top--;
printf("\n\n Element Deleted = %d", element);
}
}
void display()
{
int i;
if(top == -1)
printf("\n\n Stack is Empty.");
else
{
for(i=top; i>=0; i--)
printf("\n%d", stack[i]);
}
}
2. Display
3. Delete
Stack Operations
As we studied, there are two important operations used for adding the elements and removing the elements. They are Push() and Pop().
Following are the other operations used in Stack:
| Operations | Description |
|---|
| Peek() | The peek() function gets the top element of the stack, without deleting it. |
| isEmpty() | The isEmpty() function checks whether the stack is empty or not. |
| isFull() | The isFull() function is used to check whether the stack is full or not. |
