The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+31 votes
3.7k views

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 _______.

 

 

asked in DS by Boss (9.2k points)
edited by | 3.7k views
i guess answer no. of iteration of while loop will be equal to no. of element in Queue bcoz the "IF" condition always satisfy till "q" become empty.
Each answer below is telling that descending order of input will result in maximum no. of While loop run. But no one is telling how they arrived to this order or how to guess this order during exam.
If my input is 1,2,3..15, 0.. then how many iterations will happen?

Notice -->  Loop invariant property in selected answer.

7 Answers

+28 votes
Best answer
While loop will run for the maximum number of times when the Queue elements are sorted in descending order.

Let's suppose that initially, Queue elements are 16, 15, 14, 13...............2, 1

Now, 16 will be first pushed into the stack, So, now stack top is 16 and Head(Q) is 15, So 16 will be popped out of the stack ( since, "if S is Empty OR Top(S) ≤ Head (Q) "returns false, hence else part will be executed) and enqueued into the Queue.

So, after two iterations Queue elements will be -> 15, 14, 13, .........................2, 1, 16 and stack will be empty.

Similarly, each of the elements 15,14,13...........2 will be pushed into the stack and immediately popped out of the stack(when popped out of the stack then also enqueue into the queue).So after 30 iterations stack will be empty and Queue contains will be like==> 1, 16, 15, 14, .....................2.

Now 1 will be Dequeued and pushed into the stack.Once 1 is pushed into the stack, it will never be popped(or we can say never be enqueued into the Queue again) because in order to Pop 1, there should be an element into the Queue which is less than 1 and that element comes at the front of the queue, since there is no element currently present in the Queue which is less than 1, there is no way to pop 1.

So, after 31 iterations Queue is==> 16, 15, 14, ........................2 and stack contains 1.

Now, the problem boils down to Queue with 15 elements.

Using the similar logic we can say after another 29 iterations (Total =31+29 )Queue will be like==> 16, 15, 14, ............3 and stack contains 1,2  (stack top is 2) and then 2 will remain there in the stack forever.

Similar way if we go on then, after 31 + 29 + 27 + 25 + ......+1 iterations Queue will be empty.

This is in A.P series with d=2. Sum = (16 *(1+31))/2= 16*32/2= 256
answered by Junior (631 points)
selected by
nice answer..

@Sourav Basu

best answer................

thanks to give detailed explanation
+29 votes

256 when 16,15,14,...,1 are present in queue

alternately 15 dequeue & push,15 pop & enqueue followed by 1 dequeue & push i.e. 31 iterations

brings it to the state 16,15,...,2 in queue and 1 in stack

29 iterations to get to 16,15,...,3 in queue and 2,1 in stack and so on

31+29+27+...+1=16^2=256

answered by (389 points)
not clear can someone explain more clearly?

@madhab it creates little bit confusion bcoz of 16 elements lets solve for 3 elements 
for worst case take 3,2,1
  step1.   initially queue contains 3 elements so after 5 while loop iteration  queue contains 3,2 and stack contains 1
step 2. now after 3 more while loop iterations queue contains 3 and stack contains 1,2{top=2}
step3. now after 1 more while loop iteration just push 3 in stack so queue is empty  and stack contains 1,2,3{top=3}
so total no of iteration =5+3+1 =9.
now u can easily generalize the result for n elements it is 
[2n-1]+[2(n-1)-1]+[2(n-2)-1]+[2(n-3)-1]+ ............,+3+1  //it is an a.p. with n terms and common difference=2
so sum= n/2*(1+2n-1)=n2 
so now for 16 elements ans =16=256
 

It's an eminent explanation saurabh rai sir,

#Boss

Thanks

its ok brother just chillllll...
btw i m nt sir i m a fellow aspirant like u  :)
i found this question difficult. how to handle such questions in exam :( ??

@Saurabh

" so after 5 while loop iteration  queue contains 3,2 "

how after 5 iteration.

Can u show me 5 iteration?

@Saurabh During exam how to guess that descending order of elements will run maximum no. of while loop?

why descending ? srestha

I have a little confusion that in the else case are there  2 statements or 1...  Is enqueue included in else??
@gari It's included in Else part. We get through its identation.

Swati Rauniyar thanx:)

+5 votes
Queue Q contains 16,15,14,13,.....,1 where front pointing to 16 and rear is pointing to 1, Let denote Top(S) as T(s) and Head(Q) as H(q)
Stack S is empty now.
Now See While loop condition, As T(s) is empty,we do Dequeue 16 and push 16 to S, So one DEQUEUE and one PUSH, now T(s)=16 and H(q)=15
...........................................................................................................................
As T(S)>H(Q) we do POP 16 and then do Enqueue 16, So one POP and one ENQUEUE , now T(s)=empty and H(q)=15
..........................................................................................................................
As T(s) is empty,we do Dequeue 15 and push 15 to S, So one DEQUEUE and one PUSH, now T(s)=15 and H(q)=14
.......................................................................................................................
As T(S)>H(Q) we do POP 15 and then do Enqueue 15, So one POP and one ENQUEUE , now T(s)=empty and H(q)=14
---------------------------------------------------------------------------------------
..........
...........
For each number upto 2, we dequeue and push once, then POP and enqueue once, for last number that is 1 we dequeue and push once but after that T(S)<H(Q) as then H(Q)=16 and T(S)=1
so it takes 15*2+1=31 iterations to place 1 in stack and make Q(16 to 2), then 29 iterations to place 1,2 in stack and make Q(16 to 3)..then 27 iterations to place 1,2,3 in stack and make Q(16 to 4)..so on....
so total iterations=31+29+27+....+1=256
answered by Junior (517 points)
+1 vote
there can be 3 cases

case 1:

all elements in queue are arranged in ascending order,suppose 1,2,3......16

then it will take 16 iterations are there

but we are asked to compute max possible iterations so consider next case

 

case 2:

all elements are same ,  16 loops are possible in this case

case 3:

it will take 31+29+27+25.......+1=256

which can be calculated as

15             15

⅀(2n+1)=2  ⅀n+15=2*120+15=256

n=0           n=0

 

so the answer is 256
answered by (455 points)

Ans: 256

Worst case input: 16, 15, 14, .... 1

First 16 will get into stack(since S is Empty) then popped out to the end of the queue (since Top(S)>Head(Q)). This happens for all the 15 elements (from 16 to 2). i.e, 2 operations per item (one push to stack and one pop from stack since top(S)>Head(Q)).

After this element 1 gets pushed to stack.

Therefore, in total = 2 * 15 + 1 = 31 operations to insert just one element into stack.

Now the problem gets reduced to handling 15 numbers in the queue (16, 15, 14, .... 2).

Total number of operations  = 31+29+27+...+1

 an =31, a1=1.

an=a1+(n-1)*d   ==> n=16

Total = n/2 * (a1+an) = 16/2*(1+31) = 256

0 votes
i m not getting ??? how it came ??
answered by Active (1.7k points)
0 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;
}
answered by Active (1.1k points)
What is the significance of line given in question that Head(Q) returns element without removing it from Q. Please anyone tell
–1 vote

Maximum no of iterations of the while loop is n2 (in worst case , when (n-1) are in ascending order and nth element is in min of all the element)

I try for n=3 (2 3 1) got 9 iteration of while loop

for base case , it will be n iteration ( no are in ascending order)

and for descending order it will infinite time

 

answered by Loyal (3.5k points)
edited by
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,065 questions
36,872 answers
91,629 comments
34,760 users