Last Updated: 20 January, 2025 6 Mins Read
A stack is a fundamental data structure in computer science used to store collection of elements that follows the Last In, First Out (LIFO) principle, meaning the last element added to the stack is the first one to be removed. Stack is commonly used in programming for tasks such as function call management, expression evaluation, and backtracking algorithms.
In this tutorial, we are going to explore about Stack data structures and their operations, implementation, uses, advantages and disadvantages etc. in details.
A stack is a linear (ordered) data structure used to store and manipulate a collection of data elements. Stack follows the LIFO (Last In First Out) principle, which means the last element added to the stack will be removed first from the stack.
In a stack, insertion and deletion of an element can be done from one end known as the top of the stack.
The stack data structure is commonly used in programming for tasks such as managing function calls, undo/redo functionality in applications, parsing expressions, backtracking algorithms, maintaining browser history, and many more.
The following operations can be performed on a stack data structure:
push() - It performs an insert operation, meaning adding a new element to the top of the stack.
pop() - It performs a delete operation, meaning removing an existing element from the top of the stack.
peek() - It performs a retrieve operation, meaning it returns the element at the top of the stack.
isEmpty() - Checks if the stack is empty.
isFull() - Checks if the stack is full.
Let's understand each operation of the stack data structure in detail.
In Stack, the push operation means to add or insert a new element; if we are doing a push operation, that means we are adding a new element to the stack. Stack stores that new element at the top of the storage and increments the top index by 1.
If the stack is full, then it is said to be in an overflow condition and show the error message.
Algorithm for Push Operation:
Before inserting a new element into the stack, first we will check if the stack is full or not.
If the stack is full (top == capacity - 1), then the stack overflows, and we cannot insert the element into the stack.
else, the value of top will be increased by 1 (top = top + 1), and the new element will be inserted at the top position of the stack.
Once we reach the capacity of the stack, the elements can be inserted into the stack.
Example of push operation in Stack
In Stack, the pop operation means deleting an existing element from the stack. The elements are popped (removed) in the reversed order in which they are pushed (inserted).
If the stack is empty, it is often referred to as an underflow condition.
Algorithm for Pop Operation:
Before performing the pop operation, we will check the stack is not empty.
If the stack is empty (top == -1), then the pop operation will be performed.
else, we store the element at the top; the value of top will be decreased by 1 (top = top - 1) and return the stored top element.
Example of pop operation in Stack
The top or peek operation returns the element at the top of the stack.
Algorithm for Top or Peek Operation:
The top or peek operation cannot be performed on an empty stack, so first of all we will check the stack is not empty.
If the stack is empty (top == -1), we display the message “Stack is empty”.
Else, the element stored at index = top will be returned.
Example of peek or Top operation in Stack
The isEmpty operation is used to check whether the stack is empty or not and returns true if the stack is empty, else false.
Algorithm for isEmpty Operation:
Check for the value of top in the stack.
If (top == -1), that means the stack is empty, so return true.
Else, the stack is not empty, so return false.
Example of isEmpty operation in Stack
The isFull operation is used to check whether the stack is full or not and, as a result, returns a boolean output; if the stack is full, then return true, else false.
Algorithm for isFull Operation:
Check for the value of top in the stack.
If (top == capacity - 1), then the stack is full, so return true.
Else, the stack is not full, so return false.
| Operations | Time Complexity | Space Complexity |
|---|---|---|
| push() | O(1) | O(1) |
| pop() | O(1) | O(1) |
| top() or peek() | O(1) | O(1) |
| isEmpty() | O(1) | O(1) |
| isFull() | O(1) | O(1) |
There are two ways to implement a stack data structure:
Using Array
Using Linked List
In an array-based stack implementation, the push operation is implemented by incrementing the index of the top element by 1 and storing the new element at that index. Whereas in the pop operation, the index of the top element will be decremented by 1 and return the value stored at that index. Read more...
In a linked list-based stack implementation, the push operation is implemented by creating a new node with the new element and setting the next pointer of the current top node to the new node. The pop operation is implemented by setting the next pointer of the current top node to the next node and returning the value of the current top node. Read more...
That's all, guys. I hope this article is helpful for you.
Happy Learning... 😀
Please share this article on social media to help others.
feedback@javabytechie.com