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.