Data Structures are the programmatic way of storing data so that data can be used efficiently. Almost every enterprise application uses various types of data structures in one or the other way. There are many types of data structures frequently used in programs depending on the requirement. Stack is one of the most popular and widely known data structures in computer science, and one of the easiest to learn and understand.
What is Stack?
A stack is a linear data structure that can be logically thought of physical stack or a pile. The stack operations find a place in several applications. A stack can be illustrated by thinking of your data set as a stack of books where you can only take an item from the top and also can place an item at the top only.
Stack is a linear data structure where the data is arranged in such a way that you can insert the data only at the top of it.
In a stack, the data that is inserted first is taken out at the last and the data that is inserted last is taken out first. That’s the reason stack is also called LIFO list (Last In First Out).
3 Basic Operations in Stacks
Mainly the following three basic operations are performed in the stack:
Push: Adds an item in the stack. If the stack is full, then it is said to be an overflow condition.
Pop: Removes an item from the stack. The items are popped in the revered order in which they are pushed. If the stack is empty, then it is said to be an underflow condition.
Peek: Returns the top element of the stack.
Stack Implementation
Stack is a very useful concept that a programmer could use to her/his benefit. Have you ever implemented it in your code yet? It’s not as difficult as you might think. Let’s walk through its properties and implement them in code.
A stack can be implemented in two ways:
- Using Array
- Using Linked List
Implementing Stack Using Array
An array is one of the simplest containers offering random access to users based on indexes. But we cannot access any element of the stack at any position. That’s why we need to set an index at the top and then access only the element at the index top.
int stack[10];
int top = -1;Here, 10 is a pre-defined capacity of the stack. You can write a code for stack overflow error if a user tries to exceed this capacity.
The second thing to note here is that top = -1, which means the stack is empty (since the index in an array starts from 0. Index 0 means position 1).
Stack is implemented by using the following code:
struct stack
{
int arr[capacity];
int top;
}
PUSH Operation
To insert a new element is inserted into the stack, the following steps are performed:
- The value of top is incremented by 1.
- The value is placed at the top.
The code for push operation will be:
void push(int item)
{
if ( top == capacity - 1 )
cout << "Stack overflow!" ;
else
{
top = top + 1;
arr[top+1] = item;
}
}
POP Operation
To remove an element from the stack, the following steps are performed
- The top element is removed.
- The value top is decreased by 1.
The code for pop operation will be:
void pop()
{
if ( top == -1 )
cout << "Stack is empty!";
else
cout << arr[top];
top = top - 1
;
}
PEEK Operation
The peek operation accesses (peeks) the element at the top of the stack. The code for peek operation will be:
int peek()
{
if ( top == -1 )
{
cout << "Stack is empty!";
}
else
return arr[top];
}
Implementing Stack Using Linked List
In a linked list there are two ends – head and tail. While implementing a stack using a linked list, the head is taken as the top of the stack.
First of all, a linked list is implemented using the following code:
struct ListNode{
int val;
ListNode *next;
}
Now, this linked list is used to implement the stack.
struct Stack{
int capacity;
struct ListNode{
int val;
ListNode *next;
}
}
PUSH Operation
The same properties hold as above with an added benefit that we need not worry about the stack being full. The code for push operation will be:
void push(int item)
{
ListNode temp = ListNode(item)
;
temp->next = head
;
head = temp
;
}
POP Operation
Since the top is represented by the head in this implementation. The basic idea to implement the pop operation is to make the second element as the head. The code for push operation will be:
void pop()
{
if ( head == NULL )
cout << "Stack is empty!";
else
head = head->next;
}
You may be required to deallocate the popped node to avoid memory leaks.
PEEK Operation
The implementation of peek operation using a linked list is straightforward. The code for peek operation will be:
int peek()
{
if ( head == NULL )
{
cout << "Stack is empty!";
return -1;
}
else
return head->val;
}
Applications of Stack Data Structure
Following are a few of the applications where stacks are used:
Balancing of symbols: Stack is used for balancing a symbol. For example, we have the following program:
int main()
{
cout<<"Hello";
cout<<"World";
} As we know, each program has opening and closing braces; when the opening braces come, we push the braces in a stack, and when the closing braces appear, we pop the opening braces from the stack. Therefore, the net value comes out to be zero. If any symbol is left in the stack, it means that some syntax occurs in a program.
String reversal: Stack is also used for reversing a string. For example, we want to reverse a “CodingHero” string, so we can achieve this with the help of a stack. First, we push all the characters of the string in a stack until we reach the null character. After pushing all the characters, we start taking out the character one by one until we reach the bottom of the stack.
UNDO/REDO: It can also be used for performing UNDO/REDO operations. For example, we have an editor in which we write ‘a’, then ‘b’, and then ‘c’; therefore, the text written in an editor is abc. So, there are three states, a, ab, and abc, which are stored in a stack. There would be two stacks in which one stack shows UNDO state, and the other shows REDO state. If we want to perform UNDO operation and want to achieve an ‘ab’ state, then we implement the pop operation.
Recursion: The recursion means that the function is calling itself again. To maintain the previous states, the compiler creates a system stack in which all the previous records of the function are maintained.
DFS(Depth First Search): This search is implemented on a Graph, and Graph uses the stack data structure.
Backtracking: Suppose we have to create a path to solve a maze problem. If we are moving in a particular path, and we realize that we come on the wrong way. To come at the beginning of the path to create a new path, we have to use the stack data structure.
Expression conversion: Stack can also be used for expression conversion. This is one of the most important applications of stack. The list of the expression conversion is given below:
Infix to prefix
Infix to postfix
Prefix to infix
Prefix to postfix
Postfix to infix
Memory management: The stack manages the memory. The memory is assigned in the contiguous memory blocks. The memory is known as stack memory as all the variables are assigned in a function call stack memory. The memory size assigned to the program is known to the compiler. When the function is created, all its variables are assigned to the stack memory. When the function completed its execution, all the variables assigned in the stack are released.
Conclusion: As with any abstract data type, a stack can be implemented with a variety of data structures, such as a linked list or an array. A stack has a variety of applications such as reversing the order of elements, evaluating polish strings, etc.
