棧是應用最廣泛的數據結構之一，很有必要對其進行一些總結。
棧（stack）是限制插入和刪除只能在一個位置上進行的表，該位置是表的末端，叫做棧的頂（top），它是後進先出（LIFO）的。對棧的基本操作只有push（進棧）和pop（出棧）兩種，前者相當於插入，後者相當於刪除最後的元素。
棧本質上是一種受限制的表，所以可以使用任何一種表的形式來實現它，最常用的是使用鏈表和數組。
使用鏈表的特點：不需要指定其大小，不會浪費空間；進棧和出棧涉及到動態內存的申請釋放，時間花銷大；
使用數組的特點：需要指定其大小，有可能浪費空間，也可能空間不夠用；進棧和出棧不涉及動態內存的申請釋放，因此時間上幾乎沒有花銷；另外支持隨機存取。
結論：一般使用鏈表是首選，除非滿足兩個條件：1.對運行時的效率要求極高；2.能夠預知棧需要的空間大小。
下面是利用單鏈表實現的棧：
/*stack.h (slist.h is the heaher file of single list class SList)*/
#include "slist.h"
template<typename T>
class Stack
{
public:
Stack();
Stack(const T& initdata);
~Stack();
public:
int IsEmpty() const;
void MakeEmpty();//清空。
int GetCount() const;
//void DisposeStack();//清空。對於用鏈表實現的Stack，這兩個清空的含義相同，對於用數組實現的，兩者含義不一樣。
int Push(T data);
int Pop(T *data = NULL);
int Top(T *data) const;
private:
SList<T> slist;
};
template<typename T>
inline Stack<T>::Stack():slist()
{
}
template<typename T>
inline Stack<T>::Stack(const T& initdata):slist(initdata)
{
}
template<typename T>
inline Stack<T>::~Stack()
{
}
template<typename T>
inline int Stack<T>::IsEmpty() const
{
return slist.IsEmpty();
}
template<typename T>
inline void Stack<T>::MakeEmpty()
{
slist.RemoveAll();
}
template<typename T>
inline int Stack<T>::GetCount() const
{
return slist.GetCount();
}
/*template<typename T>
inline void Stack<T>::DisposeStack()
{
slist.RemoveAll();
}*/
template<typename T>
inline int Stack<T>::Push(T data)
{
return slist.AddHead(data);
}
template<typename T>
inline int Stack<T>::Pop(T *data)
{
if (IsEmpty())
return 0;
if (data)
Top(data);
slist.RemoveHead();
return 1;
}
template<typename T>
inline int Stack<T>::Top(T *data) const
{
ASSERT(data);
if (IsEmpty())
return 0;
*data = slist.GetHead();
return 1;
}
下面是利用數組實現的棧：
/*stackarray.h*/
#include <assert.h>
const int EmptyTOS=-1;
const int MinStackSize=5;
const int MaxStackSize=500;
template<typename T>
class StackArray
{
public:
StackArray(int maxsize=MaxStackSize);
~StackArray();
public:
int IsEmpty() const;
void MakeEmpty();
int GetCount() const;
int IsFull();
int Resize(int newmaxsize);//change the capacity.
int Push(const T& data);
int Pop(T *data = NULL);
int Top(T *data) const;
private:
void DisposeStack();//釋放數組所占的內存，即棧被銷毀.
private:
int capacity;
int tos;//Top of stack for now.
T* array;
};
template<typename T>
inline StackArray<T>::StackArray(int maxsize):capacity(maxsize),tos(EmptyTOS),array(NULL)
{
ASSERT(capacity>=MinStackSize);
try
{
array=new T[capacity];
}
catch(std::bad_alloc&)
{
}
}
template<typename T>
inline StackArray<T>::~StackArray()
{
DisposeStack();
}
template<typename T>
inline void StackArray<T>::DisposeStack()
{
capacity=0;
tos=EmptyTOS;
if(array)
{
delete [] array;
}
}
template<typename T>
inline int StackArray<T>::IsEmpty() const
{
return EmptyTOS==tos;
}
template<typename T>
inline void StackArray<T>::MakeEmpty()
{
tos=EmptyTOS;
}
template<typename T>
inline int StackArray<T>::GetCount() const
{
return tos+1;
}
template<typename T>
inline int StackArray<T>::IsFull()
{
return tos>=capacity-1;
}
template<typename T>
inline int StackArray<T>::Resize(int newmaxsize)
{
DisposeStack();
capacity=newmaxsize;
tos=EmptyTOS;
try
{
array=new T[newmaxsize];
}
catch(std::bad_alloc&)
{
return 0;
}
return 1;
}
template<typename T>
inline int StackArray<T>::Push(const T& data)
{
if(IsFull())
{
return 0;
}
else
{
array[++tos]=data;
return 1;
}
}
template<typename T>
inline int StackArray<T>::Pop(T* data=NULL)
{
if(IsEmpty())
{
return 0;
}
else
{
if(data)
{
*data=array[tos];
}
--tos;
return 1;
}
}
template<typename T>
inline int StackArray<T>::Top(T* data) const
{
if(IsEmpty())
{
return 0;
}
else
{
*data=array[tos];
return 1;
}
}
