A stack is a linear data structure in which the insertion of a new element and removal of an existing element takes place at the same end represented as the top of the stack. The stack data structure follows the Last-In, First-Out (LIFO) principle. This means that the last item added to the stack is the first one to be removed. In other words, the most recently pushed item is always at the top of the stack, and it is the one that is accessed and removed first when performing operations on the stack.
The LIFO principle makes stacks particularly useful in scenarios where you need to keep track of elements in a specific order, such as function calls in a program (call stack), undo/redo functionality in applications, and parsing expressions, among other applications in computer science and programming.
In day-to-day life, you may encounter situations that can be analogously related to the stack data structure's Last-In, First-Out (LIFO) principle:
Stacking Dishes: After washing dishes, you might stack them in a cabinet. The last dish you place on top of the stack will be the first one you use the next time you set the table.
Stacking Chairs: When you stack chairs for storage, the chair you stack last is the one you'll need to remove first when you want to use them again.
Stacking Firewood: If you're stacking firewood for a fireplace or wood stove, the last piece of wood you stack is usually the first one you'll grab when you're ready to use it.
These everyday examples demonstrate how the LIFO principle of a stack can be observed in various situations where items are added and removed in a specific order, with the most recently added item being the first to be accessed or used.
Basic Operations on Stack
To make manipulations in a stack, there are certain operations provided to us.
push() to insert an element into the stack
pop() to remove an element from the stack
peek() Returns the top element of the stack.
isEmpty() returns true if the stack is empty else false.
size() returns the size of the stack.
push():
Adds an item to the stack. If the stack is full, then it is said to be an Overflow condition.
Algorithm for push():
Start
Store the element to push into the array
If top is equal to (stackSize - 1 > 1), then go to step 4 else go to step 6
Increment top as top = top+1
Add an element to the position arr[top] = num
Print Stack overflow
void push(int element)
{
if (size - top > 1)
{
top++;
arr[top] = element;
}
else
{
cout << "Stack Overflow" << endl;
}
}
pop():
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.
Algorithm for pop():
Start
Check if top >= 0, then go to step 3 else go to step 4
top--
Print Stack underflow
void pop()
{
if (top >= 0)
{
top--;
}
else
{
cout << "Stack Underflow" << endl;
}
}
top():
Returns the top element of the stack.
Algorithm for top():
Start
Check if top > = 0, then go to step 3 else go to step 4
return arr[top]
Print Stack is empty
int peek()
{
if (top >= 0)
{
return arr[top];
}
else
{
cout << "Stack is empty" << endl;
return -1;
}
}
isEmpty():
Returns true if the stack is empty, else false.
Algorithm for isEmpty():
Start
Check if top == -1, then return true
Else return false
bool isEmpty()
{
if (top == -1)
{
return true;
}
else
{
return false;
}
}
Implementation of Stack
Using C++ STL
#include <iostream> #include <stack> using namespace std; int main(){ // Create a stack of integers stack<int> myStack; // push() operation myStack.push(2); myStack.push(3); // pop() operation myStack.pop(); // top() operation cout << "Printing top element " << myStack.top() << endl; // empty() operation if (myStack.empty()) { cout << "Stack is empty " << endl; } else { cout << "Stack is not empty " << endl; } return 0; }Using Arrays
#include <iostream> using namespace std; class Stack { // properties public: int *arr; int top; int size; // behaviour Stack(int size) { this->size = size; arr = new int[size]; top = -1; } void push(int element) { if (size - top > 1) { top++; arr[top] = element; } else { cout << "Stack Overflow" << endl; } } void pop() { if (top >= 0) { top--; } else { cout << "Stack Underflow" << endl; } } int peek() { if (top >= 0) { return arr[top]; } else { cout << "Stack is empty" << endl; return -1; } } bool isEmpty() { if (top == -1) { return true; } else { return false; } } }; int main(){ Stack st(5); st.push(22); st.push(33); st.push(44); cout << st.peek() << endl; st.pop(); cout << st.peek() << endl; cout << st.isEmpty() << endl; }
We can also implement stack using vectors and linked lists, I will cover that in a letter blog.
Using an array to implement a stack has its own set of advantages and disadvantages:
Advantages:
Efficiency: Array-based stacks provide constant-time (O(1)) complexity for basic stack operations like push and pop. This makes them very efficient for managing elements in a Last-In, First-Out (LIFO) manner.
Simple Implementation: Implementing a stack using an array is straightforward to understand. It requires minimal code, making it an excellent choice for basic stack operations.
Deterministic Memory Allocation: Since arrays have a fixed size when created, using an array for a stack allows for deterministic memory allocation. This can be beneficial in scenarios where memory management needs to be predictable.
Disadvantages:
Fixed Size: One of the most significant limitations of array-based stacks is their fixed size. You need to specify the size of the array when creating it, and it cannot be changed dynamically. If the stack size exceeds the array size, it leads to stack overflow errors.
Wasted Space: If you allocate a large array to accommodate potential stack growth, you might end up wasting memory when the stack doesn't use its full capacity.
Limited Capacity: The stack's capacity is limited to the size of the array, and you cannot add more elements once it's full. This limitation can be problematic if the stack's size is unknown in advance or can vary significantly.
Inefficient Dynamic Resizing: If you want to implement a stack that can grow and shrink dynamically, you'll need to manage this manually by creating a new array with a larger size, copying elements, and deallocating the old array. This process can be computationally expensive.
No Automatic Memory Management: Arrays don't provide automatic memory management. If you allocate more memory than necessary or forget to deallocate memory when it's no longer needed, it can lead to memory leaks.
In summary, array-based stacks are efficient and simple for basic stack operations but have limitations in terms of fixed size, wasted space, and manual memory management. Depending on your specific use case, these advantages and disadvantages should guide your decision on whether to use an array-based stack or consider other data structures like linked lists for more dynamic stack management.
Applications of the stack:
Redo-undo features at many places like editors and photoshops.
Forward and backward features in web browsers
Used in many algorithms like Tower of Hanoi, tree traversals, stock span problems, and histogram problems.
In Graph Algorithms like Topological Sorting and Strongly Connected Components
In Memory management, any modern computer uses a stack as the primary management for a running purpose. Each program that is running in a computer system has its memory allocations
String reversal is also another application of stack.
Application of Stack in real life:
CD/DVD stand.
Stack of books in a bookshop.
Call centre systems.
Undo and Redo mechanism in text editors.
The history of a web browser is stored in the form of a stack.
Call logs, E-mails, and Google photos in any gallery are also stored in the form of a stack.
YouTube downloads and Notifications are also shown in LIFO format(the latest appears first ).
Allocation of memory by an operating system while executing a process.
Advantages of Stack:
Easy implementation: Stack data structure is easy to implement using arrays or linked lists, and its operations are simple to understand and implement.
Efficient memory utilization: Stack uses a contiguous block of memory, making it more efficient in memory utilization as compared to other data structures.
Fast access time: Stack data structure provides fast access time for adding and removing elements as the elements are added and removed from the top of the stack.
Helps in function calls: Stack data structure is used to store function calls and their states, which helps in the efficient implementation of recursive function calls.
Supports backtracking: Stack data structure supports backtracking algorithms, which are used in problem-solving to explore all possible solutions by storing the previous states.
Used in Compiler Design: Stack data structure is used in compiler design for parsing and syntax analysis of programming languages.
Enables undo/redo operations: Stack data structure is used to enable undo and redo operations in various applications like text editors, graphic design tools, and software development environments.
Disadvantages of Stack:
Limited capacity: Stack data structure has a limited capacity as it can only hold a fixed number of elements. If the stack becomes full, adding new elements may result in stack overflow, leading to the loss of data.
No random access: Stack data structure does not allow for random access to its elements, and it only allows for adding and removing elements from the top of the stack. To access an element in the middle of the stack, all the elements above it must be removed.
Memory management: Stack data structure uses a contiguous block of memory, which can result in memory fragmentation if elements are added and removed frequently.
Not suitable for certain applications: Stack data structure is not suitable for applications that require accessing elements in the middle of the stack, like searching or sorting algorithms.
Stack overflow and underflow: Stack data structure can result in stack overflow if too many elements are pushed onto the stack, and it can result in stack underflow if too many elements are popped from the stack.
Recursive function calls limitations: While stack data structure supports recursive function calls, too many recursive function calls can lead to stack overflow, resulting in the termination of the program.
In this comprehensive exploration of the stack data structure and its various aspects, we've uncovered its fundamental principles, everyday analogies, basic operations, and real-world applications. We've also delved into its implementation using C++ STL , array-based and linked-list approaches. Additionally, we've discussed the advantages and limitations of the stack data structure.
Stacks, with their Last-In, First-Out (LIFO) behaviour, play a crucial role in computer science and programming. They are vital for managing function calls, undo/redo functionality, and parsing expressions, among other applications. As we've seen in everyday examples like stacking dishes and chairs, the LIFO principle is not confined to the digital realm; it mirrors our experiences in the physical world.
The stack's basic operations, including push, pop, peek/top, isEmpty, and size, empower developers to efficiently manage data in a specific order. We've explored their algorithms and their roles in ensuring proper stack manipulation.
However, it's important to be mindful of its limitations, such as fixed capacity and lack of random access. Understanding these limitations and choosing the appropriate data structure for specific tasks is key to effective problem-solving.
In summary, stacks are not just abstract data structures; they are a fundamental concept with practical applications in our digital and physical worlds, making them an essential topic for anyone delving into computer science and programming.