A stack is a linear list where insertion and deletion can perform only at one end. and the end where we perform the operation is called the top of the stack. It uses Last-In-First-Out (LIFO) functionality means the item that inserts last will out first.
In the technical form insertion operation in the stack is called push and the deletion operation is called pop operation.
What is the Stack – definition?
A stack is an ordered collection of items in which we can insert a new item or can delete an existing item only from one end called the top of the stack.
The stack has a single end called the top from only where we can delete or insert new data so when a new item is put on the top of the stack then the top of the stack moves upward to correspond to the new highest element or if an item is deleted from the top of the stack then, in this case, the top of the stack moves downward to the corresponding item. we can decide which end of the linear list will become the top of the stack or at which end items are added or deleted.
sometimes stack is also called a pushdown list because of the push operation which adds elements to the stack. one thing we also need to consider while using the stack is that there is no upper limit on the number of items that can be allowed to insert in the stack. but if a stack contains only one item and then we pop the element from the stack then the stack will be left with no elements. so now the pop operation cannot be applied to the empty stack because the stack has no element.
So before deleting or applying the pop operation to the stack we always need to check if the stack is empty or not. so we kept a variable and check for the stack if it is empty or not. if the stack is empty then we do not use the pop operation.
And if the stack has not any item and if we use the pop operation then this will result in an attempt to access an item from an empty stack. this situation is called underflow.
Implementation of Stack
we can implement a stack using the array or by using the linked list.
Implementing stack using an array
To implement a stack we need a variable named the top that always holds the index of the top element of the stack and an array to hold the elements of the stack. let’s say we have an array of integer types and it can store a maximum of 10 elements. so the maximum stack size is 10 and can only store a maximum of 10 elements.
we need to define a data type called stack using the structure and need to define the first element as a top that will be used as an index to the top element and a variable MAXSIZE of integer type that will hold the elements of the stack.
Implementing stack using linked list
Implementing a stack using the linked list is called a linked stack. we first need to define a data type named stack using the structure with two variables called info and next. info variable will hold the data of the stack and the next variable holds the address of the element. and at the last, we declare a pointer variable called the top of the type stack that will hold the values of the stack.
Create an empty stack
To create an empty stack we need to initialize a stack using the empty linked list. set the top pointer variable to NULL.
To push or insert an element into the stack we need to insert the element at the first position of the array or linked list.
To pop an element or delete an element to the stack we need to delete/remove the element from the beginning of the linked list.
Check Underflow condition
To check for the underflow condition we need to check if the linked list or array is empty or not.
Check overflow condition
A linked list does not have any end to insert an element. so this condition does not occur in the terms of linked list implementation. but while implementing using the array we need to consider this condition.
Dispose of stack
Disposal of a stack means releasing the memory occupied by the stack when the data is not there.