A stack is a linear data structure in which the insertion and deletion operations can be performed at one end called top of the stack. A stack is also called a Last In First Out (LIFO) data structure. Remember Array and Linked list where we can add or remove the data from both the end (front or back). Unlike these data structures, stack allows the user to access only one end. Figure 1 visualizes a stack with 5 items.
As we can see in Figure 1, we can not access item 1. The bottom is closed. Top of the stack is the only place where we have access to. We can only access item 5 which is at the top of the stack. In order to get to the item 4, we need to remove 5, to get to item 3, we need to remove 4 and 5 and so on. In all the operations we do in the stack, we manipulate the top of the stack in some way. Based on how we use the top, there are three operations we can do on the stack.
Push: We insert a new item at the top of the stack.
Pop: We remove the item from the top of the stack.
Top: We read the value of the item at the top of the stack.
Now I am going to explain all these operations in detail.
Operations on stack
Push
A new item can be pushed into a stack using the following steps.
Check if the stack is full. If it is, then you can not insert the item. Raise “Stack Overflow” error.
If the stack is not full, insert the item at the top of the stack.
Make this item a new top of the stack.
Pop
An item on the top of the stack can be removed (popped) using following steps.
Check if the stack is empty. If it is, then you can not remove the item. Raise “Stack Underflow” error.
If the stack is not empty, remove the item at the top of the stack.
Update the top of the stack.
Top (or peek)
The top operation returns the item at the top of the stack. Don’t be confused this operation with the pop operation. The pop operation removes the top item whereas the top operation only reads the value of the top item. As in the pop operation, we need to check if the stack is empty before reading the value.
Complexities
The complexities of all the operations are tabulated below.
Operation
Complexity
Push
O(1)
Pop
O(1)
Top (Peek)
O(1)
Applications of a stack
A stack is widely used in many areas of computer science. Some of the applications are listed below.
Many algorithms like Depth First Search, Graham Scan, Monotone Triangulation, etc.
Expressions evaluation and syntax parsing.
Series of functions are stored in a stack by a compiler.
Backtracking
Undo features, back and forth features etc.
Implementation
A stack can be implemented using arrays as well as linked lists.
Implementation using array
Implementation of the stack using an array in C, C++, and Java is given below.
// global variables intstack[MAX_SIZE]; int top = -1;
// inserts item at the top of the stack voidpush(int item){ // check for overflow if (top >= MAX_SIZE - 1) { printf("%s\n", "Error: Can not push item. Stack Overflow"); return; }
// insert the item and update the top stack[top + 1] = item; top = top + 1; }
// removes an item from the top of the stack intpop(){ // check for underflow if (top <= -1) { printf("%s\n", "Error: Can not pop item. Stack Underflow"); return-999999; }
top = top - 1; returnstack[top + 1]; }
// returns the item at the top intpeek(){ // check for underflow if (top <= -1) { printf("%s\n", "Error: Can not read item. Stack Underflow"); return - 999999; }
classMyStack { private: conststaticint MAX_SIZE = 10; intstack[MAX_SIZE]; int top; public: MyStack() { top = -1; }
// inserts item at the top of the stack voidpush(int item){ // check for overflow if (top >= MAX_SIZE - 1) { cout<<"Error: Can not push item. Stack Overflow"<<endl; return; }
// insert the item and update the top stack[top + 1] = item; top = top + 1; }
// removes item from the top of the stack intpop(){ // check for underflow if (top <= -1) { cout<<"Error: Can not pop item. Stack Underflow"<<endl; return-999999; }
top = top - 1; returnstack[top + 1]; }
// returns the item at the top intpeek(){ // check for underflow if (top <= -1) { cout<<"Error: Can not read item. Stack Underflow"<<endl; return - 999999; }
// inserts item at the top of the stack publicvoidpush(int item){ // check for overflow if (top >= MAX_SIZE - 1) { System.out.println("Error: Can not push item. Stack Overflow"); return; }
// insert the item and update the top stack[top + 1] = item; top = top + 1; }
// removes an item from the top of the stack publicintpop(){ // check for underflow if (top <= -1) { System.out.println("Error: Can not pop item. Stack Underflow"); return -999999; }
top = top - 1; return stack[top + 1]; }
// returns the item at the top publicintpeek(){ // check for underflow if (top <= -1) { System.out.println("Error: Can not read item. Stack Underflow"); return - 999999; }