知識星球（點選上方公眾號，可快速關註）
轉自：melonstreet
http://www.cnblogs.com/QG-whz/p/5170418.html
棧的特點
棧(Stack)是一種線性儲存結構，它具有如下特點：
1、棧中的資料元素遵守”先進後出”(First In Last Out)的原則，簡稱FILO結構。
2、限定只能在棧頂進行插入和刪除操作。
棧的相關概念
1、棧頂與棧底：允許元素插入與刪除的一端稱為棧頂，另一端稱為棧底。
2、壓棧：棧的插入操作，叫做進棧，也稱壓棧、入棧。
3、彈棧：棧的刪除操作，也叫做出棧。
例如我們有一個儲存整型元素的棧，我們依次壓棧：{1,2,3}
在壓棧的過程中，棧頂的位置一直在”向上“移動，而棧底是固定不變的。
如果我們要把棧中的元素彈出來：
出棧的順序為3、2、1 ，順序與入棧時相反，這就是所謂的”先入後出“。
在彈棧的過程中，棧頂位置一直在”向下“移動，而棧底一直保持不變。
如果你玩過一種稱為漢諾塔的益智玩具，你就會知道遊戲中小圓盤的存取就是一種先
進後出的順序，一個圓柱就是一個棧：
棧的操作
棧的常用操作為：
1、彈棧，通常命名為pop
2、壓棧，通常命名為push
3、求棧的大小
4、判斷棧是否為空
5、獲取棧頂元素的值
棧的儲存結構
棧既然是一種線性結構，就能夠以陣列或連結串列（單向連結串列、雙向連結串列或迴圈連結串列）作為底層資料結構。
本文我們以陣列、單向連結串列為底層資料結構構建棧。
基於陣列的棧實現
當以陣列為底層資料結構時，通常以陣列頭為棧底，陣列頭到陣列尾為棧頂的生長方向：
棧的抽象資料型別
棧提供瞭如上所述操作的相應介面。
template<typename T>
class ArrayStack
{
public:
ArrayStack(int s = 10); //預設的棧容量為10
~ArrayStack();
public:
T top(); //獲取棧頂元素
void push(T t); //壓棧操作
T pop(); //彈棧操作
bool isEmpty(); //判空操作
int size(); //求棧的大小
private:
int count; //棧的元素數量
int capacity; //棧的容量
T * array; //底層為陣列
};
1、count 為棧的元素數量，capacity為棧的容量，count<=capacity，當棧滿的時候，count = capacity。
2、本實現中不支援棧的動態擴容，棧滿的時候無法再插入元素。棧的容量在定義棧的時候就需要指定，預設的棧容量為10。
棧的具體實現
棧的實現還是相對簡單的，很容易理解。
/*棧的判空操作*/
template <typename T>
bool ArrayStack<T>::isEmpty()
{
return count == 0; //棧元素為0時為棧空
};
/*傳回棧的大小*/
template <typename T>
int ArrayStack<T>::size()
{
return count;
};
/*插入元素*/
template <typename T>
void ArrayStack<T>::push(T t)
{
if (count != capacity) //先判斷是否棧滿
{
array[count++] = t;
}
};
/*彈棧*/
template <typename T>
T ArrayStack<T>::pop()
{
if (count != 0) //先判斷是否是空棧
{
return array[—count];
}
};
/*獲取棧頂元素*/
template <typename T>
T ArrayStack<T>::top()
{
if (count != 0)
{
return array[count – 1];
}
};
棧的程式碼測試
int _tmain(int argc, _TCHAR* argv[])
{
ArrayStack <int> p(5);
for (int i = 0; i < 5; i++)
{
p.push(i);
}
cout << “棧的大小:”<<p.size() << endl;
cout << “棧是否為空:”<<p.isEmpty() << endl;
cout << “棧頂元素：”<<p.top() << endl;
cout << “依次出棧:” << endl;
while (!p.isEmpty())
{
cout << p.pop() << endl;
}
getchar();
return 0;
}
測試結果：
棧的大小:5
棧是否為空:0
棧頂元素：4
依次出棧:
4
3
2
1
0
基於單連結串列的棧
以連結串列為底層的資料結構時，以連結串列頭為作為棧頂較為合適，這樣方便節點的插入與刪除。壓棧產生的新節點將一直出現在連結串列的頭部；
連結串列節點
/*連結串列節點結構*/
template <typename T>
struct Node
{
Node(T t) :value(t), next(nullptr){};
Node() :next(nullptr){};
public:
T value;
Node<T>* next;
};
1、value:棧中元素的值
2、next:連結串列節點指標，指向直接後繼
棧的抽象資料型別
基於連結串列的棧提供的介面與基於陣列的棧一致。
/*棧的抽象資料結構*/
template <typename T>
class LinkStack
{
public:
LinkStack();
~LinkStack();
public:
bool isEmpty();
int size();
void push(T t);
T pop();
T top();
private:
Node<T>* phead;
int count;
};
棧的具體實現
/*傳回棧的大小*/
template <typename T>
int LinkStack<T>::size()
{
return count;
};
/*棧的判空操作*/
template <typename T>
bool LinkStack<T>::isEmpty()
{
return count == 0;
};
/*插入元素*/
template<typename T>
void LinkStack<T>::push(T t)
{
Node <T> *pnode = new Node<T>(t);
pnode->next = phead->next;
phead->next = pnode;
count++;
};
/*彈棧*/
template <typename T>
T LinkStack<T>::pop()
{
if (phead->next != nullptr) //棧空判斷
{
Node<T>* pdel = phead->next;
phead->next = phead->next->next;
T value = pdel->value;
delete pdel;
count—;
return value;
}
};
/*獲取棧頂元素*/
template <typename T>
T LinkStack<T>::top()
{
if (phead->next!=nullptr)
return phead->next->value;
};
棧的程式碼測試
int _tmain(int argc, _TCHAR* argv[])
{
LinkStack <string> lstack;
lstack.push(“hello”);
lstack.push(“to”);
lstack.push(“you！”);
cout << “棧的大小:” << lstack.size() << endl;
cout <<“棧頂元素:”<< lstack.top() << endl;
while (!lstack.isEmpty())
{
lstack.pop();
}
cout << “棧的大小:” << lstack.size() << endl;
getchar();
return 0;
}
測試結果：
棧的大小:3
棧頂元素:you！
棧的大小:0
覺得本文有幫助？請分享給更多人
關註「演演算法愛好者」，修煉程式設計內功
