Stack ADT

Introduction:

• A stack is an ordered list in which all insertions and deletions are made at one end called the top.
• In stack always the last item to be put in to the stack is the first item to be removed. So stack is a Last In First Out or LIFO data structure.
• Push and Pop are the operations that are provide for insertion of an element in to the stack and the removal of an element from the stack.

                                               |      |
                                               |  E  | <-----Top
                                               |  D  |
                                               |  C  |
                                               |  B  |
                                               |_A_|
                                             
                                                Stack 

Basic Stack Operations:

• A stack is a container which provides exactly one method push for putting objects into the container and one method pop for taking objects out of the container.
• Push---> adds a new node
• Pop---->removes a node

            |    |           |      |

            |    |           |      |
            |    |           |      | 
            |    |   top--|___|
    top--|__|           |_A_| 

       Empty Stack Push(A)

Implementation of stack:

       A stack is basically a list. so it can be implemented by using an array or by using a linked list.

1.Linked List Implementation of stack

• The implementation of stack uses a Singly linked list.
• Linked List is a dynamic data structure. So collection of data can be used which are variable in size and structure.The program executes can grow and shrink to accommodate the data being stored. 
• The push operation is performed by inserting the element at the front of the list
• The pop operation is performed by deleting the element at the front of the list 

Drawback of Linked List implementation

• All the operations take constant time
• Calls to malloc and free are expensive especially in comparison to the pointer manipulation routines.   

2.Array implementation of stack :

• A simple way of implementing the stack uses an array. 
• when a stack is implemented using array there is no need for pointers and the push and pop operations are realized by using the operations available on an array.
• Array is a static data structure so the collection of data must be fixed in size.  
• The only problem with this implementation is array size must be specified initially. 

Limitation of Array Implementation:

• The stack cannot grow and shrink dynamically as per the requirement. 

A simple C program to demonstrate Stack operations:

#include<stdio.h>
#define SIZE 3
int top=-1,data;
int stack[SIZE];

void push(int data)
{
    if(top==SIZE-1)
    {
        printf("Stack is full\n");
        return;
    }
    else
    {
        top=top+1;
        stack[top]=data;
        printf("Item added\n");
    }
}

void pop()
{
    if(top<0)
    {
        printf("stack is empty\n");
        return;
    }
    else
    {
        data=stack[top];
        top=top-1;
        printf("Popped element is=%d\n",data);
    }
}        

int main()
{
    push(1);
    push(2);
    push(3);
    push(4);
    pop();
    pop();
    pop();
    pop();
    return;
} 

Output:
./a.out
Item added
Item added
Item added
Stack is full
Popped element is=3
Popped element is=2
Popped element is=1
stack is empty

Applications of Stacks:

      1.  Direct Applications

• Page visited history in a Web browser
• Undo sequence in a text editor 

     2.   Indirect Applications 

• Function call--As processor executes a program, when a function call is made,the called function must know how to return back to the program, so the current address of program execution is pushed on to stack.once the function is finished the address that was saved is removed from the stack and execution of the program resumes. If a series of function calls occur the successive return values are pushed on to the stack in LIFO order so that each function can return back to calling program. Stacks support recursive function calls.
• Balancing Symbols--while compiling any program the compilers  check for syntax errors.if one symbol(missing brace or comment starter)is missing then the compiler will stop compiling.so we need to checks whether everything is balanced.(ie) every right brace,bracket and parenthesis must correspond to their left counterparts. using a stack we read all the characters until end of file if the character is an open anything push it on to the stack. If it is close anything then if the stack is empty report an error.otherwise pop the stack. If the symbol popped is not the corresponding opening symbol then report an error.It is the fast way to find an error.
• Expression evaluation.  
• Reversing a string--Simply push each letter of the string on to the stack then pop them back.now the string is reversed

         Example:         STACK---->KCATS