What is Stack Data Structure?

Stack is a linear data structure that follows a specific order that performs the activities. It's just like a stack of overlapping plates. It works on the Last-In-First-Out (LIFO) principle–the last item to be positioned is the first item to be released. It's an abstract type of data. It is widely used in most languages of programming.It is named stack as it behaves like a real-world stack. For example, a deck of plates.

Working of Stack :

Stack data structure works on LIFO basis. LIFO stands for Last-in-first-out. Here, the element which is inserted at last, is accessed first. In stack terminology, insertion operation is called PUSH operation and removal operation is called POP operation. It has only one pointer TOP that points the last or top most element of Stack. Insertion and Deletion in stack can only be done from top only.

The most significant thing here is the TOP point. At the time of stack initialization, we need to set its value to-1 so we can check if the stack is empty or not by comparing TOP==-1.

Whenever an item is inserted, boost the TOP value by 1 and place the fresh item in the TOP-pointed position.

When removing an element, return the TOPpointed element and reduce its value by 1.

 Before operating push() it is necessary to verify whether the stack is already complete. [ Stack Overflow Condition ] 

Check if the stack is already empty before the pop() procedure. [Condition of stack underflow ]

Stack Operations

Stack is an ADT (Abstract Data structure). We can implement this linear structure using array, linked list or some other way. It is supported in different programming languages like C, C++, Java, C# etc. We can perform following operations in a stack:

Push()

Push() is used to add an element to the top of stack. Before inserting an element into the stack, we must check for stack overflow i.e. whether the stack has space to add an item or its already full.

void push(int data) 
{
if(!isFull()) {
top = top + 1;
stack[top] = data;
} 
else 
{
printf("Stack is already full.\n");
}
}

Pop()

Pop() is used to remove an element from the top of stack. Before popping an element from the stack, we must check for stack underflow i.e. whether the stack is empty or it contain item to remove.

int pop(int data)
{
if(!isempty())
{
data = stack[top];
top = top - 1;
return data;
} 
else 
{
printf("Stack is empty. Nothing to remove.\n");
}
}

IsEmpty()

IsEmpty() operation is used to check whether stack is empty or not. It check out for stack underflow.

int isempty() {
if(top == -1)
return 1;
else
return 0;
}

IsFull()

IsFull() operation is used to check whether stack is full or it has space to add more item. It check out for stack overflow.

int isfull() {
if(top == MAXSIZE)
return 1;
else
return 0;
}

Peek()

Peek() is used to retrieve the value of the top element without removing it. It returns the value of top of the stack element.

int peek() {
return stack[top];
}

Applications of Stack

Through it is a simple data structure and easy to implement, it is beneficial as well. Most common use of this data structure are:

• Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram problem.
• Backtracking, Knight tour problem, rat in a maze, N queen problem and sudoku solver
• Forward and backward feature in web browsers
• In Graph Algorithms like Topological Sorting and Strongly Connected Components
• Infix to Postfix /Prefix conversion
• Balancing of symbols
• Redo-undo features at many places like editors, photoshop.