棧的鏈表基礎表示結構
#include<iostream>
#include<stdexcept>
using namespace std;
//模板聲明，表明Stack類是一個通用的模板，可以用于存儲任何類型的元素T
template<typename T>
//棧的聲明
//Stack類的聲明，表示一個棧的數據結構
class Stack {
private://定義私有（成員變量）
?? ?struct Node {//結構體定義，用于表示棧中的結點，每個結點包含一個數據成員data和一個指向下一個結點的指針next
?? ??? ?T data;
?? ??? ?Node* next;
?? ??? ?Node(T d):data(d),next(NULL){}
?? ?};
?? ?Node* head;//用于保存棧的頭結點指針
?? ?int size;//用于保存棧的大小
?? ?
public://定義公共
?? ?Stack() : head(NULL),size(0){}//構造函數，用于初始化棧，它將頭結點指針設置為NULL，并將棧的大小設置為0
?? ?~Stack();//析構函數，用于釋放棧所用的內存
?? ?void push(T element);//公共函數，用于將一個新元素壓入棧頂
?? ?T pop();//用于從棧頂彈出一個元素
?? ?T top() const;//用于獲取棧頂的元素，但不彈出它
?? ?int getSize() const;//用于獲取棧中元素數量
};
//棧的擴容
//有鏈表實現棧時，每次如果是新生成的結點，則不涉及到像順序表那樣的擴容操作
//棧的銷毀
template<typename T>
Stack<T>::~Stack() {//析構函數的聲明，用于在對象銷毀時,釋放動態分配的結點內存
//不斷循環訪問棧中的元素，每次取出棧頂元素，存儲到臨時變量temp中，并且彈出棧頂，并利用delete將彈出的元素進行內存釋放，知道棧為空為止
?? ?while (head != NULL) {
?? ??? ?Node* temp = head;
?? ??? ?head = head->next;
?? ??? ?delete temp;
?? ?}
}
//入棧
template<typename T>
void Stack<T>::push(T element) {
//創建了一個新的Node對象，并將傳入的元素賦值給該對象的數據成員。通過使用new操作符動態分配了內存來存儲新的結點
?? ?Node* newNode = new Node(element);
?? ?newNode->next = head;//將新節點的next指針指向當前的頭結點。這樣，新節點就被添加到了棧的頭部
?? ?head = newNode;//將頭節點的指針更新為新節點，使新節點成為棧的新頭部
?? ?++size;//棧大小+1
}
//出棧
template<typename T>
T Stack<T>::pop() {
?? ?if (head == NULL) {
?? ??? ?throw std::underflow_error("Stack is empty");//如果棧空，拋出異常
?? ?}
?? ?T result = head->data;//將頭結點的數據成員賦值給result變量，準備返回彈出的元素
?? ?Node* temp = head;//將頭結點的指針賦值給temp變量，用于后續刪除頭結點
?? ?head = head->next;//將頭結點的next指針賦值給頭結點本身，從而將頭結點從鏈表中移除
?? ?delete temp;//調用delete釋放temp所指向的結點內存
?? ?--size;//棧大小-1
?? ?return result;//返回彈出的元素
}
//獲取棧頂元素
template<typename T>
T Stack<T>::top() const {
?? ?if (head == NULL) {
?? ??? ?throw std::underflow_error("Stack is empty");//如果棧空，拋出異常
?? ?}
?? ?return head->data;//不空，返回head的data域，即棧頂元素。
}
template<typename T>
int Stack<T>::getSize() const{
?? ?return size;
}
int main() {
?? ?Stack<int> st;
?? ?st.push(4);
?? ?st.push(7);
?? ?st.push(13);
?? ?cout << st.top() << endl;
?? ?st.push(17);
?? ?cout << st.top() << endl;
?? ?st.pop();
?? ?st.pop();
?? ?cout << st.top() << endl;
?? ?cout << st.getSize() << endl;
?? ?return 0;
}
