Introduction
Stack is one of the memory allocation techniques having a concept of linear data structure where operations like insertion and deletion were performed to store and remove the data item from one end only and that to be from the Top. In Stack, for insertion and deletion, the terminology used is Push and Pop. Push means Insert and Pop means Remove/Delete data elements. Data is removed only by the principle of LIFO, which means Last In First Out. The Element inserted at last will be removed first. For this reason, a stack is called a LIFO structure: last in/first out. In Stack, there are two basic cases such as Underflow and Overflow which are generally considered exceptions. Underflow occurs when we try to pop out any data element from an empty Stack and when Stack is full and we try to Push an element then Overflow occurs.
Possible cases on Stack: Push, Pop, Overflow and Underflow
Consider an example of a pile of plates kept in a wedding buffet. The plate that was added at the last is removed first and that is from the top of the pile. Similarly in a stack, operations are performed on one end only.
Stack operations
- Push (int data): Inserts data onto the stack.
- int Pop(): Removes and returns the last inserted element from the stack.
- int Top(): Returns the last inserted element without removing it.
- int Size(): Returns the number of elements stored in the stack.
- int IsEmptyStack(): Indicates whether any elements are stored in the stack or not.
- int IsFullStack(): Indicates whether the stack is full or not
push() Operation
Let’s start with the insert operation. The push operation refers to adding a new element to the top of the stack.
if TOP = MAX-1
return “Overflow”
endif
top = top + 1
stack[top] = item
end
Consider inserting A, B, and C onto an empty stack as an example. We begin by pushing A and the top points at A. The top is then updated to point at B when we push B onto the stack. Finally, when we add C to the stack, the top of the stack is updated to point to C:
pop() :
Second, consider the delete operation. The pop operation refers to removing an element from the top of the stack.
If TOP = -1
return “Underflow”
endif
item=Stack[Top]
top=top-1
return Item
end
peek() :
Lastly, the peek operation retrieves the element at the top of the stack without removing it.
int peek() {
if ( isEmpty() == True ) {
print( “Stack is empty!” )
return -1
}
else
return stack[top]
}
isFull() :
It determines whether the stack is complete.
isEmpty() :
Finally, consider the isEmpty operation. It determines whether the stack is empty.
bool isEmpty()
{
if ( top == -1 )
return True
else
return False
}
Application of the Stack
- A Stack can be used for evaluating expressions consisting of operands and operators.
- Stacks can be used for Backtracking, i.e., to check parenthesis matching in an expression.
- It can be used for systematic Memory Management.
- used in the “undo” mechanism in a text editor.
- used in the Reversal of String.
- Checking Validity of any Expression Containing Nested Parenthesis.
- Used in Function Call.
- Conversion of Infix expression to postfix form.
- Evaluation of Postfix Expression.
Advantages of Stack
- A Stack helps to manage the data in the ‘Last in First out’ method.
- When the variable is not used outside the function in any program, the Stack can be used.
- It allows you to control and handle memory allocation and deallocation.
- It helps to automatically clean up the objects.
Disadvantages of Stack
- It is difficult in Stack to create many objects as it increases the risk of the Stack overflow.
- It has very limited memory.
- In Stack, random access is not possible.
