一、棧的概念

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

二、棧的基本組成和操作

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

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

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

三、棧元素的存儲方式

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

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

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

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

（1）棧類的設計

根據(jù)前面對?；竟δ芎徒M成的描述，棧類應該包含下述的公有函數(shù)成員和私有數(shù)據(jù)成員。其中currentSize為棧頂指針，用于壓棧、入棧、判空、判滿等操作；T表示模板參數(shù)類型，棧元素為T類型數(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()判斷是否已滿

如果棧頂指針值等于棧的存儲容量SIZE時，棧滿：

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

（3）push()壓棧

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

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ù)并不需要對棧頂指針進行移動：

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

（6）clear()清空棧

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

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

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

最新評論