『壹』 用php解決的一個棧的面試題
前言
遇到一道面試題，題目大概意思如下：
使用兩個普通棧實現一個特殊棧，使得pop、push、min三個函數的都是復雜度為O(1)的操作，min函數是獲得當前棧的最小值。
初步想法
1.要實現min函數為(1)操作，當時第一想法是事先需要算好當前最小值,於是會想到用一個值來保存當前棧中最小值元素，然後push和pop操作的時候維護這個值。這樣min,push都是O(1)了，但pop可不是，如果當前彈出的是最小值，需要從新尋找當前元素的最小值，這個就不是o(1)了。
2.而且上面方法沒有用到另外一個棧，於是又想到：在一個棧中存儲排好序的元素，同樣在push和pop操作中維護這個有序堆棧，如圖：
但是這樣的話min操作是O(1)，但是push、pop操作因為要維護這個有序棧，怎麼也想不到一個方法可以O(1)的復雜度。
當時覺得肯定是在另一個棧中緩存最小值信息，但是不知道是因為沒吃飯還是怎麼地，思維就此僵住了。
正確解法
遇到問題解決不了，感覺心裡很不爽，於是吃飯的時候又開始想怎麼充分理由棧的特性，有效的緩存最小值信息，以便min操作使用。
棧操作最大的特性是只能操作棧頂元素，想到那用一個輔助棧緩存每次棧操作時的最小值，不是剛剛好。這樣每次pop操作的時候，兩邊一起彈出就可以；因為輔助棧的棧頂元素最當前棧中的最小值，push操作是也只需要比較入棧元素和輔助棧棧頂元素就可以。這樣push、pop、min都都O(1)操作了。如圖：
文字可能沒說清楚，上代碼，下面是PHP的實現，通過數組來模擬堆棧。
<?php
/**
*
使用一個輔助棧，O(1)復雜度求出棧中的最小數
*
@hack
類中通過數組來模擬堆棧
*
*
@author
laiwenhui
*/
class
strack{
/**
*
數據棧，存儲棧數據；
*
*
@var
array
*/
private
$_arrData
=
array();
/**
*
輔助棧，存儲數據組棧中每層的最下值信息；
*
*
@var
array
*/
private
$_arrMin
=
array();
/**
*
棧頂所在單元
*
*
@var
int
*/
private
$_top=-1;
/**
*
出棧
*
@return
bool|int
*/
public
function
pop(){
if
($this->_top
===
-1){
return
false;
}
array_pop($this->_arrMin);
$this->_top--;
return
array_pop($this->_arrData);
}
/**
*
入棧
*
@param
int
$element
*
@return
bool
*/
public
function
push($element){
$element
=
intval($element);
//如果棧為空，直接入棧
if
($this->_top
===
-1){
array_push($this->_arrData,
$element);
array_push($this->_arrMin,
$element);
$this->_top++;
return
true;
}
//不為空，判斷入棧的值是否比最小棧棧頂小
$min
=
$this->_arrMin[$this->_top];
//比較求出最小值
$currentMin
=
$element
<
$min
?
$element
:
$min;
//當前棧中最小值入棧
array_push($this->_arrMin,
$currentMin);
//數據入棧
array_push($this->_arrData,
$element);
$this->_top++;
return
true;
}
/**
*
求當前棧空間的最小值
*
@return
bool|int
*/
public
function
min(){
if
($this->_top
===
-1){
return
false;
}
return
$this->_arrMin[$this->_top];
}
}
使用如下：
復制代碼
代碼如下:
$obj
=
new
strack();
$obj->push(12);
$obj->push(56);
$obj->push(23);
$obj->push(89);
$obj->push(4);
var_mp($obj->min());
$obj->pop();
var_mp($obj->min());
$obj->push(8);
var_mp($obj->min());
輸出為：
復制代碼
代碼如下:
int(4)
int(12)
int(8)
OK，滿足要求。
你是否有其他更好方法實現，如果有，請告訴我^_^
『貳』 php中的靜態變數和動態變數的區別
動態變數和靜態變數的區別：
1、存儲位置
動態變數：存儲在內存出棧數據區
靜態變數：存儲在全局數據區（靜態數據區）
2、生命期
動態變數：根據你定義的位置確定，比如你在一個函數中定義的，那麼超出該函數范圍變數將失效
靜態變數：程序結束時才釋放
3、作用域
動態變數：同樣的要根據你定義的位置才能確定，和第二點的一樣
靜態變數：當前文件中有效
堆和棧的區分：
堆（Heap）棧（Stack）
1、內存分配方面：
堆：一般由程序員分配釋放， 若程序員不釋放，程序結束時可能由OS回收 。注意它與數據結構中的堆是兩回事，分配方式是類似於鏈表。可能用到的關鍵字如下：new、malloc、delete、free等等。
棧：由編譯器(Compiler)自動分配釋放，存放函數的參數值，局部變數的值等。其操作方式類似於數據結構中的棧。
2、申請方式方面：
堆：需要程序員自己申請，並指明大小。在c中malloc函數如p1 = (char *)malloc(10)；在C++中用new運算符，但是注意p1、p2本身是在棧中的。因為他們還是可以認為是局部變數。
棧：由系統自動分配。 例如，聲明在函數中一個局部變數 int b；系統自動在棧中為b開辟空間。
3、系統響應方面：
堆：操作系統有一個記錄空閑內存地址的鏈表，當系統收到程序的申請時，會遍歷該鏈表，尋找第一個空間大於所申請空間的堆結點，然後將該結點從空閑結點鏈表中刪除，並將該結點的空間分配給程序，另外，對於大多數系統，會在這塊內存空間中的首地址處記錄本次分配的大小，這樣代碼中的delete語句才能正確的釋放本內存空間。另外由於找到的堆結點的大小不一定正好等於申請的大小，系統會自動的將多餘的那部分重新放入空閑鏈表中。
棧：只要棧的剩餘空間大於所申請空間，系統將為程序提供內存，否則將報異常提示棧溢出。
4、大小限制方面：
堆：是向高地址擴展的數據結構，是不連續的內存區域。這是由於系統是用鏈表來存儲的空閑內存地址的，自然是不連續的，而鏈表的遍歷方向是由低地址向高地址。堆的大小受限於計算機系統中有效的虛擬內存。由此可見，堆獲得的空間比較靈活，也比較大。
棧：在Windows下, 棧是向低地址擴展的數據結構，是一塊連續的內存的區域。這句話的意思是棧頂的地址和棧的最大容量是系統預先規定好的，在WINDOWS下，棧的大小是固定的（是一個編譯時就確定的常數），如果申請的空間超過棧的剩餘空間時，將提示overflow。因此，能從棧獲得的空間較小。
5、效率方面：
堆：是由new分配的內存，一般速度比較慢，而且容易產生內存碎片，不過用起來最方便，另外，在WINDOWS下，最好的方式是用VirtualAlloc分配內存，他不是在堆，也不是在棧是直接在進程的地址空間中保留一快內存，雖然用起來最不方便。但是速度快，也最靈活。
棧：由系統自動分配，速度較快。但程序員是無法控制的。
6、存放內容方面：
堆：一般是在堆的頭部用一個位元組存放堆的大小。堆中的具體內容有程序員安排。
棧：在函數調用時第一個進棧的是主函數中後的下一條指令（函數調用語句的下一條可執行語句）的地址然後是函數的各個參數，在大多數的C編譯器中，參數是由右往左入棧，然後是函數中的局部變數。 注意: 靜態變數是不入棧的。當本次函數調用結束後，局部變數先出棧，然後是參數，最後棧頂指針指向最開始存的地址，也就是主函數中的下一條指令，程序由該點繼續運行。
7、存取效率方面：
堆：char *s1 = "Hellow Word"；是在編譯時就確定的；
棧：char s1[] = "Hellow Word"； 是在運行時賦值的；用數組比用指針速度要快一些，因為指針在底層匯編中需要用edx寄存器中轉一下，而數組在棧上直接讀取。
『叄』 php能不能像java那樣列印錯誤堆棧信息到錯誤日誌
PHP 確實不會輸出錯誤堆棧，但通過函數，還是能夠獲取到錯誤堆棧的。
function getBacktrace() {
ob_start();
debug_print_backtrace();
return ob_get_clean();
}
調用上面這個函數取得錯誤堆棧，再用 file_put_contents('log_path', FILE_APPEND); 寫入日誌文件即可。
還有一個辦法：為 PHP 安裝 xdebug 擴展
windows 下的安裝方法 安裝好後，修改 php.ini