Consider a stack S[1; : : : ; n] of…

0

Consider a stack S[1; : : : ; n] of n elements stored in an array implementation with the array running
from index 1 to index n (top of the stack). Write a pseudocode for reversing the elements t of the
stack such that i t j. The other elements of the stack must retain their positions at the end
of the process. You are allowed to use two extra stacks S1 and S2 each the same size as S. What
is the time complexity of the procedure as a function of n; i; j? Would a similar problem take more
or less time if we were given the input in a queue, and allowed to use two extra queues?

Ravi Garg edited question
    0
    Ashish Gaur (anonymous)

    First of all I have understood the problem as follows : Given a stack s, i and j , reverse the elements between i and j inclusive using exactly two more stacks i.e.

    input : S 1 2 3 4 5 6 7[top], i = 3, j = 5
    output : S 1 2 5 4 3 6 7[top]

    if the above problem statement is right then pseudocode using stack (Assuming n is top of the stack):

    do{
    x = s.pop();
    s1.push(x);
    }while(x!=i);

    do{
    x = s1.pop();
    s2.push(x);
    }while(x!=i)

    while(!s2.isEmpty())
    s.push(s2.pop());

    while(!s1.isEmpty)
    s.push(s1.pop())

    Worst case : i = 1, j = n => O(n)
    Best case : i = j = 1 => Ω(1)

    Ashish Gaur answered
      0
      Ashutosh Bhatia (anonymous)

      I am not able to understand the exact problem, can u give a example of input and output in terms of the stack

      Ashutosh Bhatia answered
        0
        Ashish Gaur (anonymous)

        pseudocode using queue :

        start = q.peek();

        while(true){
        x = q.dequeue();
        if(x!=i) q.enqueue(x);
        else{
        q1.enqueue(x);
        break;
        }
        }

        do{
        x = q.dequeue();
        q1.enqueue(x);
        }while(x!=j);
        //now q1 contains list in range i to j

        size = q1.size();
        while(size>0){
        for(int i = 1; i O(n^2)
        Best case : i = j = 1 => Ω(1)

        Ashish Gaur answered
          0
          Ashutosh Bhatia (anonymous)

          Let S1, S2 and S3 be three stacks. Assume that values are initially stored in S1. Pop the elements from S1 one by one till ith element and push them in stack S2. The S2 is having n-i+1 elements. Pop the top j-i+1 elements from S2 and push them in S3. After that, pop all the elements from S3 and push them to S1. Finally, pop all the elements of S2 and push them back in S1. The stack S1 has the final result.

          Ashutosh Bhatia answered
            Add image to editor add image from link

            Question stats

            • Active
            • Views304 times
            • Answers4 answers
            • Followers1 follower
            Question and answer is powered by AnsPress