Stack

Stack is an abstract data type with a 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.

Implementation of Stack Data Structure

Stack can be easily implemented using an Array or a Linked List. Arrays are quick, but are limited in size and Linked List requires overhead to allocate, link, unlink, and deallocate, but is not limited in size. Here we will implement Stack using array.

Applications

• The simplest application of a stack is to reverse a word. You push a given word to stack — letter by letter — and then pop letters from the stack.
• Another application is an “undo” mechanism in text editors; this operation is accomplished by keeping all text changes in a stack.
• Backtracking. This is a process when you need to access the most recent data element in a series of elements. Think of a labyrinth or maze — how do you find a way from an entrance to an exit?
• Once you reach a dead end, you must backtrack. But backtrack to where? to the previous choice point. Therefore, at each choice point you store on a stack all possible choices. Then backtracking simply means popping a next choice from the stack.
• Language processing: space for parameters and local variables is created internally using a stack, compiler’s syntax check for matching braces is implemented by using stack.
• In compilers — Compilers use the stack to calculate the value of expressions like 2 + 4 / 5 * (7 - 9) by converting the expression to prefix or postfix form.
• In browsers — The back button in a browser…