Stack Tutorial using C, C++ programs

What is Stack?

It is type of linear data structure.
It follows LIFO (Last In First Out) property.
It has only one pointer TOP that points the last or top most element of Stack.
Insertion and Deletion in stack can only be done from top only.
Insertion in stack is also known as a PUSH operation.
Deletion from stack is also known as POP operation in stack.

Stack Implementation

Stack implementation using array.
Stack implementation using linked list.

Applications of Stack

Conversion ofpolish notations
There are three types of notations:
> Infix notation - Operator is between the operands : x + y
> Prefix notation - Operator is before the operands : + xy
> Postfix notation - Operator is after the operands : xy +
To reverse a string
A string can be reversed by using stack. The characters of string pushed on to the stack till the end of the string. The characters are popped and displays. Since the end character of string is pushed at the last, it will be printed first.
When function (sub-program) is called
When a function is called, the function is called last will be completed first. It is the property of stack. There is a memory area, specially reserved for this stack.

    /*stack declaration*/
    typedef struct
    {
        int   top;
        int   items[MAX];
    }Stack;

    #define MAX 5

    //Declaration of Stack
    class Stack
    {
	    private:
		    int top;
		    int ele[MAX];
	    public:
		    Stack();
		    int 	isFull();
		    int 	isEmpty();
		    void    push(int item);
		    int     pop(int *item);
    };

Stack representation

Functions and Algorithms

Initialization of stack.
Insertion into stack ( push operation).
Deletion from stack (pop operation).
Check fullness.
Check emptiness.

Algorithms

In stack related algorithms TOP initially point 0, index of elements in stack is start from 1, and index of last element is MAX.

    INIT_STACK (STACK, TOP)

    Algorithm to initialize a stack using array. 
    TOP points to the top-most element of stack.

    1) TOP: = 0;
    2) Exit

Push operation is used to insert an element into stack.

    PUSH_STACK(STACK,TOP,MAX,ITEM)

    Algorithm to push an item into stack.
            
    1) IF TOP = MAX   then
    Print “Stack is full”;
    Exit;
    2) Otherwise
    TOP: = TOP + 1;        /*increment TOP*/
    STACK (TOP):= ITEM;
    3) End of IF
    4) Exit

Pop operation is used to remove an item from stack, first get the element and then decrease TOP pointer.

    POP_STACK(STACK,TOP,ITEM)

    Algorithm to pop an element from stack.

    1) IF TOP = 0 then
        Print “Stack is empty”;
        Exit;
    2) Otherwise
        ITEM: =STACK (TOP);
        TOP:=TOP – 1;
    3) End of IF
    4) Exit

    IS_FULL(STACK,TOP,MAX,STATUS)

    Algorithm to check stack is full or not. 
    STATUS contains the result status.

    1) IF TOP = MAX then
        STATUS:=true;
    2) Otherwise
        STATUS:=false;
    3)  End of IF
    4)  Exit

    IS_EMPTY(STACK,TOP,MAX,STATUS)

    Algorithm to check stack is empty or not.
    STATUS contains the result status.

            
    1) IF TOP = 0 then
        STATUS:=true;
    2) Otherwise
        STATUS:=false;
    3)  End of IF
    4)  Exit

Complete program to implement stack using above functions & algorithms

Using C
Using C++

    #include<stdio.h>
    #define MAX 3

    typedef struct
    {
        int TOP;
        int ele[MAX];

    }Stack;

    void init(Stack *s)
    {
    s->TOP = -1;
    }

    int isFull(Stack *s)
    {
    if(s->TOP == MAX-1)
    return 0;
    return -1;
    }

    int isEmpty(Stack *s)
    {
	    if(s->TOP == -1)
		    return 0;
	    return -1;
    }

    void push(Stack *s, int item)
    {
	    if( !isFull(s) )
	    {
		    printf("\nStack is full");
		    return;
	    }
	    s->TOP = s->TOP + 1;
	    s->ele[s->TOP] = item;
    }

    int pop(Stack *s, int *item)
    {
	    if(!isEmpty(s))
	    {
		    printf("\nStack is empty");
		    return -1;
	    }
	    *item = s->ele[s->TOP];
	    s->TOP = s->TOP - 1;

	    return 0;

    }

    int main()
    {
	    Stack s;
	    int item;

	    clrscr();

	    init(&s);

	    push(&s,10);
	    push(&s,20);
	    push(&s,30);

	    pop(&s,&item);
	    printf("\nPoped Item : %d",item);

	    pop(&s,&item);
	    printf("\nPoped Item : %d",item);

	    pop(&s,&item);
	    printf("\nPoped Item : %d",item);
	    getch();

	    return 0;
    }

    Inserted item : 10
    Inserted item : 20
    Inserted item : 30
    Inserted item : 40
    Inserted item : 50
    Stack Overflow
    Deleted item : 50
    Deleted item : 40
    Deleted item : 30
    Deleted item : 20
    Deleted item : 10
    Stack Underflow

    #include <iostream>
    using namespace std;
    #define MAX 5

    //Declaration of Stack
    class Stack
    {
	    private:
		    int top;
		    int ele[MAX];
	    public:
		    Stack();
		    int 	isFull();
		    int 	isEmpty();
		    void    push(int item);
		    int     pop(int *item);
    }; 

    //Initialization of stack
    Stack:: Stack()
    {
	    top = -1;
    }

    //Check stack is full or not
    int Stack:: isFull()
    {
	    int full = 0;

	    if( top == MAX-1 )
		    full = 1;

	    return full; 
    }

    //Check stack is empty or not
    int Stack:: isEmpty()
    {
	    int empty = 0;

	    if( top == -1 )
		    empty = 1;

	    return empty;
    }

    //Insert item into stack
    void Stack:: push( int item )
    {
	    if( isFull() )
	    {
		    cout<<"\nStack Overflow";
		    return;
	    }

	    top++;
	    ele[top] = item;

	    cout<<"\nInserted item : "<< item;	
    }

    //Delete item from stack
    int Stack:: pop( int *item )
    {
	    if( isEmpty() )
	    {
		    cout<<"\nStack Underflow";
		    return -1;
	    }

	    *item = ele[top--];
	    return 0;
    }

    int main()
    { 
	    int item = 0;

	    Stack s = Stack();

	    s.push( 10 );
	    s.push( 20 );
	    s.push( 30 );
	    s.push( 40 );
	    s.push( 50 );
	    s.push( 60 );


	    if( s.pop(&item) == 0 )
		    cout<<"\nDeleted item : "<< item;
	    if( s.pop(&item) == 0 )
		    cout<<"\nDeleted item : "<< item;
	    if( s.pop(&item) == 0 )
		    cout<<"\nDeleted item : "<< item;
	    if( s.pop(&item) == 0 )
		    cout<<"\nDeleted item : "<< item;
	    if( s.pop(&item) == 0 )
		    cout<<"\nDeleted item : "<< item;
	    if( s.pop(&item) == 0 )
		    cout<<"\nDeleted item : "<< item;

	    cout<< endl;

	    return 0;
    }

    Inserted item : 10
    Inserted item : 20
    Inserted item : 30
    Inserted item : 40
    Inserted item : 50
    Stack Overflow
    Deleted item : 50
    Deleted item : 40
    Deleted item : 30
    Deleted item : 20
    Deleted item : 10
    Stack Underflow