一、棧的概念

棧的英文為stack，譯為一疊或者一摞。棧是一種采用先進(jìn)后出FILO（first in last out）或稱為后進(jìn)先出LIFO（last in first out）策略進(jìn)行元素訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。棧經(jīng)常被比作是一摞碟子，最上面的碟子是最后放上去的，卻是最先被拿走的。

二、棧的基本組成和操作

如果要正確的使用棧，則必須保證其含有棧頂指針和棧元素。此外，棧的基本操作含有：

• 初始化；
• 入棧；
• 出棧；
• 清空棧；
• 訪問(wèn)棧頂元素；
• 檢測(cè)棧的狀態(tài)；

其中，棧包含三種狀態(tài)：棧空、一般狀態(tài)、棧滿。檢測(cè)棧滿是非常重要的步驟，防止在棧容量不能擴(kuò)充時(shí)出現(xiàn)溢出現(xiàn)象，此時(shí)稱為上溢。如果在?？諘r(shí)進(jìn)行出棧操作，此時(shí)會(huì)出現(xiàn)下溢。所以在入棧和出棧時(shí)，必須對(duì)棧的狀態(tài)進(jìn)行檢查。

三、棧元素的存儲(chǔ)方式

常用的實(shí)現(xiàn)方式分為兩種;

• 第一種策略是使用靜態(tài)數(shù)組實(shí)現(xiàn)，此時(shí)棧的容量是有限的；
• 第二種策略是使用動(dòng)態(tài)數(shù)組或者鏈表，此時(shí)棧的容量可以動(dòng)態(tài)擴(kuò)充。

四、C++實(shí)現(xiàn)靜態(tài)棧

使用靜態(tài)數(shù)組實(shí)現(xiàn)棧結(jié)構(gòu)時(shí)，棧底固定不變，棧頂隨著壓棧和出棧操作進(jìn)行自加和自減。一般采用整型變量來(lái)表示棧頂，壓棧時(shí)棧頂變量加一，出棧時(shí)棧頂變量減一。

（1）棧類的設(shè)計(jì)

根據(jù)前面對(duì)?；竟δ芎徒M成的描述，棧類應(yīng)該包含下述的公有函數(shù)成員和私有數(shù)據(jù)成員。其中currentSize為棧頂指針，用于壓棧、入棧、判空、判滿等操作；T表示模板參數(shù)類型，棧元素為T(mén)類型數(shù)組，可以在隱式或顯式實(shí)例化時(shí)指定；SIZE表示棧的容量，一旦確定就不能更改。

代碼如下：

template <typename T, int SIZE=10>
class Stack {
public:
?? ?bool isEmpty();
?? ?bool isFull();
?? ?void push(const T &data);
?? ?T pop();
?? ?void clear();
?? ?T getTop();
?? ?
private:
? ? // 棧頂指針
?? ?int currentSize=-1;
?? ?T array[SIZE];
};

（1）isEmpty()判斷是否為空

如果棧頂指針值為0，則表示為棧為空，代碼如下：

template<typename T, int SIZE>
bool Stack<T, SIZE>::isEmpty() {
?? ?if (currentSize == 0) {return true;}
?? ?else {return false;}
}

（2）isFull()判斷是否已滿

如果棧頂指針值等于棧的存儲(chǔ)容量SIZE時(shí)，棧滿：

template<typename T, int SIZE>
bool Stack<T, SIZE>::isFull() {
?? ?if (currentSize == SIZE) {return true;}
?? ?else { return false; }
}

（3）push()壓棧

將數(shù)據(jù)壓棧時(shí)，棧頂指針同步加一；

template<typename T, int SIZE>
void Stack<T, SIZE>::push(const T &data) {
?? ?// 棧頂壓入
?? ?currentSize++;
?? ?array[currentSize] = data;
}

（4）pop()出棧

將數(shù)據(jù)彈出后，棧頂指針需要減一：

template<typename T, int SIZE>
T Stack<T, SIZE>::pop() {
? ? if(currentSize>=1){return array[currentSize--];}
}

（5）getTop()獲取棧頂元素

獲取棧頂數(shù)據(jù)并不需要對(duì)棧頂指針進(jìn)行移動(dòng)：

template<typename T, int SIZE>
T Stack<T, SIZE>::getTop() {
?? ?return array[currentSize];
}

（6）clear()清空棧

由于采用的是靜態(tài)數(shù)組，所以清空棧時(shí)無(wú)需進(jìn)行內(nèi)存釋放，將棧頂指針歸零即可：

template<typename T, int SIZE>
void Stack<T, SIZE>::clear() {
?? ?currentSize = -1;
}

到此這篇關(guān)于C++實(shí)現(xiàn)棧與分析棧的知識(shí)點(diǎn)的文章就介紹到這了,更多相關(guān)C++棧內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論