Question

urgent help needed! How to reverse a stack in O(1) ?

Answer 1

How is your stack built? If you build it using an array or a doubly linked list, just change which side you consider the `top' of your stack, and you've reversed it.

Answer 2

it's built using an array . Oh, i didn't think about it being that simple :O . Thankyou :)

Answer 3

No problem :)

Answer 4

Ok, so actually I'm sort of lying -- you need to change which side is the top of your stack *and* you need to change what you consider `popping'. For an array, instead of adding to the index, you'll have to subtract from it to correctly reverse the stack.

Answer 5

Umm ok . But isn't there any other way for which we wouldn't have to change the 'pop' function ?

Answer 6

You don't have to change the pop function. Some pseudocode, assuming your array contains doubles:

double myStack[10];
int currentIndex = 0;
int toPop = 1;

double pop() {
double top = myStack[currentIndex];
currentIndex += toPop;

return top;
}

void reverse() {
if (currentIndex == 0)
currentIndex = 9;
else
currentIndex = 0;

toPop = -toPop; // flip the direction we `pop' in
}

Answer 7

Omg, i get it! :) . Thanks alot ! :)

Answer 8

No problem :)