Stack Data Structure: Definition, Operations, and Applications

Key Operations on a Stack:

1. Push:

   • Adds an element to the top of the stack.

2. Pop:

   • Removes the element from the top of the stack.

3. Peek or Top:

   • Returns the element at the top of the stack without removing it.

4. isEmpty:

   • Checks if the stack is empty.

A stack is a list with the restriction that inserts and deletes can be performed in only one position, namely the end of the list called the top. The fundamental operations on a stack are push, which is equivalent to an insert, and pop, which deletes the most recently inserted element. The most recently inserted element can be examined prior to performing a pop by use of the top routine. A pop or top on an empty stack is generally considered an error in the stack ADT. On the other hand, running out of space when performing a push is an implementation error but not an ADT error.

Stacks are sometimes known as LIFO (last in, first out) lists. The model depicted in Figure below signifies only that pushes are input operations and pops and tops are output. The usual operations to make empty stacks and test for emptiness are part of the repertoire, but essentially all that you can do to a stack is push and pop.

Important Points for the PUSH operation

1. Check if the stack is full or not.
2. If the stack is full, then print error of overflow and exit the program.
3. If the stack is not full, then increment the top and add the element.

Important Points for POP operation

1. Check if the stack is empty or not.
2. If the stack is empty, then print error of underflow and exit the program.
3. If the stack is not empty, then print the element at the top and decrement the top.

Stack is an abstract data type with a bounded(predefined) capacity. It is a simple data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack and the only element that can be removed is the element that is at the top of the stack, just like a pile of objects.

Basic features of Stack

1. Stack is an ordered list of similar data type.
2. Stack is a LIFO(Last in First out) structure or we can say FILO(First in Last out).
3. push() function is used to insert new elements into the Stack and pop() function is used to remove an element from the stack. Both insertion and removal are allowed at only one end of Stack called Top.
4. Stack is said to be in Overflow state when it is completely full and is said to be in Underflow state if it is completely empty.
5. Whenever an element is pushed into stack, it must be checked whether the stack is full or not.
6. Whenever an element is popped form stack, it must be checked whether the stack is empty or not.
7. We can implement the stack ADT either with array or linked list.

Applications of stack:

• Stacks are used in the conversion of expression from infix notation to postfix and prefix notation.
• Stacks are used for evaluation of infix and postfix forms.
• Stacks are used in tree traversal techniques.
• Recursive functions are implemented using stacks. The copies of variables at each level of recursion are stored in stack.
• Compilers use stacks in syntax analysis phase to check whether a particular statement in a program is syntactically correct or not.
• Computers use stack during interrupts and function calls. The information regarding actual parameters return values, return addresses and machine status is stored in stack.
• Stacks are used in depth-first search of a graph.