edited by
34,493 views
143 votes
143 votes

Let $Q$ denote a queue containing sixteen numbers and $S$ be an empty stack. $Head(Q)$ returns the element at the head of the queue $Q$ without removing it from $Q$. Similarly $Top(S)$ returns the element at the top of $S$ without removing it from $S$. Consider the algorithm given below.

while Q is not Empty do 
  if S is Empty OR Top(S) ≤ Head (Q) then 
     x:= Dequeue (Q); 
     Push (S, x); 
  else  
     x:= Pop(S); 
     Enqueue (Q, x);
  end
 end

The maximum possible number of iterations of the while loop in the algorithm is _______.

edited by

12 Answers

1 votes
1 votes
ans will be n^2 ; where n is the no. of elements insterted in queue in descending order ,here n=16 so answer is 256 ,the complete working code for this including stacks nd queues is below:-

//author-ashwin.s.suthar software engg
//gate cs 2017;air 1880 gate cs 2018 all in  top 10 rank final ans of given while loop total iteratons is 256 for 16 queue descending elememts it will result 16*16=256:iteraton
#include<stdlib.h>
#include<stdio.h>
#define max 500
#define size 500
struct stack
{
    int s[size];
    int top;
} st;
int pop();
void displaystk();
int stfull();
int top();
int head();
int gatewhile();
void push(int x);
int stempty();
int queue[max], front = 0, rear = 0;
int menu();
void enqueue();
void prenqueue(int x);
int dequeue();
void display();
int main()
{
    int ch, outq = 0, outs = 0, e;
    do
    {
        outq = 0;
        printf("\nQueues using Arrays\n");
        ch = menu();
        switch (ch)
        {
        case 1:
            enqueue();
            break;
        case 2:
            e = dequeue();
            break;
        case 3:
            display();
            break;
        case 4:
            outq = 1;
            break;
        default:
            printf("\n Please enter a valid choice for queues and then stacks will ru n next!!");
        }

        int item, choice;
        char ans;
        st.top = -1;
        outs = 0;
        printf("\n\tImplementation Of Stack");

        printf("\nMain Menu");
        printf
            ("\n1.Push \n2.Pop \n3.Display \n4.run the while loop of gate q 2016\n5.exit from stack& queue");
        printf("\nEnter Your Choice");
        scanf("%d", &choice);
        switch (choice)
        {
        case 1:
            printf("\nEnter The item to be pushed");
            scanf("%d", &item);
            if (stfull())
                printf("\nStack is Full!");
            else
                push(item);
            break;
        case 2:
            if (stempty())
                printf("\nEmpty stack!Underflow !!");
            else
            {
                item = pop();
                printf("\nThe popped element is %d", item);
            }
            break;
        case 3:
            displaystk();
            break;
        case 4:
            printf("\n final ans count of while loop is %d", gatewhile());
            break;
        case 5:
            outs = 1;
            break;
        }

    }
    while ((outs + outq) < 2);

    return 0;
}

int menu()
{
    int ch;
    printf("\n1.ENQUEUE \n2.DEQUEUE \n3.DISPLAY \n4goto stack and then exit");
    printf("\nEnter your Choice:");
    scanf("%d", &ch);
    return ch;
}

void enqueue()
{
    int element;
    if (rear == max)
    {
        printf("\nOverflow!!");
    }
    else
    {
        printf("\nEnter Element:");
        scanf("%d", &element);
        queue[rear++] = element;
        printf("\n %d Enqueued at %d", element, rear - 1);
    }

}

void prenqueue(int x)
{
    int element;
    element = x;
    if (rear == max)
    {
        printf("\nOverflow!!");
    }
    else
    {
        queue[rear++] = element;
        printf("\n %d Enqueued at %d", element, rear - 1);
    }

}

int dequeue()
{
    if (rear == front)
    {
        printf("\nUnderflow!!");
    }
    else
    {
        front++;
        printf("\n%d Element is Dequeued from %d", queue[front - 1], front - 1);
    }
    return queue[front - 1];
}

void display()
{
    int i;
    if (front == rear)
    {
        printf("\nQueue is Empty!!!");
    }
    else
    {
        printf(" \n");
        for (i = front; i < max; i++)
        {
            printf(" | %d ", queue[i]);
        }
        printf("|");
    }
}

int stfull()
{
    if (st.top >= size - 1)
        return 1;
    else
        return 0;
}

void push(int item)
{
    st.top++;
    st.s[st.top] = item;
    printf("\n Item %d pushed at top %d ", item, st.top);
}

int stempty()
{
    if (st.top == -1)
    {
        printf("\nstack is empty");
        return 1;
    }
    else
    {
        printf("\nstack is non empty and topmost element %d and top %d", st.s[st.top], st.top);
        return 0;
    }
}

int pop()
{
    int item;
    item = st.s[st.top];
    st.top--;
    printf("\nItem popped is %d and current top is %d", item, st.top);
    return (item);
}

void displaystk()
{
    int i;
    if (stempty())
        printf("\nStack Is Empty!");
    else
    {
        for (i = st.top; i >= 0; i--)
            printf("\n%d", st.s[i]);
    }
}

int top()
{
    printf("\n topmost element is %d and top is %d", st.s[st.top], st.top);
    if (st.top == -1)
        return 0;
    return st.s[st.top];
}

int head()
{
    printf("\n element at front of queue is %d and front is %d", queue[front], front);
    if (front == rear)
        return 0;
    return queue[front];
}

int gatewhile()
{
    int c = 0, x;
    while (rear != front)        // queue is not empty by ashwi n code up
    {
        c++;
        if (stempty() || (top() <= head()))
        {
            x = dequeue();
            push(x);
        }
        else
        {
            x = pop();
            prenqueue(x);
        }
    }
    return c;
}
1 votes
1 votes
how to approach?

look basically there could be 3 cases->

case 1 ;  let the queue contains numbers in the ascending order

q:[1,2,3]     s[]:  nothing initially             count(no of times while loop will be executed)=0;

now s is empty   ;  push 1                  count=1,,            q[2,3]

since stack.top=1 < 2  hence push     s[1,2]  count=2       q[3]

again stack.top=2 < 3  hence push  again     s[1,2,3]   count=3    q[];

thus count=3;

but it seems the best case in which the while loop will be executed less no. of times.

 

case2:  let it be neither increasing nor decreasing

let    q[1,3,2]   s[]   count=0;

since stack is empty   push 1

q[3,2]    s[1]   count=1;

now stack.top =1<3 hence again push

q[2]    s[1,3]    count=2;

stack.top =3 but is greater than 2 hence pop from stack and insert in the queue

q[2,3]    s[1]   count =3

now stack.top=1<2 hence push

q[3]   s[1,2]    count=4

stack.top =2<3 hence again push

q[]   s[1,2,3]   count=5

so here while loop gets executed more no. of times than case1

 

case 3:

let q contains nos. in descending order

q[3,2,1]     s[]     count=0

since stack is empty

push 3 onto the stack

q[2,1]     s[3]    count=1;

stack.top=3>2 hence pop from stack and insert into queue

q[2,1,3]     s[]   count=2;

since stack is empty   push

q[1,3]    s[2]     count=3

stack.top =2>1  hence pop from stack and insert into queue

q[1,3,2]  s[]   count=4

again stack empty  push

q[3,2]      s[1]    count=5;

( here we should note few points   

a-  now since 1 is at the bottom then everytime whenever we will apply stack.top < queue.element  it will always hold true . that means 1 will always be present at the bottom from here onwards.

b-  for putting 1 to the bottom how many times while loop gets executed(count=5)  ?

5 because   3 pushed in stack

                    3 popped from stack and inserted into queue

                   2 pushed in stack

                   2  popped from stack and inserted into queue

                   1 pushed into stack

conclusion1:  for 3 elements we need 2*3-1  times while loop execution for placing the least element (here 1 ) onto the stack

conclusion2 :  for n elements we will need 2*n-1 times while loop execution for placing the least element (here 1 ) onto the stack

)

now continuing with the problme:

q[3,2]      s[1]    count=5;

now out problem is the same see it is decreasing order and 1 on stack has nothing to do i.e assume stack is empty.

stack.top=1<3  therfore push    

q[2]    s[1,3]  count=6;

stack.top =3>2 hence pop from stack and insert into queue

q[2,3]   s[1]   count=7;

stack.top=1<2 hence 2 pushed onto the stack

q[3]    s[1,2]    count=8;

stack.top =2<3 hence pushed onto stack

q[]   s[1,2,3]    count=9

 so finally queue with decreasing order of elements have taken most no. of time of while loop execution.

 

now actually we have solved for n=16 if we can conclude

so our recurrence relation should be

count[n]= 2n-1+count[n-1]

why?

bcz it is taking 2n-1 steps to put the least element onto the bottom of the stack and same problem continues for (n-1)

and one more thing the order in which the elements are getting stored onto the stack is increasing order(bottom to top)

 

now   count[16]=   31 + count[15]

=31+29+count[14]

=31+29+27+count[13]

similarly if you will add

31+29+27+.....+3+count[1]

count[1]=1 only because only 1 element on queue and initially when (stack.isempty() is checked then it will be inserted into stack thus here count=1 only]

=31+29+27+.......+3+ 1

now this is the sum of A.P

a=1 ,   cd=2   n=16

thus   Sn=n/2(a+l)

=16/2(1+31)

=8*32=256
0 votes
0 votes

Maximum number of iterations is only possible when  queue has element in decreasing order.

16,15,14,13,12...............1

1st iteration : As, initially stack is empty, 16 will  be pushed onto stack.

2nd iteration : Head(q) = 15, so, 16 will be popped from stack and enqueued in queue.(due to else part)

So each number from (16 to 2 ) same pattern will follow, that is for each number 2 iterations is performed. Total iteration =2*15 =30.

now stack is empty and Head(Q) =1 , then 1 will be pushed and 1 will remain in stack. 

So total iterations after  which one elements is removed from queue is = 30+1 =31 (i.e 2n-1 ,n = no elements in queue)

Now queue has 15 elements therefore no. of iteration to remove another element from queue will be 2*15 -1 = 29.

Similarly 14 elements =27 iteration, 13 elements =25 iteration and so on....

Therefore total iterations = 31+29+27+25....3+1= 8*32 =256 iterations

edited by
Answer:

Related questions