スタックとキューのいくつかのアルゴリズム
この記事を読む前に、このブログのhttp://blog.csdn.net/lsjseu/article/details/9351141,STLにおけるシーケンスコンテナのインタフェースおよび内部実装構造を熟知する.
私はまずスタックとキューの基本的な状況について話します:スタックは後進先出の構造で、STLの中で私たちのためにスタックを編んでくれましたが、私たちも自分で実現することができます.通常、2つの実装方式があり、1つは静的配列または動的配列の実装方式であり(ここでは、実装時にスタック空間がいっぱいになった場合、拡張容量を提供する戦略が好ましいことに注意)、2つ目はチェーンテーブルと同じ実装方式である.スタックに適用するアルゴリズムはどれらがありますか:カッコマッチング問題、接尾辞式回転接尾辞式問題、迷宮経路検索問題、非再帰遍歴問題、遡及検索問題、再帰回転非再帰.
キューについてお話しします.キューは先進的な先発構造で、キューには両端キュー、優先順位キュー、循環キューがあります.キューにも2つの簡単な実装方式があり、1つは静的配列または動的配列、1つはチェーンテーブルによって実装される.では、キューはどのアルゴリズムで使われていますか.楊式三角、迷宮最短パス検索(ここが最短パスであることに注意してください.スタックではパスしか検索できません.必ずしも最短ではありません)、広さ優先遍歴問題、階層遍歴問題(実は広さ優先の特例です)、プロセススケジューリング(優先キュー、スタック)、
スタックとキューに関するいくつかのアルゴリズムを集めた.
(1)2つのスタックで1つのキューを構成する.
アルゴリズムは簡単で、1つのスタックが「挿入」を担当し、1つのスタックが「ポップアップ」を担当します.ポップアップされたスタックに要素がない場合は、挿入されたスタックから要素をすべて運んでください.
ここではpopとpushの2つの操作を簡単に実現しただけで、STLのキューに関する他のインタフェースを実現していません.詳細については、このブログを参照してください.
http://blog.csdn.net/lsjseu/article/details/9108711
「Julyマイクロソフト面接百題シリーズ」には、マルチスレッドの下でキューを実現するpopとpush操作があることを覚えています.私の理解ではpopとpush操作の時に「ロック」が必要です.
(2)2つのキューが1つのスタックを実現する
このアルゴリズムは2つのキューで往復する必要がある.以下に簡単に実現する.読めない場合も参考になります.http://blog.csdn.net/lsjseu/article/details/9108711
(3)min関数を含むスタック(剣指offer)
剣指offerで与えられた解答は補助的なスタックを構築して最小値を格納することであり、同様に、プログラミングの美しさにも同様の答えが与えられているが、プログラミングの美しさで与えられた答えは最小値を維持するインデックスである.以下に簡単に実現します.
(4)min関数を含むキュー(プログラミングの美)
実はキューとスタックは上と同じで、簡単に上記の案で解くことはできません.考えればわかる.このプログラミングの美しさには2つの答えがあります.
第1のスキーム:特殊な最大スタックを構築するが、このスタックパッケージにはキューのポインタが含まれており、o(lgn)で挿入と削除を行い、最小値の時間複雑度をo(1)とすることができる.
第2のスキーム:上記の構造min関数を含むスタックを用いて、この特殊なキューを構築する.
(4)印刷スタック
(5)スタック内の要素のソート
何も言わないで、直接プログラムを見ます.もちろんここでは非再帰的な方法に変換して実現することができる.
第5題の考え方に従って、私たちは普段またこの問題に出会って、再帰的な方法で挿入ソートを書くべきです.コードをすぐに書くことができます
(6)スタックの逆順序問題(正確には補助空間として追加のスタックは使用できない)
(7)スタックトップ要素をスタックの下部に移動する(上のアルゴリズムを参照)
(8)スタックの逆順序問題(正確には補助空間として追加のスタックは使用できない)
上の(6)番目の問題は実際にはスタックの反転を実現したが,本題は(7)を参考にスタックの反転を実現したい.
(9)所与のスタックのインスタックシーケンスは、所与のシーケンスがそのシーケンスのアウトスタックシーケンスである可能性があるか否かを判断する.(剣指offer 134ページ)
この問題は補助スタックで解く.
ここでは、所与のスタックのインスタックシーケンス、アウトスタックのシーケンスがいくつあるかを説明します.(これはカトラン数です)類似の問題で、与えられた前シーケンスの遍歴を含めて、中シーケンスの遍歴は何種類ありますか?かっこ一致の問題.1,2,5……詳細参考:http://blog.csdn.net/lsjseu/article/details/11827109
私はまずスタックとキューの基本的な状況について話します:スタックは後進先出の構造で、STLの中で私たちのためにスタックを編んでくれましたが、私たちも自分で実現することができます.通常、2つの実装方式があり、1つは静的配列または動的配列の実装方式であり(ここでは、実装時にスタック空間がいっぱいになった場合、拡張容量を提供する戦略が好ましいことに注意)、2つ目はチェーンテーブルと同じ実装方式である.スタックに適用するアルゴリズムはどれらがありますか:カッコマッチング問題、接尾辞式回転接尾辞式問題、迷宮経路検索問題、非再帰遍歴問題、遡及検索問題、再帰回転非再帰.
キューについてお話しします.キューは先進的な先発構造で、キューには両端キュー、優先順位キュー、循環キューがあります.キューにも2つの簡単な実装方式があり、1つは静的配列または動的配列、1つはチェーンテーブルによって実装される.では、キューはどのアルゴリズムで使われていますか.楊式三角、迷宮最短パス検索(ここが最短パスであることに注意してください.スタックではパスしか検索できません.必ずしも最短ではありません)、広さ優先遍歴問題、階層遍歴問題(実は広さ優先の特例です)、プロセススケジューリング(優先キュー、スタック)、
スタックとキューに関するいくつかのアルゴリズムを集めた.
(1)2つのスタックで1つのキューを構成する.
アルゴリズムは簡単で、1つのスタックが「挿入」を担当し、1つのスタックが「ポップアップ」を担当します.ポップアップされたスタックに要素がない場合は、挿入されたスタックから要素をすべて運んでください.
class MyQueue{
private:
stack<int> insertStack;
stack<int> popStack;
public:
int Dequeue(){
if(popStack.empty()){
if(insertStack.empty())
throw new runtime_error("Null Queue");
while(!insertStack.empty()){//
popStack.push(insertStack.top());
insertStack.pop();
}
}
int result = popStack.top();
popStack.pop();
return result;
}
void Enqueue(int elem){
insertStack.push(elem);
}
}; ここではpopとpushの2つの操作を簡単に実現しただけで、STLのキューに関する他のインタフェースを実現していません.詳細については、このブログを参照してください.
http://blog.csdn.net/lsjseu/article/details/9108711
「Julyマイクロソフト面接百題シリーズ」には、マルチスレッドの下でキューを実現するpopとpush操作があることを覚えています.私の理解ではpopとpush操作の時に「ロック」が必要です.
(2)2つのキューが1つのスタックを実現する
このアルゴリズムは2つのキューで往復する必要がある.以下に簡単に実現する.読めない場合も参考になります.http://blog.csdn.net/lsjseu/article/details/9108711
class MyStack{
private:
queue<int> q1;
queue<int> q2;
public:
int Pop(){
if(q1.empty() && q2.empty())
throw new runtime_error("Null Stack");
int result;
if(q1.empty()){
while(q2.size() != 1){
q1.push(q2.front());
q2.pop();
}
result = q2.front();
q2.pop();
return result;
}
if(q2.empty()){
while(q1.size() != 1){
q2.push(q1.front());
q1.pop();
}
result = q1.front();
q1.pop();
return result;
}
}
void Push(int elem){
if(q1.empty() && q2.empty()){// ，
q1.push(elem);
}
else if(q1.empty())
q2.push(elem);
else
q1.push(elem);
}
};(3)min関数を含むスタック(剣指offer)
剣指offerで与えられた解答は補助的なスタックを構築して最小値を格納することであり、同様に、プログラミングの美しさにも同様の答えが与えられているが、プログラミングの美しさで与えられた答えは最小値を維持するインデックスである.以下に簡単に実現します.
template<class T>
class MinStack{
private:
stack<T> st;
stack<T> minst;
public:
void Push(T t){
st.push(t);
if(minst.empty() || (t<minst.top()))// T "<"
minst.push(t);
else
minst.push(minst.top());
}
T Pop(){
int popNum;
if(!st.empty()){
popNum = st.top();
st.pop();
minst.pop();
}
else
throw new runtime_error("Empty Stack");
return popNum;
}
T GetMin(void)const{
return minst.top();
}
T IsEmpty()const{
return st.empty();
}
};(4)min関数を含むキュー(プログラミングの美)
実はキューとスタックは上と同じで、簡単に上記の案で解くことはできません.考えればわかる.このプログラミングの美しさには2つの答えがあります.
第1のスキーム:特殊な最大スタックを構築するが、このスタックパッケージにはキューのポインタが含まれており、o(lgn)で挿入と削除を行い、最小値の時間複雑度をo(1)とすることができる.
第2のスキーム:上記の構造min関数を含むスタックを用いて、この特殊なキューを構築する.
template<class T>
class MinStack{
private:
stack<T> st;
stack<T> minst;
public:
void Push(T t){
st.push(t);
if(minst.empty() || (t<minst.top()))// T "<"
minst.push(t);
else
minst.push(minst.top());
}
T Pop(){
int popNum;
if(!st.empty()){
popNum = st.top();
st.pop();
minst.pop();
}
else
/*throw std::runtime_error("Empty Stack");*/
cout<<"Null Stack"<<endl;
return popNum;
}
T GetMin(void)const{
return minst.top();
}
T IsEmpty()const{
return st.empty();
}
};
template<class T>
class MinQueue{
private:
MinStack<T> sta;
MinStack<T> stb;
public:
T GetMin()const{
if(sta.IsEmpty() && stb.IsEmpty())
throw new runtime_error("Null Stack");
else if(!sta.IsEmpty() && stb.IsEmpty())
return sta.GetMin();
else if(sta.IsEmpty() && !stb.IsEmpty())
return stb.GetMin();
else return min(sta.GetMin(),stb.GetMin());
}
void Enqueue(T t){
sta.Push(t);
}
T Dequeue(){
if(stb.IsEmpty()){
while(!sta.IsEmpty()){
stb.Push(sta.Pop());
}
}
return stb.Pop();
}
};(4)印刷スタック
#include <iostream>
#include <stack>
using namespace std;
void PrintStack(stack<int>& st)
{
if(st.empty())
return;
int top = st.top();
cout<<top<<" ";
st.pop();
PrintStack(st);
st.push(top);
}
int main()
{
stack<int> st;
st.push(1);
st.push(2);
st.push(3);
PrintStack(st);
cout<<endl;
PrintStack(st);// ，
system("pause");
return 0;
}(5)スタック内の要素のソート
何も言わないで、直接プログラムを見ます.もちろんここでは非再帰的な方法に変換して実現することができる.
#include <iostream>
#include <stack>
using namespace std;
void PrintStack(stack<int>& st)
{
if(st.empty())
return;
int top = st.top();
cout<<top<<" ";
st.pop();
PrintStack(st);
st.push(top);
}
void SortStack(stack<int>& st)
{
if(st.empty())return;
int topNum = st.top();
st.pop();
SortStack(st);// ，
stack<int> tempSt;
while(!st.empty() && st.top()>topNum){
tempSt.push(st.top());
st.pop();
}
st.push(topNum);
while(!tempSt.empty()){
st.push(tempSt.top());
tempSt.pop();
}
}
int main()
{
stack<int> st;
st.push(1);
st.push(4);
st.push(3);
PrintStack(st);
SortStack(st);
cout<<endl;
PrintStack(st);// ，
system("pause");
return 0;
}第5題の考え方に従って、私たちは普段またこの問題に出会って、再帰的な方法で挿入ソートを書くべきです.コードをすぐに書くことができます
#include <iostream>
#include <stack>
#include <cassert>
using namespace std;
void PrintArr(int arr[],int len){
assert(arr && len>=0);
for(int i=0; i<len; ++i){
cout<<arr[i]<<" ";
}
cout<<endl;
}
void InsertSortRecursively(int arr[],int index){
assert(arr && index>=0);
if(index == 0) return;
int base = arr[index];
InsertSortRecursively(arr,index-1);//
int i = index-1;
while(i>=0 && arr[i]>base){
arr[i+1] = arr[i];
i--;
}
arr[i+1] = base;
}
int main()
{
const int LEN = 4;
int arr[LEN] = {3,2,4,5};
PrintArr(arr,LEN);
InsertSortRecursively(arr,LEN-1);
PrintArr(arr,LEN);
system("pause");
return 0;
}(6)スタックの逆順序問題(正確には補助空間として追加のスタックは使用できない)
#include <iostream>
#include <stack>
using namespace std;
void PrintStack(stack<int>& st)
{
if(st.empty())
return;
int top = st.top();
cout<<top<<" ";
st.pop();
PrintStack(st);
st.push(top);
}
void MoveButtomToTop(stack<int>& st)//
{
if(st.empty())return;
int top1 = st.top();//
st.pop();
if(!st.empty()){
MoveButtomToTop(st);//
int top2 = st.top();
st.pop();
st.push(top1);
st.push(top2);// top1 top2
return;
}
st.push(top1);
}
void ReverseStack(stack<int>& st)
{
if(st.empty())return;
MoveButtomToTop(st);
int topNum = st.top();
st.pop();
ReverseStack(st);
st.push(topNum);
}
int main()
{
stack<int> st;
st.push(1);
st.push(4);
st.push(3);
PrintStack(st);
ReverseStack(st);
cout<<endl;
PrintStack(st);
system("pause");
return 0;
}(7)スタックトップ要素をスタックの下部に移動する(上のアルゴリズムを参照)
#include <iostream>
#include <stack>
using namespace std;
void PrintStack(stack<int>& st)
{
if(st.empty())
return;
int top = st.top();
cout<<top<<" ";
st.pop();
PrintStack(st);
st.push(top);
}
void MoveTopToButtom(stack<int>& st){
if(st.empty())return;
int firstTop = st.top();
st.pop();
if(!st.empty()){
int secondTop = st.top();
st.pop();
st.push(firstTop);
MoveTopToButtom(st);
st.push(secondTop);
return;
}
st.push(firstTop);
}
int main()
{
stack<int> st;
st.push(1);
st.push(4);
st.push(3);
PrintStack(st);
MoveTopToButtom(st);
cout<<endl;
PrintStack(st);
system("pause");
return 0;
}(8)スタックの逆順序問題(正確には補助空間として追加のスタックは使用できない)
上の(6)番目の問題は実際にはスタックの反転を実現したが,本題は(7)を参考にスタックの反転を実現したい.
#include <iostream>
#include <stack>
using namespace std;
void PrintStack(stack<int>& st)
{
if(st.empty())
return;
int top = st.top();
cout<<top<<" ";
st.pop();
PrintStack(st);
st.push(top);
}
void MoveTopToButtom(stack<int>& st){ //
if(st.empty())return;
int firstTop = st.top();
st.pop();
if(!st.empty()){
int secondTop = st.top();
st.pop();
st.push(firstTop);
MoveTopToButtom(st);
st.push(secondTop);
return;
}
st.push(firstTop);
}
void ReverseStack(stack<int>& st){
if(st.empty())return;
int topNum = st.top(); //
st.pop();
ReverseStack(st);// ，
st.push(topNum);//
MoveTopToButtom(st);//
}
int main()
{
stack<int> st;
st.push(1);
st.push(2);
st.push(3);
PrintStack(st);
ReverseStack(st);
cout<<endl;
PrintStack(st);
system("pause");
return 0;
}(9)所与のスタックのインスタックシーケンスは、所与のシーケンスがそのシーケンスのアウトスタックシーケンスである可能性があるか否かを判断する.(剣指offer 134ページ)
この問題は補助スタックで解く.
#include <iostream>
#include <stack>
#include <cassert>
#include <string>
using namespace std;
bool IsPopOrder(int pushSeq[],int popSeq[],int len)
{
assert(pushSeq && popSeq && len>0);
stack<int> st;
int i,j = 0;
for(i=0; i<len; ++i){
int popNum = popSeq[i];
while(st.empty() || st.top()!=popNum){
st.push(pushSeq[j++]);
if(j == len)break;
}
if(st.top() != popNum)
break;
st.pop();
}
if(st.empty() && i==len)
return true;
else return false;
}
int main()
{
const int SIZE = 5;
int pushSeq[SIZE] = {1,2,3,4,5};
int popSeq[SIZE] = {4,5,3,2,1};
string result = IsPopOrder(pushSeq,popSeq,SIZE)?"True":"False";
cout<<result<<endl;
system("pause");
return 0;
}ここでは、所与のスタックのインスタックシーケンス、アウトスタックのシーケンスがいくつあるかを説明します.(これはカトラン数です)類似の問題で、与えられた前シーケンスの遍歴を含めて、中シーケンスの遍歴は何種類ありますか?かっこ一致の問題.1,2,5……詳細参考:http://blog.csdn.net/lsjseu/article/details/11827109