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