Data structure & Algorithms

Stack

Stack is a linear data structure with property last in first out. In this page we will define stack using 2 way i.e. first with array & second with link list.

1: What is a Stack?

Another linear data structure with collection of object which follows a thumb rule i.e. element or data inserted in stack at last is pop out from stack first. In-sort this is called LIFO(last in first out)

The above image describes how elements or data is keep stacking on the top of each other i.e. insert or push operation once pop operation is done it's always from top i.e. first in last out. An example last inserted element in stack was "element 5" when poped it was non other but "element 5".


2: How to declare and define stack

Array & link list both have been covered, let us define the stack using both
A: Define stack using Array of size 100: it has limitation i.e. once array is full new memory need to be allocated. Below code define an stack that can have 100 data of type integer. since no push & pop operation is performed initialize 'top' to -1.



int stack[100];
int top = -1; 	
							 

B: Define stack using Link List: It uses dynamic memory allocation for every inserted element. Below code define a stack using link list that can store the data of type integer and initialize it's head or top with null.


typedef struct _stack
{
    int data;
    struct _stack *next;
}stack;

stack *top_head = NULL;
							 


3: List of operation in a stack

There are 2 operations in stack , 1st push i.e. inserting data/element in stack and 2nd operation is pop i.e. delete or remove data/element from stack.
Now let is think if stack is implemented using array. we have seen 2 operation of array i.e.
1st : Insert an element as a last of an Array - this is nothing but the push operation in stack.
2nd: Delete an element at last of an Array- this is nothing but pop operation if stack is implemented using array.

So first we have seen if stack is implemented using array how to do the push & pop using array operations, Now if stack is implemented using link list. let us see which link list operation work as push & pop.
1st link list operation to insert element i.e. Insert An Element At Beginning Of Link List - is push operation
2nd link list operation to delete i.e. Delete An Element In Link List From Beginning - act as pop operation of stack.
detail of each operation is given in below sections.



4: Push operation in Stack

In previous section we have seen what is push operation in sort adding element at top is push operation.
Problem statement:
- Write a code to insert integer data in stack using array.
A1. Solution steps:
- define array of size 100 & init top as -1


int stack[100];
int top = -1;
							   
- Check if stack is empty insert the data

if(top<99)
{
    top++;
    stack[top] = data;
}
else
    cout<<"\nStack is full\n";
							   
- let us put these above code in function

#include <iostream>
#include <string>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

int stack[100];
int top = -1;

void push(int data)
{
    if(top<99)
    {
        top++;
        stack[top] = data;
    }
    else
        cout<<"\nStack is full\n";
}
							
B1. Now let us change the problem : Create stack using link list instead of array
Solution : - below is code using list for push

typedef struct _stack
{
    int data;
    struct _stack *next;
}stackUsingLinkList;

stackUsingLinkList *top_head = NULL;

void push(int data)
{
   if(top_head == NULL)
    {
        top_head = (stackUsingLinkList *)malloc(sizeof(stackUsingLinkList));
        if(top_head)
        {
            top_head->data = data;
            top_head->next = NULL;
        }
    }
    else
    {
        stackUsingLinkList *tmp = top_head;
        top_head = (stackUsingLinkList *)malloc(sizeof(stackUsingLinkList));
        if(top_head)
        {
            top_head->data = data;
            top_head->next = tmp;
        }
        else
        {
            top_head = tmp;
        }
    }
}
							


5: POP operation in stack

This section explains & provide code to how to pop out data / element from stack.
Problem statement:
- pop out data from stack that is implemented using array
Solution Steps
- Push operation is defined in section 4
- Check if stack is empty return


int ret = -1;
if(top>=0)
{

}
return ret;

							   
- if stack is not empty return the last element from array & reduce top by 1

int ret = -1;
if(top>=0)
{
	ret = stack[top];
	top--;
	if(top <0)
		top =-1;
}
return ret;

							   
- Now let us put this code in pop function which return -1 if stack is empty

int pop()
{
    int ret = -1;
    if(top>=0)
    {
        ret = stack[top];
        top--;
        if(top < 0)
            top =-1;
    }
    return ret;
}

							   
stack code to pop using link list


int pop()
{
   if(top_head)
   {
      stackUsingLinkList *tmp = top_head;
      top_head = top_head->next;
      tmp->next = NULL;
      int ret = tmp->data;
      free(tmp);
      return ret;
   }
   return -1;
}
							   
Complete stack code using array is below

#include <iostream>
#include <string>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

int stack[100];
int top = -1;

typedef struct _stack
{
    int data;
    struct _stack *next;
}stackUsingLinkList;

stackUsingLinkList *top_head = NULL;

void push(int data)
{
    if(top<99)
    {
        top++;
        stack[top] = data;
    }
    else
        cout<<"\nStack is full\n";
}
int pop()
{
    int ret = -1;
    if(top>=0)
    {
        ret = stack[top];
        top--;
        if(top <0)
            top =-1;
    }
    return ret;
}
void display_stack()
{
    cout<<"\nstack data\n";
    for(int i=top;i>=0;i--)
    {
        cout<>index;
   return index;
}

int main()
{
    int input =0;
    do{
        input = main_menu();
        if(input == 1)
        {
            int data;
            cout<<"\nEnter Data: ";
            cin>>data;
            push(data);
        }
        else if(input == 2)
        {
            int poped_data = pop();
            if(poped_data == -1)
                cout<<"\nStack empty\n";
            else
            {
                cout<< " pop out data from stack: "<<  poped_data << "\n";
            }
        }
        else if(input == 3)
            display_stack();
    }while(input != 4);
    return 0;
}
                               
Stack code using link list is below

#include <iostream>
#include <stdlib.h>
#include <malloc.h>

using namespace std;

typedef struct _stack
{
    int data;
    struct _stack *next;
}stackUsingLinkList;

stackUsingLinkList *top_head = NULL;

void push(int data)
{
   if(top_head == NULL)
    {
        top_head = (stackUsingLinkList *)malloc(sizeof(stackUsingLinkList));
        if(top_head)
        {
            top_head->data = data;
            top_head->next = NULL;
        }
    }
    else
    {
        stackUsingLinkList *tmp = top_head;
        top_head = (stackUsingLinkList *)malloc(sizeof(stackUsingLinkList));
        if(top_head)
        {
            top_head->data = data;
            top_head->next = tmp;
        }
        else
        {
            top_head = tmp;
        }
    }
}

int pop()
{
   if(top_head)
   {
      stackUsingLinkList *tmp = top_head;
      top_head = top_head->next;
      tmp->next = NULL;
      int ret = tmp->data;
      free(tmp);
      return ret;
   }
   return -1;
}
void display()
{
    cout<<"\nstack data\n";
    stackUsingLinkList *tmp = top_head;
    while(tmp)
    {
        cout<<" "<data<<" ";
        tmp =tmp->next;
    }
    cout<<"\nstack end\n";
}

int main_menu()
{
   int index = 0;
   cout<<"\n Main Menu\n";
   cout<<"\n==============================\n";
   cout<<"\n1: Push";
   cout<<"\n2: Pop";
   cout<<"\n3: Print Stack";
   cout<<"\n4: Exit";
   cout<<"\n==============================\n";
   cout<<"\nEnter Your Input: ";
   cin>>index;
   return index;
}

int main()
{
    int input =0;
    do{
        input = main_menu();
        if(input == 1)
        {
            int data;
            cout<<"\nEnter Data: ";
            cin>>data;
            push(data);
        }
        else if(input == 2)
        {
            int poped_data = pop();
            if(poped_data == -1)
                cout<<"\nStack empty\n";
            else
            {
                cout<< " pop out data from stack: " << poped_data << "\n";
            }
        }
        else if(input == 3)
            display();
    }while(input != 4);
    return 0;
}