Stacks and Queues using linked list

Concept of Stack and Queue

1. Stack :

Now stack works on the concept of LIFO , which means last element in will be the first element out . For only understanding purpose we take stack to be horizontal ,

For our conceptual understanding consider a stack of plates example , you have to put plate one after another and can only take the top most plate out .

Now there are a few functions you should know about stacks , there are a few functions :

1. Push (): it enters value into stack ,
2. Pop() :it remove the top value of the stack
3. Display () : to display the stack

firstly the array approach to make you understand the concept of stacks

 int item, choice, i;
    int stack[10];
    int top = 0;//we start from the zero index ,
    int exit = 0;//for the do-while condition 

    cout << "\nStack using array ";
    do {
        cout << "\n1.Push \n2.Pop \n3.Display \nOthers to exit";
        cout << "\nEnter Your Choice : ";
        cin>>choice;
        switch (choice) {
            case 1:
                if (top == 10)
                    cout << "\n Stack is Full!";
                else {
                    cout << "\nEnter The Value to be pushed : ";
                    cin>>item;
                    cout << "\n Position : " << top << ", Pushed Value  :" << item;
                    stack[top++] = item;
                }
                break;
            case 2:
                if (top == 0)
                    cout << "\n Stack is Empty!";
                else {
                    --top;
                    cout << "\n Position : " << top << ", Popped Value  :" << stack[top];
                }
                break;
            case 3:
                cout << "\n Stack Size : " << top;
                for (i = (top - 1); i >= 0; i--)
                    cout << "\n Position : " << i << ", Value  :" << stack[i];
                break;
            default:
                exit = 1;
                break;
        }
    } while (exit==0);

Now the problem with Stack array was that , it was not scalable , our problems our going to be static in nature .Hence we use Linked list approach or vector approach or Dynamic memory allocation approach to counter this ,

our class’s will look like this,

Our code snippet will be ,

void Stack ::push(int x,int counter)
{
    node * newnode= new node(x);
    newnode->next=top;
    top=newnode;
    if(counter==0)
    {
        bottom =newnode ;
        //value of bottomest node , it's not used but if you want to find the value of it then 
    }
}

int Stack ::isEmpty()
{
    return (top==NULL);
}

void Stack::pop()
{
    int n = top->data;
    node *temp=top;
    top=top->next;
    cout<<"value "<<n<<" is deleted ";
    free (temp);
}
void Stack::Display(Stack s1)
{

    node * current_node1=s1.top;
    while (current_node1!=NULL)
    {
        cout<<current_node1->data<<"\t";
        current_node1=current_node1->next;
    }

}

2.Queue :

Now Queue works on the concept of first element pushed will be last element to be first out , for conceptual reasons we use queue to be Vertical,

For our conceptual understanding , we use an example of a line at a store , the first person who arrived gets served first ,

Now there are a few functions you should know about queue , there are a few functions :

1. Push (): it enters value into queue
2. Pop() :it remove the top value of the queue
3. Display () : to display the queue

First lets take an easy implementation of queue using array ,

   int item, choice, i;
    int queue[10];
    int rear = 0;///rear index of queue
    int front = 0;//front index of queue 
    int exit = 0;

    cout << "\n Queue using array";
    do {
        cout << "\n1.Insert \n2.Remove \n3.Display \nOthers to exit";
        cout << "\nEnter Your Choice : ";
        cin>>choice;
        switch (choice) {
            case 1:
                if (rear == 10)
                    cout << "\nQueue Reached Max!!";
                else {
                    cout << "\nEnter The Value to be Insert : ";
                    cin>>item;
                    cout << "\nPosition : " << rear + 1 << " , Insert Value  : " << item;
                    queue[rear++] = item;
                }
                break;
            case 2:
                if (front == rear)
                    cout << "\n## Queue is Empty!";
                else {
                    cout << "\nPosition : " << front << " , Remove Value  :" << queue[front];
                    front++;
                }
                break;
            case 3:
                cout << "\nQueue Size : " << (rear - front);
                for (i = front; i < rear; i++)
                    cout << "\nPosition : " << i << " , Value  : " << queue[i];
                break;
            default:
                exit = 1;
                break;
        }
    } while (exit!=0);

Now the problem with queue array was that , it was not scalable , our problems our going to be static in nature .Hence we use Linked list approach or vector approach or Dynamic memory allocation approach to counter this ,

our code snippet is ,

int Queue ::isEmpty()
{
    return (front==NULL);
}


void Queue :: enque(int x)
{
    node * newnode= new node(x);
    if(isEmpty()!=0)
        front=rear=newnode;
    else
    {
        rear->next=newnode;
        rear=newnode;    
    }
}


void Queue::deque()
{
    int n = front->data;
    node *temp=front;
    front=front->next;
    cout<<"value "<<n<<" is deleted ";
    free (temp);
    if(front==NULL)
        rear=front;
}
void Queue::Display(Queue q1)
{

    node * current_node1=q1.front;
    while (current_node1!=NULL)
    {
        cout<<current_node1->data<<"\t";
        current_node1=current_node1->next;
    }

}

GitHub link for code -> https://github.com/kakabisht/Data-structures/tree/master/Stack%20%26%20Queue%20using%20array%20and%20linklist

For any other questions or suggestions, you can leave a comment or connect with me on LinkedIn .