Building a queue with two stacks

[pozorvlak]

Here's a data-structure I use almost every day. It's an implementation¹ of a queue. You have two stacks, an in-stack and an out-stack. To add a new item, push it onto the in-stack. To remove an item, take the top item off the out-stack; if the out-stack's empty, push all the items on the in-stack onto the out-stack in reverse order and then take the top item.

In C++:

#ifndef QUEUE_H
#define QUEUE_H

#include <stack>
#include <iostream>

// This code brought to you by 10yo Talisker

template <class T>
class ts_queue
{
	private:
		std::stack<T> in;
		std::stack<T> out;
		void turnover();
		void turn_back_over();
		void dump_stack(std::stack<T>& stack);
	public:
		void push(T);
		void pop();
		int size();
		T& front();
		T& back();
		bool empty() const;
		void dump(); // dump output state, for debugging
};

template <class T>
void ts_queue<T>::turnover()
{
	// sample implementation, O(n)
	while (!in.empty()) {
		out.push(in.top());
		in.pop();
	}
}

template <class T>
void ts_queue<T>::turn_back_over()
{
	// sample implementation, O(n)
	while (!out.empty()) {
		in.push(out.top());
		out.pop();
	}
}

template <class T>
void ts_queue<T>::push(T t)
{
	in.push(t);
}

template <class T>
void ts_queue<T>::pop()
{
	if (out.empty()) {
		turnover();
	}
	out.pop();
}

template <class T>
int ts_queue<T>::size()
{
	return in.size() + out.size();
}

template <class T>
T& ts_queue<T>::front()
{
	if (out.empty()) {
		turnover();
	}
	out.top();
}

template <class T>
T& ts_queue<T>::back()
{
	if (in.empty()) {
		turn_back_over();
	}
	in.top();
}

template <class T>
bool ts_queue<T>::empty() const
{
	return in.empty() && out.empty();
}

// A couple of debugging functions, non-standard

template <class T>
void ts_queue<T>::dump_stack(std::stack<T>& st)
{
	using namespace std;
	stack<T> temp;
	while (!st.empty()) {
		cout << st.top() << " ";
		temp.push(st.top());
		st.pop();
	}
	while (!temp.empty()) {
		st.push(temp.top());
		temp.pop();
	}
	cout << endl << endl;
}

template <class T>
void ts_queue<T>::dump()
{
	std::cout << "in:  ";
	dump_stack(in);
	std::cout << "out: ";
	dump_stack(out);
}

// The rest of the std::queue API is left as an exercise for the reader

#endif

Here's a quick test harness, nicked from here:

#include <assert.h>
#include "queue.h"

int main() {
  ts_queue<int> Q;
  Q.push(8);
  Q.push(7);
  Q.push(6);
  Q.push(2);
  Q.dump();
  
  assert(Q.size() == 4);
  assert(Q.back() == 2);
  Q.dump();

  assert(Q.front() == 8);
  Q.pop();
  Q.dump();

  assert(Q.front() == 7);
  Q.pop();
  Q.dump();

  assert(Q.front() == 6);
  Q.pop();
  Q.dump();
  
  assert(Q.front() == 2);
  Q.pop();
  Q.dump();

  assert(Q.empty());
}

You can get the whole thing from GitHub.

Now I know what you're thinking: you're thinking "why would you do that when std::stack is just a wrapper around std::deque in almost all STL implementations?" And indeed it doesn't make much sense to use this representation in most situations. However, it does make sense when it's possible to provide an O(1) implementation of turnover() and turn_back_over() for your stacks. Such as with physical stacks of T-shirts.


Physical stacks of T-shirts, with kittens to scale. Note how the T-shirts on the in-stack (left) are upside-down.

Every morning I take a T-shirt off the top of the out-stack and put it on; T-shirts come off the washing line, are folded, and placed upside-down on top of the in-stack. When the out-stack is empty, the in-stack is turned upside-down and placed onto the out-stack. The net effect is an O(1) queue, and even wear on my T-shirts.

Edit: it's been pointed out to me on Reddit that it only appears O(1) because I'm lifting at most one armful of shirts: the asymptotic behaviour is still amortised O(n). On the other hand, I've cut the constant factor down substantially, so it's not all bad news.



While Josie looks for an escape route, Haggis accepts the sudden shift in the Earth's gravity with stoic equanimity.

¹ This originally read "an unusual (AFAIK) implementation", but at least three people have now told me that it's the standard implementation used in the purely-functional world. I'm honestly astonished that people think this is a good idea in general, but hey, I guess I've learned something.

Comments

[kragen.livejournal.com]

Very nice.

It seems like its O(N) worst-case time (for more normal representations of stacks) might matter sometimes, but std::vector has that too, and I think std::deque has it in theory but in practice the O(N) term is always vanishingly small compared to the O(1) term.

You could view the standard ring-buffer FIFO as being an implementation of this algorithm: you start out with an imaginary stack-bottom mark; the items before the stack-bottom mark are a downward-growing stack you're popping off of, while the items after it are an upward-growing stack you're pushing onto. When your popping reaches this mark, you move the imaginary mark to the end of the current items, thus converting them from an upward-growing stack to a downward-growing stack of the same items in reverse order — in O(1) time, since this actually involves executing zero instructions.

But that's a pretty silly way to look at it.

If you make your stacks out of doubly-linked lists, you can do the same kind of trick, with an O(1) reverse that consists of attaching a reverse iterator to the list — but doubly-linked lists work fine as a queue out of the box.

[kragen.livejournal.com]

More laundry algorithms: on the complexity of sock-matching. (http://www.mail-archive.com/kragen-tol@canonical.org/msg00084.html)