Stack

The stack  is a non-primitive linear data structure in computer science. In a simple way can visualize a pile of books as stack. we can put the book from the TOP
end only and also for removing any book from the pile, we have to first remove the book from the top end only.

Stack in Java or C is an ordered collection of items into which new data items may be added/inserted and from which items may be deleted at only one end, called the top of the stack. As all the addition and deletion in a stack is done from the top of the stack, the last added element will be first removed from the stack. That is why the stack is also called Last-in-First-out (LIFO).

Operations performed in a stack:

PUSH: The process of adding (or inserting) a new element to the top of the stack is called PUSH operation. Pushing an element to a stack will add the new element at the top. After every push operation the top is incremented by one. If the array is full and no new element can be accommodated, then the stack overflow condition occurs. 

POP: The process of deleting (or removing) an element from the top of stack is called POP operation. After every pop operation the stack is decremented by one. If there is no element in the stack and the pop operation is performed then the stack underflow condition occurs. 

IsEmpty: Check if stack is empty

IsFull: Check if stack is full

Peek: Get the value of the top element without removing it

How stack works?

The operations work as follows:

• A pointer called TOP is used to keep track of the top element in the stack.
• When initializing the stack, we set its value to -1 so that we can check if the stack is empty by comparing TOP == -1.
• On pushing an element, we increase the value of TOP and place the new element in the position pointed to by TOP.
• On popping an element, we return the element pointed to by TOP and reduce its value.
• Before pushing, we check if stack is already full
• Before popping, we check if stack is already empty

Stack Implementation:

Stack can be implemented in two ways:

1. Static implementation (using arrays)

2. Dynamic implementation (using pointers)

Static implementation uses arrays to create a stack. Static implementation using arrays is a very simple technique but is not a flexible way, as the size of the stack has to be declared during the program design, because after that, the  size cannot be varied (i.e., increased or decreased). Moreover, static implementation is not an efficient method when resource optimization is concerned (i.e., memory utilization). For example, a stack is implemented with array size 50.

That is before the stack operation begins, memory is allocated for the array of size 50. Now if there are only a few elements (say 30) to be stored in the stack, the rest of the statically allocated memory (in this case 20) will be  wasted, on the other hand if there are number of elements to be stored in the stack (say 60) then we cannot change the size array to increase its capacity.

The above-said limitations can be overcome by dynamically implementing (is also called linked list representation) the stack using pointers.

Stack Using Array and Pointer:

Implementation of stack using arrays is a very simple technique. Algorithm for pushing (or add or insert) a new element at the top of the stack and popping (or delete) an element from the stack is given below.

Algorithm for push:

Suppose STACK[SIZE] is a one dimensional array for implementing the stack, which will hold the data items. TOP

is the pointer that points to the top most element of the stack. Let DATA is the data item to be pushed.

1. If TOP = SIZE – 1, then:

(a) Display “The stack is in overflow condition”

(b) Exit

2. TOP = TOP + 1

3. STACK [TOP] = ITEM

4. Exit

Algorithm for pop:

Suppose STACK[SIZE] is a one dimensional array for implementing the stack, which will hold the data items. TOP

is the pointer that points to the top most element of the stack. DATA is the popped (or deleted) data item from the

top of the stack.

1. If TOP < 0, then

(a) Display “The Stack is empty”

(b) Exit

2. Else remove the Top most element

3. DATA = STACK[TOP]

4. TOP = TOP – 1

5.Exit.

⇒Code for Stack using Array:http://bit.ly/2WHl5Rz

⇒Code for Stack using Pointer :http://bit.ly/2HTYldR

Basic features of Stack

• Stack is an ordered list of similar data type.
• Stack is a LIFO structure. (Last in First out).
• push() function is used to insert new elements into the Stack and pop() function is used to delete an element from the stack. Both insertion and deletion are allowed at only one end of Stack called Top.
• 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.

Applications of Stack

1. Expression evaluation:This study of arithmetic expression evaluation is an example of problem solving where you solve a simpler problem and then transform the actual problem to the simpler one.
2. Backtracking (game playing, finding paths, exhaustive searching):Backtracking is used in algorithms in which there are steps along some path (state) from some starting point to some goal.
3. Memory management, run-time environment for nested language features:Any modern computer environment uses a stack as the primary memory management model for a running program. Whether it's native code (x86, Sun, VAX) or JVM, a stack is at the center of the run-time environment for Java, C++, Ada, FORTRAN, etc.

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.

There are other uses also like : Parsing, Expression Conversion(Infix to Postfix, Postfix to Prefix etc) and many more.