![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
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++:
Here's a quick test harness, nicked from here:
Now I know what you're thinking: you're thinking "why would you do that when
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.
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.
Tags:
no subject
no subject
no subject
Are your t-shirts immutable?
no subject
no subject
no subject
no subject
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.
no subject
no subject
no subject
no subject
no subject
no subject
no subject
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 areturnbeforeout.top()? And similarly forts_queue::back()?no subject
no subject
An interesting bit of g++ behavior, cool to learn about it :-)
no subject
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 (http://blog.plover.com/prog/perl/undefined.html).
Интересно читать
переводчик скачать без регистрации
торрент трекер быстро скачать [url=http://tapdivamal.tk/9-film-skachat-torrent-390.html]9 фильм скачать торрент[/url] учебник физика перышкин 7 скачать скачать сумерки 4 фильм фабрика звезд 5 скачать криминальная россия скачать торрент [url=http://jiaperhyaspur.tk/nokia-5230-igry-skachat-torrent-706.html]nokia 5230 игры скачать торрент[/url] скачать фильм прорыв торрент александр бородач скачать на телефон скачать vice city rus
скачать электронные книги формата fb2 ххх скачать без регистрации [url=http://weahaltirest.tk/skachat-igru-gta-zima-torrent-706.html]скачать игру gta зима торрент[/url] скачать windows 7 сборник скачать программу для нарезки trustedinstaller windows 7 скачать [url=http://signcalpeni.tk/pinnacle-studio-skachat-russkaya-versiya-90.html]pinnacle studio скачать русская версия[/url] скачать игру diablo 2
домашнее порно скачать видео [url=http://sergastdaren.tk/povtoryayushii-homyak-na-kompyuter-skachat-286.html]повторяющий хомяк на компьютер скачать[/url] microsoft flight 2010 скачать скачать музыку lady via pci драйвер скачать тетки порно скачать [url=http://verplatourrio.tk/skachat-bez-registracii-pesni-vintazh-711.html]скачать без регистрации песни винтаж[/url] скачать magic 4 скачать порно по категориям скачать фильм проклятая
скачать игру ферма 4 скачать worms 2 русская версия [url=http://staranserne.tk/online-tvx-registracionnyi-klyuch-skachat-807.html]online tvx регистрационный ключ скачать[/url] книга миллионер скачать скачать песню птица скачать книгу по эксплуатации автомобиля [url=http://tiotratollog.tk/cats-skachat-na-telefon-297.html]cats скачать на телефон[/url] скачать форму 2 ндфл 2010
скачать монтаж видео русская версия [url=http://staranserne.tk/skachat-noch-muzyka-708.html]скачать ночь музыка[/url] скачать xp sp3 2010 торрент скачать драйвер по коду скачать порно с блондинками скачать гиа 7 класс [url=http://serticonsbo.tk/so-5-skachat-235.html]со 5 скачать[/url] скачать темы на телефон 5230 скачать 5 1 3 сентября скачать
портал игра скачать торрент скачать 3ds max rus [url=http://hieristersdark.tk/skachat-fifa-10-cherez-torrent-506.html]скачать fifa 10 через торрент[/url] скачать темы для 2700 как скачать скайп на телефон скачать музыку radio edit [url=http://tapdivamal.tk/skachat-yazyk-css-434.html]скачать язык css[/url] скачать нод32 4
скачать авто для gta 4 [url=http://staranserne.tk/brutusa2-russkaya-versiya-skachat-318.html]brutusa2 русская версия скачать[/url] скачать ru видео фотошоп для виндовс 7 скачать скачать драйвер geforce 9500 скачать скайп 4.2 [url=http://nutrerihel.tk/cs3-russkaya-versiya-skachat-426.html]cs3 русская версия скачать[/url] coreldraw 5 скачать скачать новые альбомы linkin park скачать презентацию на тему лекарства
Спасибо за инфу