何らかの理由で、スタックを使用して何らかの機能を実現する必要がありますが、出力スタックの要素を逆にする必要があります。直接アクセスを実現したいのですstack<char,vector<char>
が、私の提案には誤りがあるかもしれません。STLスタックを使用してC++で出力スタックの要素を効率的に逆にする方法を教えてもらえますか?
5 に答える
一時スタックを使用します。
// On exit the stack 's' will have it's elements reversed.
void reverse_stack(std::stack<int>& s)
{
std::stack<int> tmp;
while (!s.empty())
{
tmp.push(s.pop());
}
s.swap(tmp);
}
使いたくない、または思い通りに使えない場合は、例えば を使ったり、代わりに使ったりしたほうがいいのではないか、などとstack
考えてみてください。do you really need stack?
queue
deque
stack
要素に任意の順序でアクセスしたい場合、そもそもなぜスタックを使用するのでしょうか?
std::vector
orを直接使用std::deque
してから、次のように逆方向に繰り返します
for (auto iter = vec.rbegin(); iter != vec.rend(); ++iter) {
process(*iter);
}
本当に必要な場合は、stack
の基になるコンテナ オブジェクトにアクセスするハックだが正しい方法があります。
通常、これを行うべきではありません。
コンテンツへのアクセスを制限するように特別に設計されたコンテナーを選択して、そのアクセスが本当に必要であると言うのは不適切です。
ニーズを満たすように構築されたコンテナーを選択することをお勧めします。この場合、 a を使用するdeque
方が適切と思われます。
しかし、何かばかげたことをしたい場合は、これがスタックのメンバーに直接アクセスする方法です (これは一時的な逆スタックを構築するために大量のメモリと時間を使用しないことに注意してください。他の回答が示唆しています):
#include <stack>
#include <deque>
#include <cstdlib>
#include <iostream>
using namespace std;
template <class T, class S>
S& Container(stack<T, S>& q) {
struct HackedStack : private stack<T, S> {
static S& Container(stack<T, S>& q) {
return q.*&HackedStack::c;
}
};
return HackedStack::Container(q);
}
int main()
{
stack<int> st;
deque<int> &mems = Container(st);
cout<<"Putting numbers into the stack"<<endl;
for(int i=0;i<20;i++){
int temp=rand();
cout<<temp<<endl;
st.push(rand());
}
cout<<endl<<"Reading numbers in the stack"<<endl;
for(deque<int>::iterator i=mems.begin();i!=mems.end();i++)
cout<<*i<<endl;
cout<<endl<<"Taking numbers out of the stack"<<endl;
while(!st.empty()){
int temp=st.top();
st.pop();
cout<<temp<<endl;
}
return 0;
}
そして、はい、すべてのdeque
参照をvector
参照に変更しても、これは問題なく機能します。しかしdeque
、おそらくスタックで使用するのに適したコンテナーです。
出力を逆にするには、この単純な再帰関数 (疑似コード) を使用します。
void recursiveWalk(Node* current)
{
if (current->next != NULL)
recusiveWalk(current->next);
// do stuff here
}
//call passing top
recursiveWalk(stack->top);
これにより、逆の順序でスタックが構築されます。最後の要素にいると、呼び出しスタックが巻き戻され始め、スタックを下から上に操作できるようになります。