Stack Data Structure

Stack is an abstract data type with a bounded capacity.

Stack is a LIFO(Last in First out) structure or we can say FILO(First in Last out).
Both insertion and removal are allowed only at the top of Stack.

push() function is used to insert new elements into the top of stack.
pop() function is used to remove an element from the top of stack (only element that can be removed is the element that is at the top of the Stack).

Both hardware and software stacks have been used to support 4 major computing areas:

1. expression evaluation

2. subroutine return address storage
   With the introduction of recursion as a desirable language feature, a means of storing the return
   address of a subroutine in dynamically allocated storage was required.The solution to the recursion problem is to use a
   stack for storing the subroutine return address.
   Modern machines usually have some sort of hardware support for a return address stack.

3. dynamically allocated local variable storage
   Another problem that arises when using recursion, (the possibility of multiple uses of the same code by different threads of control) is the management of local variables.
   The local variable stack not only allows recursion, but it can also save memory.
   With a local variable stack, space on the stack is reused as subroutines are called and the stack depth increases and decreases.

4. subroutine parameter passing

NOTE: 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:

A stack can be easily implemented either through an array or a linked list.

Array:
An array can be used to implement a (bounded) stack.
The first element (usually in array[0] ) is the bottom.
The program must keep track of the size of the stack, using a variable top that records the number of items pushed so far, therefore pointing to the place in the array where the next element is to be inserted.

Linked list:
Considered as a linear data structure, or more abstractly a sequential collection, the push and pop operations occur only at one end of the structure, referred to as the top of the stack. This makes it possible to implement a stack as a singly linked list and a pointer to the top element. A stack is then a pointer to the "head" of the list, with perhaps a counter to keep track of the size of the list.