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
#include

// This code brought to you by 10yo Talisker

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

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

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

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

template
void ts_queue::pop()
{
if (out.empty()) {
turnover();
}
out.pop();
}

template
int ts_queue::size()
{
return in.size() + out.size();
}

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

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

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

// A couple of debugging functions, non-standard

template
void ts_queue::dump_stack(std::stack& st)
{
using namespace std;
stack 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
void ts_queue::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
#include "queue.h"

int main() {
ts_queue 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.