C語言強化（二）設計可以求最小元素的棧
如何使用棧“先進後出的特性如何巧妙地借助輔助棧如何在結構體中定義可共享的靜態成員變量
題目 
看似很簡單的求最小值函數，思路有很多很多。筆者首先想到每次push入棧都進行一次排序，使這個棧的棧頂永遠是最小元素，然後就發現這是一個很蠢很蠢的想法，第一這樣做會改變了棧的結構，第二不滿足題目對時間復雜度的要求。 愚蠢歸愚蠢，還是有點用的。既然不能改變原來棧的結構，那為何不弄倆棧呢？輔助棧的想法由此而出。 接下來是時間復雜度的問題，顯然每次都進行排序是不可行的了，那麼是否可以記錄保存每個最小值的下一個最小值呢，也就是說，當我當前這個最小值被pop出去後，我要知道下一個最小值是哪個。這時棧的【先進後出】特性就派上用場了。
頭腦風暴到此結束。下面是具體思路 牢牢把握住棧【先進後出】的特性，模擬各種實際情況，得出算法
輔助棧： 棧結構體中添加一個輔助棧，這裡稱為【最小值棧】，存儲最小值的歷史記錄，所以該最小值棧的棧頂即為當前棧的最小元素
算法實現： --push 當push進來的元素值大於、等於最小值棧的棧頂，最小值棧不變，因為根據棧的特性，只有當前最小值元素上面的所有元素都出去的時候，該最小值元素才能pop出去，否則該最小值元素用於是最小值。
反之，當push進來的元素值小於最小值棧的棧頂，則將該元素放進最小值棧。
--pop 當pop出去的元素不是最小值棧棧頂，則最小值棧不變
如果pop出去的值為當前最小值，則最小值棧也pop出一個元素，此時最小值棧的棧頂就是下一個最小值元素
源代碼
#include
#include
#include
using namespace std;
/**
題目：
定義棧的數據結構 要求添加一個min函數，找出棧的最小元素
要求min、push、pop函數的時間復雜度都為O(1)
思路
牢牢把握住棧【先進後出】的特性，模擬各種實際情況，得出算法
棧結構體中添加一個輔助棧，這裡稱為【最小值棧】，存儲最小值的歷史記錄
所以該最小值棧的棧頂即為當前棧的最小元素
當push進來的元素值大於、等於最小值棧的棧頂，最小值棧不變
因為根據棧的特性，只有當前最小值元素上面的所有元素都出去的時候，該最小值元素才能pop出去
反之，則將該元素放進最小值棧
當pop出去的元素不是最小值棧棧頂，則最小值棧不變
反之，最小值棧pop出棧頂
這樣如果pop出去的值為當前最小值，則最小值棧也pop出一個元素
此時最小值棧的棧頂就是下一個最小值元素
*/
/*
創建棧結點結構體
value 值
nextNode 下一個結點
push() 入棧函數
pop() 出棧函數
min() 求最小值函數
push2() 入棧並且求最小值
pop2() 出棧並且求最小值
*/
struct StackNode{
int value;
static StackNode * minNode;
StackNode * nextNode;
/**
push() 入棧函數
value 入棧的值
返回 棧頂
*/
StackNode * push(int value){
StackNode * top = new StackNode();
if(NULL!=this){
top=this;
StackNode * push = new StackNode();
push->value=value;
push->nextNode=top;
top=push;
}else{
top->nextNode=NULL;
top->value=value;
}
cout<<入棧,value=<value<nextNode;
}
else{
cout<<棧已經為空<value){
cout<<最小值棧入棧<push(value);
}
}else{
//空，則直接放進去
cout<push(value);
}
}else{
//pop
//非空且pop的值等於最小值，則最小值棧pop
if((NULL!=minNode)&&(minNode->value==value)){
cout<<最小值棧出棧<pop();
}
}
if(NULL!=minNode)
cout<<現在棧的最小值value=<value<push(value);
this->min(true,value);
return node;
}
//pop+min
StackNode* pop2(){
int value = this->value;
StackNode* node=this->pop();
this->min(false,value);
return node;
}
};
//結構體靜態變量初始化！
StackNode * StackNode::minNode = NULL;
StackNode * stack;
void main()
{
stack=stack->push2(5);
stack=stack->push2(2);
stack=stack->push2(4);
stack=stack->push2(1);
stack=stack->push2(1);
while(NULL!=stack){
stack=stack->pop2();
}
system(pause);
}
效果圖
總結，所有與棧有關的題目，都記住這四個字——”先進後出“
