How would you invert a stack, without using extra data structures, like a second, or temporary, stack. Thus no stack1-stack2 or stack-queue-stack implementation in the answer. You just have access to push/pop feature of a standard stack.
I think there is way to do it by keeping a global counter and using pointer manipulation.
Does stack-stack count? You do not need a different data structure that way. In this case pop an element and push it onto the other stack. Do this for all elements and you inverted the stack. On the downside of it is that you get another stack, it is not inplace.
If you, as you added to your question, want to do this using pointers and counters, it is very implementation depended and violates the definition of a stack. Your solution can be broken at any new release or change of implementation of the stack. I would refrain from doing this. (This of course is different if you implement your own stack, but then you could use a different data structure in the first place to represent your problem more accurately.)
As a stack only gives you access to the top element, it's not possible to invert (reverse the or order of) without using some additional storage. The most minimal that I can think of (only weakly exception safe) is something like:
template<class T>
void Invert( std::stack<T>& a_stack )
{
std::stack<T> tmp;
while( !a_stack.empty() )
{
tmp.push( a_stack.top() );
a_stack.pop();
}
std::swap( a_stack, tmp );
}
If your stack is implemented as a linked list (and you have access to the implementation), then run through the linked list reversing the direction then point head at the new tail.
// oh man, I think this is right
cur = head;
while(cur->next)
{
tmp = cur->next->next;
cur->next->next = cur;
cur = tmp;
}
head->next = null;
head = cur;
Otherwise do what everyone else is saying.
If your stack is a doubly linked list... just move the top pointer to the bottom :-). Or just reverse the list in place. Even if you had an array implementation, the reversal would be easy. This all assumes that you have access to the innards of the stack. If you can only use pop(), you need other storage.
A stack maybe nothing but an array of objects. Take the midpoint and swap i and length-i elements..
Do you have control of the implementation of your stack?
If so, the stack can easily have a reverse method and be implemented by a double-ended queue. Depending on its mode, it deques from either end on a pop call.
A recursive algorithm (bounds checking left for the reader) will solve the problem without explicitly declaring additional data structures (as per the constraints of the question) by using an implicit data structure: the process call stack.
void invert( Stack stack ) {
Object o = stack.pop();
invert( stack );
append( stack, o );
}
void append( Stack stack, Object o ) {
Object obj = stack.pop();
append( stack, o );
stack.push( obj );
}
The invert function pops all the values from the call stack (which is not a new stack data structure instance variable). Once all the values have been popped, they get appended in reverse order via the append method.
See Also
http://discuss.joelonsoftware.com/default.asp?interview.11.312666.6
http://wiki.answers.com/Q/How_do_you_reverse_a_stack_in_place_using_recursion
This can be done in O(1) if you implement your stack as a doubly linked list with two pointers per node whose semantic meaning can be switched by toggling a direction attribute of the stack. You will also need attributes to keep track of both end nodes. The reverse operation then simply needs to toggle the direction attribute and switch the end node attributes.
so your question is:
I have a stack of objects, how do I invert the stack using only the push and pop functions and not storing the objects in any other data structure?
answer: you can't.
I think the better question is WHY?
Working code:
/**
* http://stackoverflow.com/questions/1072903/invert-a-stack-without-using-extra-data-structures
*
* @param s
*/
public static void revertStack(Stack<Integer> s) {
if (s.isEmpty()) {
return;
} else {
Integer a = s.pop();
revertStack(s);
appendStack(s, a);
}
}
public static void appendStack(Stack<Integer> s, Integer a) {
if (s.isEmpty()) {
s.push(a);
return;
} else {
Integer o = s.pop();
appendStack(s, a);
s.push(o);
}
}