アルゴリズム学習一---min関数を含むスタックを設計する

今学期は大学3年生になって、身の回りの学友はすべて実习を探すつもりで、就职の圧力はとても大きいと言って、最近就职の笔记试験を准备するため、とても长い时间はすべてブログを书いていません.最近すべてC++とデータの构造を学んで、今アルゴリズムに接触して、以前のアルゴリズムの教室はよく上がっていないで、ただ実験の问题をしただけで百になって、大きい升格がなくて、だから今笔记试験の准备の时にアルゴリズムをよく补って、そこでここで自分の学习の过程を记录します.
今日は興味深いアルゴリズムを学びました.マイクロソフトの面接100題のテーマです.タイトルは以下の通りです.
min関数を含むスタックを設計します.スタックのデータ構造を定義し、スタックの最小要素を得るためにmin関数を追加する必要があります.要求関数min,push,popの時間複雑度はいずれもO(1)である.
まず、このアルゴリズムの要件について説明します.
スタックにデータを挿入する場合:2 6 4 1 5、データを挿入するたびにmin関数を呼び出すと、このスタックの最小値が得られます.さらにmin,push,popの時間複雑度はいずれも定数レベルであることが要求される.
これにより、補助スタックを用いる方法を選択して実現することができ、補助スタックは最小値の位置を保存し、空間消費で効率的な時間複製度を取り替えることができる.
2つのベクトルを使用してデータを保存するデータ構造が設計され、ベクトル1はスタックのデータを保存し、ベクトル2は現在のシーケンス1の最小値の位置を保存します.
クラスの設計は次のとおりです.

template <class T>
class StackMin
{
public:
	void Push(T);
	void Pop();
	void display(ostream &out) const;
	vector<T> datas;
	vector<size_t> minStack;
	T min() const;
};

例えば、シーケンス2 6 4 1 5を挿入する手順は、以下の通りである.
A             B
5 3/最小値は1
1 3//このとき最小値が変化し、1が最小値となるので、1の下付き3をベクトル2に押し込む
4 0//このとき2は最小値です
6 0//このとき2は最小値です
2 0//このときは要素が1つしかないので、最小値はベクトル1の位置0です.
実装された擬似コード

push data ==> A
if data is minimun or B is empty
     then push data's subscript in A ==> B

C++実装

template <class T>
void StackMin<T>::Push(T data)
{
	datas.push_back(data);

	if(minStack.empty() || data < datas[minStack.back()])
	{
		minStack.push_back(datas.size()-1);
	}
}

popのプロセスは次のとおりです.
A              B
5は最小値ではないので変化しません
1は1の下付き文字--3をポップアップし、最小値がポップアップされたため、Aの中の最小値が変化した.
4は最小値ではないので変更はありません
6は変化しません.6は最小値ではありません.
2は2の下付き文字--0をポップアップします.このとき2は最小値ですから.

if A is empty
    then do nothing
if A.topValue == A[B.topvalue]
    then pop one value from B
pop one value from A

C++実装

template <class T>
void StackMin<T>::Pop()
{
	assert(!datas.empty());

	if(datas.back() == datas[minStack.back()])
	{
		minStack.pop_back();
	
	}
	datas.pop_back();
}

min関数の実現は,ベクトルBのスタックトップ要素をベクトルAの下付きとして取り出し,アクセスベクトルAを現在の最小値とする.

if A is empty or B is empty
    then do nothing
return A[B.topValue]

C++実装

template <class T>
T StackMin<T>::min() const
{
	assert(!datas.empty() && !minStack.empty());
	return datas[minStack.back()];
}

以上が操作プロセス全体の実現の分析と擬似コードである.
今回の学習アルゴリズムの体得は、アルゴリズムが重要で、面白くて、アルゴリズムをする前に分析してからコードを実現しなければならなくて、すでに時間を節約してもっと深くアルゴリズムの過程を体得しました.ここで自分がアルゴリズムを学ぶ過程を書いて、私はやはり1人のおかずが迫って、各位がよけいに指導することを望みます!