You are viewing pozorvlak

Beware of the Train - Building a queue with two stacks [entries|archive|friends|userinfo]
pozorvlak

[ website | My Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| My moblog Hypothetical, the place to be My (fairly feeble) website ]

Building a queue with two stacks [Mar. 31st, 2011|12:11 pm]
Previous Entry Add to Memories Share Next Entry
[Tags|, , , , , ]

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.
linkReply

Comments:
[User Picture]From: stronae
2011-03-31 12:21 pm (UTC)

(Link)

I love the application to laundry, and I also love the kitties. Kitties!
[User Picture]From: pozorvlak
2011-03-31 12:33 pm (UTC)

(Link)

They're gorgeous, aren't they? We've had them for just over two months now (since Burns Night, which is part of the reason we called him Haggis).
[User Picture]From: fanf
2011-03-31 03:52 pm (UTC)

(Link)

This is the standard implementation of a queue in functional programming languages :-)

Are your t-shirts immutable?
[User Picture]From: pozorvlak
2011-03-31 04:21 pm (UTC)

(Link)

They're very rarely modified, unless you count getting them dirty.
[User Picture]From: fanf
2011-03-31 04:27 pm (UTC)

(Link)

That's just a garbage collection problem, isn't it? At least, for very small garbage objects.
[User Picture]From: pozorvlak
2011-03-31 05:02 pm (UTC)

(Link)

:-)
[User Picture]From: kragen
2011-03-31 06:24 pm (UTC)

(Link)

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.
From: (Anonymous)
2011-03-31 09:05 pm (UTC)

(Link)

This was in the first or so homework of the first data structures compsci class I took back in the day.
From: (Anonymous)
2011-04-01 10:26 am (UTC)

(Link)

When the out-stack is empty, why not just swap the stack references? The out-stack becomes the new in-stack, and the old-instack becomes the new out-stack. Then, proceed as usual. (Resembles stop n' copy GC algorithm :)
[User Picture]From: pozorvlak
2011-04-01 11:02 am (UTC)

(Link)

Because then the in-stack would be upside-down :-)
From: (Anonymous)
2011-04-01 11:55 am (UTC)

(Link)

Oops. I couldn't take wearing my Sunday t-shirt on a Thursday ...
[User Picture]From: pozorvlak
2011-04-01 03:55 pm (UTC)

(Link)

I'm not so worried about that; I guess your system does have the desired property that all T-shirts are worn approximately as often as each other.
[User Picture]From: necaris
2011-04-01 03:46 pm (UTC)

(Link)

Haha, brilliant. Love the laundry application too.

It's been a while since I last worked with C++, and perhaps I'm being a bit thick, but in ts_queue::front() don't you need a return before out.top()? And similarly for ts_queue::back()?
[User Picture]From: pozorvlak
2011-04-01 03:54 pm (UTC)

(Link)

Huh. Failure to have a return statement in a value-returning function apparently results in undefined behaviour; obviously g++ handles this like Perl (return the value of the last expression evaluated) because the tests pass...
[User Picture]From: necaris
2011-04-02 03:23 am (UTC)

(Link)

Returning the value of the last evaluated expression? Seems awfully functional to me ;-)

An interesting bit of g++ behavior, cool to learn about it :-)
[User Picture]From: pozorvlak
2011-04-02 10:30 am (UTC)

(Link)

Bear in mind that RMS is a Lisper :-)

Also bear in mind the usual warning about relying on undefined behaviour in C or C++: a conformant compiler is allowed to do anything on encountering an undefined construct, up to and including erasing all your files or causing demons to fly out of your nose.