棧的鏈表基礎表示結構
#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;
}