In this section of the tutorial, we will discuss the use of Stack in Data Structure and some important Stack Operations as well as its implementation in programs that will be used thoroughly in this Data Structure tutorial.
Now, let’s move on further to the introduction of Stack in Data Structure.
What is Stack in Data Structure?
Stack is a linear list that has its own limitations where all the additions and deletions are restricted to one end, i.e. the top.
- When we insert a data series into a stack and then remove it, the data order is reversed.
- For example, if we input data {2,6,9,11}, and then remove it. It’s order will be reversed to {11,9,6,2}.
- This property of reversing the order is the reason to call Stack, last in first out in data structure.
- Stack applications can be found everywhere around us, such as a stack of coins or a stack of dishes.
Further, we will learn more about the different Stack Operations in Data Structure.
Stack Operations
There are mainly three basic types of stack operations used in data structure, i.e. push operation, pop operation, and stack top operation.
Now, we will discuss each of these operations in detail.
Push Operation
In push, we insert data values into a stack. It adds an item at the top of the stack.
- After the push of data into the top of the stack, the new data becomes the top of the stack.
- To carry out the push operation, we must ensure that there is space for new data to be added to the stack.
- If there is not enough space in the stack, then the condition of overflow will take if we try to add more data that the stack’s capacity.
Pop Operation
In pop, we remove data values from a stack and return the data to the calling module.
- To pop data out of a stack, we remove the item at the top of the stack and return it to the user.
- After removing the item, the next item becomes the top of the stack.
- Till we reach the last item of the stack for deleting, the stack must be set to empty state after all the items are popped out or deleted from the stack.
Stack Top Operation
In stack top, we return the data at the top of the stack without deleting the data from the stack.
- Here, the item at the top of the stack is copied.
- Then the copied data is returned to the user but it is not deleted.
- This operation is used to read the stack top.
- Stack top operation can result in data underflow condition in a stack.
Stack Linked List Implementation
Stack can be implemented using more than one data structure. We will discuss how we can implement linked list stack approach.
We need two different structures to implement linked list stack, i.e. a head and a data node.
We will discuss each of these parts further with the help of an illustrated diagram given below.
Stack Head
Stack head contains the metadata which means the data about the data. The data structure holds the data and a pointer that points to the next node of the stack.
- The stack head works with two basic attributes, i.e. a top pointer and a count of the number of elements in the stack.
- Many other attributes can be included in the stack head, such as to record the time of stack creation, etc.
Stack Data Node
Stack data node is the rest of the data structure left apart from the stack head.
- The stack data node seems to be any linked list node, but the only difference is that the data stored in the stack is determined by the application.
- The data node contains the link pointer to other data nodes, this makes it a self-referential data structure.
- In a self-referential data structure, the instance of the structure is linked to another instance of the same structure.
Stack Algorithms
These are some basic algorithms to perform the Stack Operations in Data Structure. Although, any other operation can also be carried out and added to the data structure.
Empty Stack
This operation is carried out to implement the programming concept of data hiding.
- It is not used when the entire program has the access to the stack head node.
- But in cases where stack is implemented in separate programs which has to linked with other programs, then the calling program does not have the access to the stack head node.
- In such situations it becomes a must to specify whether the stack is empty or not before putting it into use.
Empty Stack Algorithm
Algorithm Empty_Stack(stack) 1 if (stack count is 0) 1 return true 2 else 1 return false 3 end if end Empty_Stack
Full Stack
Similarly, this operation is also used in the programming concept of data hiding.
For some languages it can be difficult to implement this operation.
Full Stack Algorithm
Algorithm Full_Stack(stack) 1 if (memory not available) 1 return true 2 else 1 return false 3 end if end Full_Stack
- Here, the algorithm determines whether the stack is full or not and returns a Boolean value if it is full.
- stack is the metadata in the above algorithm to a valid stack.
- After the algorithm executes it returns status check.
- If the stack is full, it returns true, and if it is not full, it returns false.
Destroy Stack
This operation deletes or detroys all the data that are present inside the stack. Although after the termination of the program, the stack is automatically cleared but we can do it manually using the destroy stack operation.
Destroy Stack Algorithm
Algorithm Destroy_Stack (stack)
1 if (stack not empty)
1 loop (stack not empty)
1 delete top node
2 end loop
2 end if
3 delete stack head
end Destroy_Stack
- Here, the above algorithm deletes all the data of the stack.
- The nodes are relesed back into the dynamic memory.
- stack is passed by reference.
- After the algorithm finishes, it empties the stack and deletes all the nodes.
Program example to demonstrate the implementation of Stack Operations
Code:
#include <stdio.h>
#include <stdlib.h>
void push();
void pop();
void display();
struct node
{
int val;
struct node *next;
};
struct node *head;
void main ()
{
int n=0;
while(n != 4)
{
printf("\nEnter the number corrosponding to the function you want to do.\n");
printf("\n1.Push operation\n2.Pop operation\n3.Show stack\n4.Exit");
printf("\nEnter the operation you want to do: \n");
scanf("%d",&n);
switch(n)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("Exited successfully.");
break;
}
default:
{
printf("Enter a valid number again.");
}
};
}
}
void push ()
{
int val;
struct node *ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("Push operation failed.");
}
else
{
printf("Enter a value: ");
scanf("%d",&val);
if(head==NULL)
{
ptr->val = val;
ptr -> next = NULL;
head=ptr;
}
else
{
ptr->val = val;
ptr->next = head;
head=ptr;
}
printf("Item pushed successfully.");
}
}
void pop()
{
int item;
struct node *ptr;
if (head == NULL)
{
printf("Underflow condition.");
}
else
{
item = head->val;
ptr = head;
head = head->next;
free(ptr);
printf("Item popped successfully.");
}
}
void display()
{
int i;
struct node *ptr;
ptr=head;
if(ptr == NULL)
{
printf("Empty Stack Found.\n");
}
else
{
printf("Stack elements: \n");
while(ptr!=NULL)
{
printf("%d\n",ptr->val);
ptr = ptr->next;
}
}
}
In the next section of the tutorial, we will discuss the use of Queue in Data Structure and some important Queue Operations as well as its implementation in programs that will be used thoroughly in this Data Structure tutorial.
