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?

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)

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)

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.