Complete Guide To Stacks
Stack is a linear data structure that follows LIFO (Last In, First Out) or FILO (First In, Last Out) principle. It is an abstract data type of predefined capacity in which elements can be removed and added in a specific order.
Insertion and deletion happen at the same end in stack data structure.
Visualise stack as a pile of plates in a restaurant.
Only the topmost plate is accessible.
To access any other plate, the plates on top of that plate need to be removed first.
The plate at the bottom of the pile can only be removed at the last after all plates on top of it have been removed.
Array Implementation of Stacks
Array can be used to implement stack data structure. Only one element of a stack can be accessed at a time. This element is located at the index top.
class Stack{
int arr[50]
int size
int top
};
Array can be of any datatype.
Constructor to initialize size and top :
Stack(int n)
{
size = n
top = -1 //denotes that stack is empty
}
Operations on Stacks
Push Operation
Push operation adds an item in the stack. If the stack is full, then it is said to Overflow .
When a new element is inserted on top, the value of top increases by 1
- Check if the stack is full before insertion.
- If it is full, then display error and exit.
- If the stack is not full, then increment the index on adding an element.
3 is added to the stack after push operation
Code
void push()
{
if(top == size-1)// Check if the index is beyond the stack size
{
print(”Stack Overflow")
return
}
top=top+1//Increment the index on adding an element
s[top]=item// Add the element into the stack (array) as pointed by the index }
Pop Operation
Pop operation removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.
- Check if the stack index is beyond the initial index
- Return a value -1 if the stack is empty
- If the stack is not empty, return the topmost element
12 is removed from the top of the stack by performing pop operation
Code
//operation returns the removed element
int pop()
{
if(top== -1) //Check if the stack index is beyond the initial index
{
print(”Empty Stack")
return -1 //Return a value -1 if the stack is empty
}
return s[top--] // Return the topmost element
}
isEmpty
Returns true if stack is empty, else false.
bool isEmpty()
{
if(top==-1)
return true// stack empty
return false
}
Top or peek
Returns top element of stack.
int top()
{
if (top==-1)
{
print( "Stack is empty!")
return -1
}
else
return arr[top]
}
Time Complexities
Operation | Time Complexity |
---|---|
Push | O(1) |
Pop | O(1) |
Top | O(1) |
Search | O(n) |