? ? ? ??棧（stack）在計算機科學中是限定僅在表尾進行插入或刪除操作的線性表。棧是一種數據結構，它按照后進先出的原則存儲數據，先進入的數據被壓入棧底，最后的數據在棧頂，需要讀數據的時候從棧頂開始彈出數據。棧是只能在某一端插入和刪除的特殊線性表。用桶堆積物品，先堆進來的壓在底下，隨后一件一件往堆。取走時，只能從上面一件一件取。堆和取都在頂部進行，底部一般是不動的。棧就是一種類似桶堆積物品的數據結構，進行刪除和插入的一端稱棧頂，另一堆稱棧底。插入一般稱為進棧，刪除則稱為退棧。 棧也稱為后進先出表。

? ? ? ??

基本概念

? ? ? ??首先系統或者數據結構棧中數據內容的讀取與（壓入push和 彈出pop）是兩回事！插入是增加數據彈出是刪除數據 ，這些操作只能從棧頂即最低地址作為約束的接口界面入手操作 ，但讀取棧中的數據 是隨便的 沒有接口約束之說。很多人都誤解這個理念從而對棧產生困惑。[1]而系統棧在計算機體系結構中 又起到一個跨部件交互的媒介區域的作用 即 cpu 與內存的交流通道 ，cpu只從系統給我們自己編寫的應用程序所規定的棧入口線性地讀取執行指令， 用一個形象的詞來形容它就是pipeline（管道線、流水線）。cpu內部交互具體參見 EU與BIU的概念介紹。
? ? ? ??

棧 特性

? ? ? ?? 棧作為一種數據結構，是一種只能在一端進行插入和刪除操作的特殊線性表。它按照后進先出的原則存儲數據，先進入的數據被壓入棧底，最后的數據在棧頂，需要讀數據的時候從棧頂開始彈出數據（最后一個數據被第一個讀出來）。棧具有記憶作用，對棧的插入與刪除操作中，不需要改變棧底指針。

? ? ? ?? 棧是允許在同一端進行插入和刪除操作的特殊線性表。允許進行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動；棧中元素個數為零時稱為空棧。插入一般稱為進棧（PUSH），刪除則稱為退棧（POP）。棧也稱為后進先出表。

? ? ? ?? 棧可以用來在函數調用的時候存儲斷點，做遞歸時要用到棧！

棧與計算機
? ? ? ?? 在計算機系統中，棧則是一個具有以上屬性的動態內存區域。程序可以將數據壓入棧中，也可以將數據從棧頂彈出。在i386機器中，棧頂由稱為esp的寄存器進行定位。壓棧的操作使得棧頂的地址減小，彈出的操作使得棧頂的地址增大。
? ? ? ??

? ? ? ?? 棧在程序的運行中有著舉足輕重的作用。最重要的是棧保存了一個函數調用時所需要的維護信息，這常常稱之為堆棧幀或者活動記錄。堆棧幀一般包含如下幾方面的信息：
? ? ? ?? ? ? ? ?? 1．函數的返回地址和參數
? ? ? ?? ? ? ? ?? 2． 臨時變量：包括函數的非靜態局部變量以及編譯器自動生成的其他臨時變量。

棧算法

? ? ? ?? 進棧算法

? ? ? ?? ? ? ? ?? ①若TOP≥n時，則給出溢出信息，作出錯處理（進棧前首先檢查棧是否已滿，滿則溢出；不滿則作②）；
? ? ? ?? ? ? ? ?? ②置TOP=TOP+1（棧指針加1，指向進棧地址）；
? ? ? ?? ? ? ? ?? ③S(TOP)=X，結束（X為新進棧的元素）；

? ? ? ?? 退棧算法
? ? ? ?? ? ? ? ?? ①若TOP≤0，則給出下溢信息，作出錯處理(退棧前先檢查是否已為空棧， 空則下溢；不空則作②)；
? ? ? ?? ? ? ? ?? ②X=S(TOP)，（退棧后的元素賦給X）；
? ? ? ?? ? ? ? ?? ③TOP=TOP-1，結束（棧指針減1，指向棧頂）。
? ? ? ??

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
以后的筆記瀟汀會盡量詳細講解一些相關知識的，希望大家繼續關注、支持、頂起我的博客。
你們的關注就是我的動力，本節筆記到這里就結束了。


瀟汀一有時間就會把自己的學習心得，覺得比較好的知識點寫出來和大家一起分享。
編程開發的路很長很長，非常希望能和大家一起交流，共同學習，共同進步。
如果文章中有什么疏漏的地方，也請大家留言指正。也希望大家可以多留言來和我探討編程相關的問題。
最后，謝謝你們一直的支持~~~
------------------------------------------
Country: China
Tel: +86-152******41
QQ: 451292510
E-mail: xiaoting_chen2010@163.com
------------------------------------------


? ? ? ?C++完整個代碼示例（代碼在VS2005下測試可運行）

? ? ? ?

AL_StackSeq.h

?

    /**

  @(#)$Id: AL_StackSeq.h 31 2013-09-05 09:02:18Z xiaoting $

  @brief     Stack (stack) in computer science is limited only in the end of the table to insert or delete operations linear form. 

  A stack is a data structure that in accordance with the principle of LIFO data storage, data is first pushed into the end of the 

  last data in the stack, you need to read the data when the data from the topmost pop. The stack is only one end of the inserted 

  and deleted special linear form. Buckets stacked items, first came under pressure in the heap, followed by a one to the heap. 

  Removed, only a one taken from above. Take the top of the heap and are carried at the bottom of the general is not moving. Stack 

  is a similar data structure barrels stacked items, delete and insert one end of said stack, said another pile bottom of the stack. 

  Insert commonly known as the push to delete is called the stack back. Also known as LIFO stack table.



  @Author $Author: xiaoting $

  @Date $Date: 2013-09-05 17:02:18 +0800 (周四, 05 九月 2013) $

  @Revision $Revision: 31 $

  @URL $URL: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_StackSeq.h $

  @Header $Header: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_StackSeq.h 31 2013-09-05 09:02:18Z xiaoting $

 */



#ifndef CXX_AL_STACKSEQ_H

#define CXX_AL_STACKSEQ_H



///////////////////////////////////////////////////////////////////////////

//			AL_StackSeq

///////////////////////////////////////////////////////////////////////////



template<typename T>  

class AL_StackSeq

{

public:

	static const DWORD STACKSEQ_MAXSIZE				= 0xffffffff;

	static const DWORD STACKSEQ_DEFAULTSIZE			= 100;

	/**

	* Construction

	*

	* @param DWORD dwSize (default value: STACKSEQ_DEFAULTSIZE)

	* @return

	* @note

	* @attention

	*/

	AL_StackSeq(DWORD dwSize = STACKSEQ_DEFAULTSIZE);



	/**

	* Destruction

	*

	* @param

	* @return

	* @note

	* @attention

	*/

	~AL_StackSeq();



	/**

	* Empty

	*

	* @param	VOID

	* @return	BOOL

	* @note		Returns true stack is empty

	* @attention

	*/

	BOOL Empty() const;



	/**

	* Pop

	*

	* @param	VOID

	* @return	T

	* @note		Remove the top element and return data top element

	* @attention	if empty does not return a value... (please judge the stack is empty before use it)

	*/

	T Pop();



	/**

	* Push

	*

	* @param	const T& tTemplate

	* @return	VOID

	* @note		Add elements in the stack

	* @attention

	*/

	VOID Push(const T& tTemplate);



	/**

	* Size

	*

	* @param	VOID

	* @return	DWORD

	* @note		Returns the number of elements in the stack

	* @attention

	*/

	DWORD Size() const;

	

	/**

	* Top

	*

	* @param	VOID

	* @return	DWORD

	* @note		Back to the top element...

	* @attention	if empty does not return a value... (please judge the stack is empty before use it)

	*/

	T Top() const;

	

protected:

private:

	/**

	* GetBuffer

	*

	* @param VOID

	* @return VOID

	* @note get the work buffer

	* @attention when the buffer is not enough, it will become to double

	*/

	VOID GetBuffer();

	

	/**

	* IsFull

	*

	* @param VOID

	* @return BOOL

	* @note the list is full?

	* @attention

	*/

	BOOL IsFull() const;





public:

protected:

private: 

	T*			m_pElements;

	DWORD		m_dwMaxSize;

	DWORD		m_dwSize;

};





/**

* Construction

*

* @param DWORD dwSize (default value: STACKSEQ_DEFAULTSIZE)

* @return

* @note

* @attention

*/

template<typename T> 

AL_StackSeq<T>::AL_StackSeq(DWORD dwSize):

m_pElements(NULL),

m_dwMaxSize(dwSize),

m_dwSize(0x00)

{

	if (0x00 == m_dwMaxSize) {

		//for memory deal

		m_dwMaxSize = 1;

	}

	GetBuffer();

}



/**

* Destruction

*

* @param

* @return

* @note

* @attention

*/

template<typename T> 

AL_StackSeq<T>::~AL_StackSeq()

{

	if (NULL != m_pElements) {

		delete[] m_pElements;

		m_pElements = NULL;

	}

}



/**

* Empty

*

* @param	VOID

* @return	BOOL

* @note		Returns true stack is empty

* @attention

*/

template<typename T> BOOL 

AL_StackSeq<T>::Empty() const

{

	return (0x00 == m_dwSize) ? TRUE:FALSE;

}



/**

* Pop

*

* @param	VOID

* @return	T

* @note		Remove the top element and return data top element

* @attention	if empty does not return a value... (please judge the stack is empty before use it)

*/

template<typename T> T 

AL_StackSeq<T>::Pop()

{

	T tTypeTemp;

	memset(&tTypeTemp, 0x00, sizeof(T));

	if (TRUE == Empty()) {

		//Empty

		return tTypeTemp;

	}



	tTypeTemp = m_pElements[Size()-1];

	memset(&m_pElements[Size()-1], 0x00, sizeof(T));

	m_dwSize--;



	return tTypeTemp;

}



/**

* Push

*

* @param	const T& tTemplate

* @return	VOID

* @note		Add elements in the stack

* @attention

*/

template<typename T> VOID

AL_StackSeq<T>::Push(const T& tTemplate)

{

	if (TRUE == IsFull()) {

		// full, need to get more work buffer

		GetBuffer();

	}



	m_dwSize++;

	m_pElements[Size()-1] = tTemplate;

}



/**

* Size

*

* @param	VOID

* @return	DWORD

* @note		Returns the number of elements in the stack

* @attention

*/

template<typename T> DWORD 

AL_StackSeq<T>::Size() const

{

	return m_dwSize;

}



/**

* Top

*

* @param	VOID

* @return	DWORD

* @note		Back to the top element...

* @attention	if empty does not return a value... (please judge the stack is empty before use it)

*/

template<typename T> T 

AL_StackSeq<T>::Top() const

{

	T tTypeTemp;

	memset(&tTypeTemp, 0x00, sizeof(T));

	if (TRUE == Empty()) {

		//Empty

		return tTypeTemp;

	}



	return m_pElements[Size()-1];

}



/**

* GetBuffer

*

* @param VOID

* @return VOID

* @note get the work buffer

* @attention when the buffer is not enough, it will become to double

*/

template<typename T> VOID 

AL_StackSeq<T>::GetBuffer()

{



	if ( (Size() < m_dwMaxSize) &&(NULL != m_pElements) ) {

		//we do not need to get more buffer

		return;

	}



	if (NULL == m_pElements) {

		if(0 < m_dwMaxSize){

			//get the new work buffer

			m_pElements = new T[m_dwMaxSize];

			memset(m_pElements, 0x00, sizeof(T)*m_dwMaxSize);

		}

		return;

	}



	//we need to get more buffer, store the previous pointer

	T* pLastTpye = NULL;

	DWORD pLastSize = 0x00;



	// it will become to double

	pLastSize = m_dwMaxSize;

	pLastTpye = m_pElements;

	if (STACKSEQ_MAXSIZE/2 < m_dwMaxSize) {

		m_dwMaxSize = STACKSEQ_MAXSIZE;

	}

	else {

		m_dwMaxSize *= 2;

	}

	if(0 < m_dwMaxSize){

		//get the new work buffer

		m_pElements = new T[m_dwMaxSize];

		memset(m_pElements, 0x00, sizeof(T)*m_dwMaxSize);

	}

	//need to copy the last to the current

	memcpy(m_pElements, pLastTpye, sizeof(T)*pLastSize);

	//free the last work buffer

	delete[] pLastTpye;

	pLastTpye = NULL;

}



/**

* IsFull

*

* @param

* @return BOOL

* @note the list is full?

* @attention

*/

template<typename T> BOOL 

AL_StackSeq<T>::IsFull() const

{

	return (m_dwMaxSize == Size()) ? TRUE:FALSE;

}

#endif // CXX_AL_STACKSEQ_H

/* EOF */


  

測試代碼

?

?

    #ifdef TEST_AL_STACKSEQ

	AL_StackSeq<DWORD> cStackSeq(1);

	BOOL bEmpty = cStackSeq.Empty();

	std::cout<<bEmpty<<std::endl;

	DWORD dwPop = cStackSeq.Pop();

	std::cout<<dwPop<<std::endl;

	DWORD dwSize = cStackSeq.Size();

	std::cout<<dwSize<<std::endl;

	DWORD dwTop = cStackSeq.Top();

	std::cout<<dwTop<<std::endl;

	

	for (WORD wCnt=1; wCnt<16; wCnt++) {

		//push 15 14 13 12.....

		cStackSeq.Push(16 - wCnt);

		dwTop = cStackSeq.Top();

		std::cout<<dwTop<<std::endl;

	}



	bEmpty = cStackSeq.Empty();

	std::cout<<bEmpty<<std::endl;

	dwSize = cStackSeq.Size();

	std::cout<<dwSize<<std::endl;



	while (0x00 != cStackSeq.Size()) {

		dwPop = cStackSeq.Pop();

		std::cout<<dwPop<<std::endl;

	}

#endif


  

?

?

[置頂] ※數據結構※→☆線性表結構（stack）☆============棧 序列表結構（stack sequence）（六）