2つのスタックで1つのキューを実現する機能&&2つのキューで1つのスタックを実現する機能&&コードインスタンス
2330 ワード
2つのスタックで1つのキューの機能を実現
データ構造の説明:
桟:先入後出FILO
キュー:先入先出FIFO
実現方式一、具体:
キュー入列:スタックA入スタック;
例:A.B.C.Dを列に入れ、スタックの頂上からスタックの底まで順に:D C B A;
キューの列:スタック要素の個数が1であるかどうかを判断し、真であれば、ポップアップする.
偽の場合、スタックAのすべての要素はスタックPOPを出し、スタックBに圧入する.スタックBスタックトップ要素POP;スタックBのすべての要素はスタックAに圧入される.
例:スタックA弾スタック、スタックB圧スタック、スタックBはスタックの頂上からスタックの底まで順に:A B C D;スタックトップ要素Aをスタックに弾き、残りの要素をスタックAに戻す.スタックAはスタックの頂上からスタックの底まで順に:B C D;
実現方式二、具体的に:
キュー入列:スタック要素の個数が1であるかどうかを判断し、真であれば、ポップアップする.
偽の場合、スタックAのすべての要素はスタックPOPを出し、スタックBに圧入する.新しい要素をスタックAに押し込む.スタックBのすべての要素はスタックAに圧入される.
キューの列:スタックAのスタック;
終了、まとめ:キューのエンキューとアウトペア操作を実現しました.
2つのキューで1つのスタックの機能を実現
実現方式一、具体:
インスタック:すべての要素がキューAに順次入力されます.
例:A.B.C.Dをスタックに入れ、キューの末尾からキューの首部まで順に:D C B A;
出桟:スタック要素の個数が1であるかどうかを判断し、真であれば、キューAが列を出す.
偽の場合、キューAのすべての要素はキューから出て、キューBに入って、最後の要素はキューBに入っていないので、その要素を出力します.キューBのすべての要素がキューAに入る.
例:D C B Aを列に出し、Dを出力し、C B AはキューBに入り、最後にキューAに戻る.後進先出を実現した.
実現方式二、具体的に:
入桟:方式の出桟と似ている
出桟:方式一入桟と似ている
終了、まとめ:スタックのインスタックとアウトスタック操作を実現しました.
コードインスタンス
データ構造の説明:
桟:先入後出FILO
キュー:先入先出FIFO
実現方式一、具体:
キュー入列:スタックA入スタック;
例:A.B.C.Dを列に入れ、スタックの頂上からスタックの底まで順に:D C B A;
キューの列:スタック要素の個数が1であるかどうかを判断し、真であれば、ポップアップする.
偽の場合、スタックAのすべての要素はスタックPOPを出し、スタックBに圧入する.スタックBスタックトップ要素POP;スタックBのすべての要素はスタックAに圧入される.
例:スタックA弾スタック、スタックB圧スタック、スタックBはスタックの頂上からスタックの底まで順に:A B C D;スタックトップ要素Aをスタックに弾き、残りの要素をスタックAに戻す.スタックAはスタックの頂上からスタックの底まで順に:B C D;
実現方式二、具体的に:
キュー入列:スタック要素の個数が1であるかどうかを判断し、真であれば、ポップアップする.
偽の場合、スタックAのすべての要素はスタックPOPを出し、スタックBに圧入する.新しい要素をスタックAに押し込む.スタックBのすべての要素はスタックAに圧入される.
キューの列:スタックAのスタック;
終了、まとめ:キューのエンキューとアウトペア操作を実現しました.
2つのキューで1つのスタックの機能を実現
実現方式一、具体:
インスタック:すべての要素がキューAに順次入力されます.
例:A.B.C.Dをスタックに入れ、キューの末尾からキューの首部まで順に:D C B A;
出桟:スタック要素の個数が1であるかどうかを判断し、真であれば、キューAが列を出す.
偽の場合、キューAのすべての要素はキューから出て、キューBに入って、最後の要素はキューBに入っていないので、その要素を出力します.キューBのすべての要素がキューAに入る.
例:D C B Aを列に出し、Dを出力し、C B AはキューBに入り、最後にキューAに戻る.後進先出を実現した.
実現方式二、具体的に:
入桟:方式の出桟と似ている
出桟:方式一入桟と似ている
終了、まとめ:スタックのインスタックとアウトスタック操作を実現しました.
コードインスタンス
//
template<class T>
class deque_from_stack
{
public:
deque_from_stack()
{
size = 0;
}
void push(T& element)
{
stack_one.push(element);
size = stack_one.size();
}
T pop()
{
assert(this->size > 0);
T result = 0 ;
if(1 == this->size)
{
result = stack_one.top();
stack_one.pop();
this->size = 0;
return result;
}
if(this->size > 1)
{
while(stack_one.size())
{
stack_two.push(stack_one.top());
stack_one.pop();
}
result = stack_two.top();
stack_two.pop();
while(stack_two.size())
{
stack_one.push(stack_two.top());
stack_two.pop();
}
this->size--;
return result;
}
}
public:
stack<T> stack_one;// 1
stack<T> stack_two;// 2
size_t size;//
};
int main(int argc, char* argv[])
{
int i = 0;
//
cout << "deque_from_stack :" <<endl;
deque_from_stack<int>d_s_s;
for (i = 1; i < 5; i++)
{
cout << i << " come in " << endl;
d_s_s.push(i);
}
for (i = 1; i < 5; i++)
{
cout << d_s_s.pop() << " go out " << endl;
}
cout << endl;
}