All That You Need To Know About Stack
Author: Kanika Joshi
A stack is a linear data structure that works upon the LIFO (Last in First out) or FILO(First) approach, this means the element which is inserted at last in the stack will be the first one to be removed from the stack. Stack is an Abstract Data Type, and it behaves similar to a real-world stack, like a pile of plates kept one over another, a deck of cards, etc.
In this article, we are going to discuss the stack, types of the stack, operations performed over the stack, working of the stack, etc.
The stack data structure can be visualized as a pile of plates where one plate is placed over another plate.
From the above image, we can understand the stack data structure easily, as if we have to place a new plate in the pile, we will keep it at the top of the stack, whereas if we have to remove the plate, the plate at the top of the pile will be removed first. So, this is working on the principle of LIFO i.e. Last in First Out.
You can also explore – All You Need to Know About Algorithms and Data Structures
Principle of Stack:
In stack, there are two fundamental operations, PUSH and POP. When an item is inserted into the stack the PUSH operation is performed whereas when an item is removed from the stack the POP operation is performed. In a stack, these operations are used while following the LIFO (Last in First out) or FILO (First In Last Out) principle.
Let’s Understand with the help of an example:
In the above image, A is the first item to be pushed or inserted into the stack, then we insert B and at last C. The C was the last item to be inserted and when the POP operation was applied, C was the first to be removed from the top of the stack.
Note: In stack, all the operations are performed at TOP of the stack.
Best-suited Data Structures and Algorithms courses for you
Learn Data Structures and Algorithms with these high-rated online courses
Operations on Stack:
The basic operations that are performed over a stack are as follows:
Push:
To insert an item into the top of the stack. If the stack is full, so no item can be inserted into the stack, then such a condition is known as Overflow.
Algorithm:
- Start
- Check whether the stack is full.
- If Full, then return.
- Else, increment top.
- Insert a new element at the position pointed by the top.
- End
PseudoCode:
start if (stack== full) return(); else top++; stack[top]= value;end
Pop:
To remove an item from the top of the stack. So items are removed in reverse order as they were pushed. If the stack is empty, no items can be popped out of the stack, so such a condition is known as Underflow.
Algorithm:
- Start
- Check whether the stack is empty.
- If empty, then return.
- Else, access the topmost item.
- Decrement the top
- End
PseudoCode:
start if (stack== empty) return(); else t= top; top--; return(t);end
Peek:
Return the top of the stack without removing it.
Algorithm:
start return stack(top);End
IsEmpty:
Checking whether the stack is empty or not.
Algorithm:
start if (top<1) return true; else return false;end
IsFull:
Checking whether the stack is full or not.
Algorithm:
start if (top==n) // n is the capacity of the stack return true; else return false;end
Working of Stack:
The working of basic operations (PUSH and POP) is as follows:
- The TOP of the stack is a pointer that is used to keep track of the top item of the stack.
- When a stack is initialized, Top’s value is -1, which means Top<1, hence the stack is empty.
- Whenever an item is inserted Top’s value is incremented by 1, and the item is placed at the place where pointer Top is Pointing.
- Whenever an item is Popped out of the stack, the value of that item is stored in some variable, and Top’s value is decremented by 1.
- Before performing the PUSH operation, we always check whether the stack is full or not by using the isFull operation.
- Before performing a POP operation, we always check whether the stack is empty or not by using the isEmpty operation.
Types of Stack:
Mainly, stacks are of two types:
Register Stack: Register stack is commonly a memory element and can manage a small amount of data. Its height is always limited and less than the memory.
Memory Stack: A memory stack can manage a large size of data, the capacity of the memory stack is flexible, and can have large amounts of memory.
Must explore – 8 Most Important Data Structures Every Programmer Must Know
Implementation of Stack:
The stack can be implemented using:
- Array
- Linked List
Implementation with arrays is quite easy and fast, but arrays are limited in size. Whereas, implementation with a linked list has an overhead of allocating, linking, unlinking, and deallocating, linked lists are not limited in size.
Implementation using Array:
The stack will be implemented using an array, and all the operations of the stack will be performed using an array.
Let’s understand this by an example, consider the following data item: 10, 20, 30, 40 Push them into the stack and Pop 40, 30 from the stack.
Implementation using Linked List:
The stack will be implemented using a linked list, and all the operations of the stack will be performed using a linked list. While implementing a stack using a linked list, the top will point to every newly inserted element, and while removing any element top must point to that element
Let’s take the same example, consider the following data item: 10, 20, 30, 40 Push them into the stack and Pop 40, 30 from the stack.
Applications of Stack:
The stack data structure has numerous applications, some of them are as follows:
- It is used in Infix to Postfix or Infix to Prefix conversion.
- It is used in Balancing symbols.
- Forward and Backward feature of the Web browser.
- Undo-Redo feature.
- Used in algorithms like Tower of Hanoi.
- Used in Backtracking
- For String reversal
- For memory management
Time Complexity of Stack
The Time Complexity of different operations of the stack is as follows:
Push Operation:
- Best Case: O(1)
- Average Case: O(1)
- Worst Case: O(N), where N is the number of items in the stack
- Space Complexity: O(1)
Pop Operation:
- Best Case: O(1)
- Average Case: O(1)
- Worst Case: O(1)
- Space Complexity: O(1)
Peek Operation:
- Best Case: O(1)
- Average Case: O(1)
- Worst Case: O(1)
- Space Complexity: O(1)
isFull operation:
- Best Case: O(1)
- Average Case: O(1)
- Worst Case: O(1)
- Space Complexity: O(1)
isEmpty operation:
- Best Case: O(1)
- Average Case: O(1)
- Worst Case: O(1)
- Space Complexity: O(1)
This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio
Top Picks & New Arrivals
