The answer below is 'cheating', in that while it doesn't use any space between operations the operations themselves can use more than $O(1)$ space. See elsewhere in this thread for an answer that doesn't have this problem.
While I don't have an answer to your exact question, I did find an algorithm that works in $O(\sqrt{n})$ time instead of $O(n)$. I believe this is tight, though I don't have a proof. If anything, the algorithm shows that trying to prove a lower bound of $O(n)$ is futile, so it might help in answering your question.
I present two algorithms, the first being a simple algorithm with a $O(n)$ running time for Pop and the second with a $O(\sqrt{n})$ running time for Pop. I describe the first one mainly because of its simplicity so that the second one is easier to understand.
To be give more details: the first uses no additional space, has an $O(1)$ worst case (and amortized) Push and an $O(n)$ worst case (and amortized) Pop, but the worst case behaviour is not always triggered. Since it doesn't use any additional space beyond the two queues, it's slightly 'better' than the solution offered by Ross Snider.
The second uses a single integer field (so $O(1)$ extra space), has a $O(1)$ worst case (and amortized) Push and a $O(\sqrt{n})$ amortized Pop. It's running time is therefore significantly better than that of the 'simple' approach, yet it does use some extra space.
The first algorithm
We have two queues: queue $first$ and queue $second$. $first$ will be our 'push queue', while $second$ will be the queue already in 'stack order'.
- Pushing is done by simply enqueueing the parameter onto $first$.
- Popping is done as follows. If $first$ is empty, we simply dequeue $second$ and return the result. Otherwise, we reverse $first$, append all of $second$ to $first$ and swap $first$ and $second$. We then dequeue $second$ and return the result of the dequeue.
C# code for the first algorithm
This could should be quite readable, even if you've never seen C# before. If you don't know what generics are, just replace all instances of 'T' by 'string' in your mind, for a stack of strings.
public class Stack<T> {
private Queue<T> first = new Queue<T>();
private Queue<T> second = new Queue<T>();
public void Push(T value) {
first.Enqueue(value);
}
public T Pop() {
if (first.Count == 0) {
if (second.Count > 0)
return second.Dequeue();
else
throw new InvalidOperationException("Empty stack.");
} else {
int nrOfItemsInFirst = first.Count;
T[] reverser = new T[nrOfItemsInFirst];
// Reverse first
for (int i = 0; i < nrOfItemsInFirst; i++)
reverser[i] = first.Dequeue();
for (int i = nrOfItemsInFirst - 1; i >= 0; i--)
first.Enqueue(reverser[i]);
// Append second to first
while (second.Count > 0)
first.Enqueue(second.Dequeue());
// Swap first and second
Queue<T> temp = first; first = second; second = temp;
return second.Dequeue();
}
}
}
Analysis
Obviously Push works in $O(1)$ time. Pop may touch everything inside $first$ and $second$ a constant amount of times, so we have $O(n)$ in the worst case. The algorithm exhibits this behaviour (for instance) if one pushes $n$ elements onto the stack and then repeatedly performs a singe Push and a single Pop operation in succession.
The second algorithm
We have two queues: queue $first$ and queue $second$. $first$ will be our 'push queue', while $second$ will be the queue already in 'stack order'.
This is an adapted version of the first algorithm, in which we don't immediately 'shuffle' the contents of $first$ into $second$. Instead, if $first$ contains a sufficiently small number of elements compared to $second$ (namely the square root of the number of elements in $second$), we only reorganise $first$ into stack order and don't merge it with $second$.
- Pushing is still done by simply enqueueing the parameter onto $first$.
- Popping is done as follows. If $first$ is empty, we simply dequeue $second$ and return the result. Otherwise, we reorganising the contents of $first$ so that they are in stack order. If $|first| < \sqrt{|second|}$ we simply dequeue $first$ and return the result. Otherwise, we append $second$ onto $first$, swap $first$ and $second$, dequeue $second$ and return the result.
C# code for the first algorithm
This could should be quite readable, even if you've never seen C# before. If you don't know what generics are, just replace all instances of 'T' by 'string' in your mind, for a stack of strings.
public class Stack<T> {
private Queue<T> first = new Queue<T>();
private Queue<T> second = new Queue<T>();
int unsortedPart = 0;
public void Push(T value) {
unsortedPart++;
first.Enqueue(value);
}
public T Pop() {
if (first.Count == 0) {
if (second.Count > 0)
return second.Dequeue();
else
throw new InvalidOperationException("Empty stack.");
} else {
int nrOfItemsInFirst = first.Count;
T[] reverser = new T[nrOfItemsInFirst];
for (int i = nrOfItemsInFirst - unsortedPart - 1; i >= 0; i--)
reverser[i] = first.Dequeue();
for (int i = nrOfItemsInFirst - unsortedPart; i < nrOfItemsInFirst; i++)
reverser[i] = first.Dequeue();
for (int i = nrOfItemsInFirst - 1; i >= 0; i--)
first.Enqueue(reverser[i]);
unsortedPart = 0;
if (first.Count * first.Count < second.Count)
return first.Dequeue();
else {
while (second.Count > 0)
first.Enqueue(second.Dequeue());
Queue<T> temp = first; first = second; second = temp;
return second.Dequeue();
}
}
}
}
Analysis
Obviously Push works in $O(1)$ time.
Pop works in $O(\sqrt{n})$ amortized time. There are two cases: if $|first| < \sqrt{|second|}$, then we shuffle $first$ into stack order in $O(|first|) = O(\sqrt{n})$ time. If $|first| \geq \sqrt{|second|}$, then we must have had at least $\sqrt{n}$ calls for Push. Hence, we can only hit this case every $\sqrt{n}$ calls to Push and Pop. The actual running time for this case is $O(n)$, so the amortized time is $O(\frac{n}{\sqrt{n}}) = O(\sqrt{n})$.
Final note
It it is possible to eliminate the extra variable at the cost of making Pop an $O(\sqrt{n})$ operation, by having Pop reorganise $first$ at every call instead of having Push do all the work.
