banner
cos

cos

愿热情永存，愿热爱不灭，愿生活无憾
github
tg_channel
bilibili
首頁封存关于♪歌单NFT作品集

模板類封裝(2)——順序棧和鏈式棧

#数据结构#栈#c++124
AI 翻譯
這篇文章透過AI由簡體中文翻譯成繁體中文。查看原文
AI 生成的摘要
這篇文章介紹了模板類封裝中的顺序栈和链式栈。文章首先介紹了栈的基本功能，包括建立栈、入栈、出栈等操作。接下來，文章詳細介紹了顺序栈的實現，包括顺序栈的定義、建立、入栈、出栈等操作。最後，文章提到了链式栈的實現，包括链式栈的建立、入栈、出栈等操作。整篇文章通過封裝模板類的方式實現了栈的基本操作。

c++ 語言，鏈棧實現

實驗內容：

  1. 編程實現棧的如下功能：
    （1）建立一個長度為 n 的順序棧，元素類型可自行定義，並輸出棧中各元素值。
    （2）將數據元素 e 入棧，並輸出入棧後的順序棧中各元素值。
    （3）將順序棧中的棧頂元素出棧，並輸出出棧元素的值和出棧後順序棧中各元素值。
  2. 編程實現隊列的如下功能：
    （1）建立一個長度為 n 的循環隊列，元素類型可自行定義，並輸出隊列中各元素值。
    （2）將數據元素 e 入隊，並輸出入隊後的隊列中各元素值。
    （3）將循環隊列的隊首元素出隊，並輸出出隊元素的值和出隊後隊列中各元素值。
  3. 編程實現鏈式棧的如下功能
    建立長度為 n 的鏈式棧，元素類型可自行定義，實現棧的初始化、進棧、出棧等典型操作。

整體上，一是實現順序棧和鏈棧的基本操作：入棧操作（Push）、出棧操作（Pop）、取棧頂元素（Top）、判斷棧空（IsEmpty）、判斷棧滿（IsFull）、獲取棧中元素個數（Size）、展示棧中所有元素（PrintStack）、清空棧中所有元素（Clear）。二是實現隊列的基本操作：入隊操作（Push）、出隊操作（Pop）、取隊首元素（Front）、判斷隊空（IsEmpty）、判斷隊滿（IsFull）、獲取隊中元素個數（Size）、展示隊中所有元素（PrintQueue）、清空隊中所有元素（Clear）。依舊是封裝一個模板類。初始化和銷毀操作在構造函數和析取函數中實現。
@TOC

順序棧#

順序棧操作類定義#

//順序棧定義
template <class T> class myStack1 {
private:
	int MaxSize;  //堆棧容量
	T* Data;	  //數據
	int top;  //記錄棧頂元素 為棧頂元素下標後一個下標，為空時top為0
public:
	myStack1(int maxsize = 100);  //構造函數 分配空間
	~myStack1();				   //析構函數 回收空間
	void PrintStack();		   //展示順序棧中所有元素
	void Push(T data);	//入棧操作,top值加一,存儲元素item在棧頂
	T Pop();			//出棧操作,將元素彈出返回,Top值減一
	T Top();			//取棧頂元素,不彈出
	int Size();			//獲取堆棧元素數量
	bool IsEmpty();		//判斷棧空與否
	bool IsFull();		//判斷棧滿與否
};

主要操作#

(1) 構造函數和析構函數#

template <class T>
myStack1<T>::myStack1(int maxsize) : MaxSize(maxsize), top(0) {
	Data = new T[maxsize];
};
template <class T> myStack1<T>::~myStack1() {
	if (Data)
		delete[] Data;
}

(2) 判斷棧空棧滿#

//判斷棧空與否
template <class T> bool myStack1<T>::IsEmpty() {
	return top == 0;
}
//判斷棧滿與否
template <class T> bool myStack1<T>::IsFull() {
	return top == MaxSize;
}

(3) 入棧操作#

存儲元素 data 在棧頂，Top 值加一

template <class T> void myStack1<T>::Push(T data) {
	if (IsFull()) {
		cout << "error:Failed to Push,The Stack is Full!" << endl;
	} else {
		Data[top++] = data;
	}
}

(4) 取棧頂元素#

取棧頂元素，不彈出

template <class T> T myStack1<T>::Top() {
	if (IsEmpty()) {
		cout << "error:The Top isn't existed, The Stack is Empty!" << endl;
		return error;  // ERROR為T類型中的特殊值
	} else {
		return Data[top - 1];
	}
}

(5) 獲取堆棧元素數量#

template <class T> int myStack1<T>::Size() {
	return top;
}

(6) 出棧操作#

彈出棧頂元素，Top 值減一

template <class T> T myStack1<T>::Pop() {
	if (IsEmpty()) {
		cout << "error:Failed to Pop, The Stack is Empty!" << endl;
		return error;  // ERROR為T類型中的特殊值
	} else {
		T temp = Data[--top];
		return temp;
	}
}

(7) 展示順序棧中所有元素#

template <class T> void myStack1<T>::PrintStack() {
	if (IsEmpty())
		cout << "This Stack is empty!" << endl;
	for (int i = 0; i < top; ++i) {
		cout << "The " << i + 1 << "th Data is:";
		cout << Data[i] << endl;
	}
	cout << "The Stack has " << top << " elements in total." << endl;
}

完整代碼#

//順序棧
#include <bits/stdc++.h>
#define error -1
using namespace std;
//順序棧定義
template <class T> class myStack1 {
private:
	int MaxSize;  //堆棧容量
	T* Data;	  //數據
	int top;  //記錄棧頂元素 為棧頂元素下標後一個下標，為空時top為0
public:
	myStack1(int maxsize = 100);  //構造函數 分配空間
	~myStack1();				   //析構函數 回收空間
	void PrintStack();		   //展示順序棧中所有元素
	void Push(T data);	//入棧操作,top值加一,存儲元素item在棧頂
	T Pop();			//出棧操作,將元素彈出返回,Top值減一
	T Top();			//取棧頂元素,不彈出
	int Size();			//獲取堆棧元素數量
	bool IsEmpty();		//判斷棧空與否
	bool IsFull();		//判斷棧滿與否
};

//順序棧操作類實現
//構造函數 分配空間
template <class T>
myStack1<T>::myStack1(int maxsize) : MaxSize(maxsize), top(0) {
	Data = new T[maxsize];
};
//析構函數 釋放空間
template <class T> myStack1<T>::~myStack1() {
	if (Data)
		delete[] Data;
}
//(1) 判斷棧空與否
template <class T> bool myStack1<T>::IsEmpty() {
	return top == 0;
}
//(2) 判斷棧滿與否
template <class T> bool myStack1<T>::IsFull() {
	return top == MaxSize;
}
//(3) 入棧操作
// 存儲元素data在棧頂,Top值加一
template <class T> void myStack1<T>::Push(T data) {
	if (IsFull()) {
		cout << "error:Failed to Push,The Stack is Full!" << endl;
	}
	else {
		Data[top++] = data;
	}
}
//(4) 取棧頂元素,不彈出
template <class T> T myStack1<T>::Top() {
	if (IsEmpty()) {
		cout << "error:The Top isn't existed, The Stack is Empty!" << endl;
		return error;  // ERROR為T類型中的特殊值
	}
	else {
		return Data[top - 1];
	}
}
//(5) 獲取堆棧元素數量
template <class T> int myStack1<T>::Size() {
	return top;
}
//(6) 出棧操作
// 彈出棧頂元素,Top值減一
template <class T> T myStack1<T>::Pop() {
	if (IsEmpty()) {
		cout << "error:Failed to Pop, The Stack is Empty!" << endl;
		return error;  // ERROR為T類型中的特殊值
	}
	else {
		T temp = Data[--top];
		return temp;
	}
}
//(7) 展示順序棧中所有元素
template <class T> void myStack1<T>::PrintStack() {
	if (IsEmpty())
		cout << "This Stack is empty!" << endl;
	for (int i = 0; i < top; ++i) {
		cout << "The " << i + 1 << "th Data is:";
		cout << Data[i] << endl;
	}
	cout << "The Stack has " << top << " elements in total." << endl;
}
//主函數中調用的函數 (測試用)
template <class T> void Stack_Push(myStack1<T>& S) {
	T data;
	cout << "請輸入要入棧的元素:";
	cin >> data;
	S.Push(data);
	cout << "------------- After Push, Stack S ---------------" << endl;
	S.PrintStack();
}
template <class T> void Stack_Pop(myStack1<T>& S) {
	T data = S.Pop();
	if (data != error) {
		cout << "出棧元素為:";
		cout << data << endl;
	}
	cout << "------------- After Pop, Stack S ---------------" << endl;
	S.PrintStack();
}
template <class T> void Stack_Top(myStack1<T>& S) {
	T data = S.Top();
	if (data != error) {
		cout << "棧頂元素為:";
		cout << data << endl;
	}
}
template <class T> void Stack_Size(myStack1<T>& S) {
	cout << "該堆棧中元素個數為:" << S.Size() << endl;
}
template <class T> void Stack_PrintStack(myStack1<T>& S) {
	cout << "---------------------- Stack S --------------------" << endl;
	S.PrintStack();
}
int main() {
	int n;
	cout << "輸入n,建立長度為n的順序棧:";
	cin >> n;
	myStack1<int> S(n);
	cout << "輸入n個元素:" << endl;
	for (int i = 0; i < n; ++i) {
		int data;
		cin >> data;
		S.Push(data);
	}
	cout << "1 入棧操作" << endl;
	cout << "2 出棧操作" << endl;
	cout << "3 取棧頂元素" << endl;
	cout << "4 取堆棧元素個數" << endl;
	cout << "5 輸出順序棧中所有元素" << endl;
	cout << "6 結束" << endl;
	while (1) {
		int choice;
		cout << "菜單選擇:";
		cin >> choice;
		getchar();
		switch (choice) {
			case 1: Stack_Push(S); break;
			case 2: Stack_Pop(S); break;
			case 3: Stack_Top(S); break;
			case 4: Stack_Size(S); break;
			case 5: Stack_PrintStack(S); break;
			case 6: break;
			default: cout << "輸入錯誤，請重新輸入";
		}
		if (choice == 6)
			exit(0);
		cout << "按回車鍵繼續…" << endl;
		getchar();
	};
	return 0;
}

鏈棧#

鏈棧結點定義#

template <class T> class SNode {
private:
	SNode* next;  //指針
	T Data;		  //數據
public:
	friend class Stack<T>;
	SNode() { next = nullptr; }	 //空結點
	SNode(T data) {				 //有數據的結點
		Data = data;
		next = nullptr;
	}
	void showdata() { cout << Data << endl; }  //展示該結點數據
};

鏈棧操作類定義#

template <class T> class Stack {
private:
	int maxsize;  //堆棧容量
	SNode<T>* head;	 //頭指針 帶空頭結點，所以棧頂元素一直為head->next
public:
	Stack(int size = 100);	//構造函數 分配空間,空頭結點
	~Stack();				//析構函數 回收空間
	void PrintStack();		//展示棧中所有元素
	void Clear();			//清空棧中所有元素
	void Push(T data);		//入棧操作 存儲元素data在棧頂
	T Pop();		 //出棧操作 彈出棧頂元素並將其在棧中刪除
	T Top();		 //取棧頂元素,不彈出
	int Size();		 //獲取堆棧元素數量
	bool IsEmpty();	 //判斷棧空與否
	bool IsFull();	 //判斷棧滿與否
};

主要操作#

(1) 構造函數和析構函數#

//構造函數 分配空間,空頭結點
template <class T> Stack<T>::Stack(int size) : maxsize(size) {
	head = new SNode<T>;
	head->next = nullptr;
};

//析構函數 釋放空間
template <class T> Stack<T>::~Stack() {
	while (head->next) {
		Pop();
	}
	if (head)
		delete head;
}

(2) 判斷棧空棧滿#

template <class T> bool Stack<T>::IsEmpty() {
	if (head->next) return false;
	else return true;
}
template <class T> bool Stack<T>::IsFull() {
	if (Size() < maxsize) return false;
	else return true;
}

(3) 入棧操作#

存儲元素 data 在棧頂

template <class T> void Stack<T>::Push(T data) {
	if (IsFull()) {
		cout << "error:Failed to Push,The Stack is Full!" << endl;
	} else {
		SNode<T>* p = new SNode<T>;
		p->Data = data;
		p->next = head->next;
		head->next = p;
	}
}

(4) 取棧頂元素#

template <class T> T Stack<T>::Top() {
	if (IsEmpty()) {
		cout << "error:The Top isn't existed, The Stack is Empty!" << endl;
		return error;
	} else {
		T temp = head->next->Data;
		return temp;
	}
}

(5) 獲取堆棧元素數量#

template <class T> int Stack<T>::Size() {
	int cnt = 0;
	SNode<T>* p = head;
	while (p->next) {
		cnt++;
		p = p->next;
	}
	return cnt;
}

(6) 出棧操作#

彈出棧頂元素並將其在棧中刪除

template <class T> T Stack<T>::Pop() {
	if (IsEmpty()) {
		cout << "error:Failed to Pop, The Stack is Empty!" << endl;
		return error;
	} else {
		SNode<T>* temp = head->next;
		T TopData = temp->Data;
		head->next = temp->next;
		delete temp;
		return TopData;
	}
}

(7) 展示棧中所有元素#

彈出棧頂元素並將其在棧中刪除

template <class T> T Stack<T>::Pop() {
	if (IsEmpty()) {
		cout << "error:Failed to Pop, The Stack is Empty!" << endl;
		return error;
	} else {
		SNode<T>* temp = head->next;
		T TopData = temp->Data;
		head->next = temp->next;
		delete temp;
		return TopData;
	}
}

(8) 清空棧中所有元素#

//(8) 清空棧中所有元素
template <class T> void Stack<T>::Clear() {
	while (head->next) {
		Pop();
	}
}

完整代碼#

//鏈棧
#include <bits/stdc++.h>
#define error -1
using namespace std;
template <class T> class Stack;
//鏈棧結點定義
template <class T> class SNode {
private:
	SNode* next;  //指針
	T Data;		  //數據
public:
	friend class Stack<T>;
	SNode() { next = nullptr; }	 //空結點
	SNode(T data) {				 //有數據的結點
		Data = data;
		next = nullptr;
	}
	void showdata() { cout << Data << endl; }  //展示該結點數據
};
//鏈棧操作類定義
template <class T> class Stack {
private:
	int maxsize;  //堆棧容量
	SNode<T>* head;	 //頭指針 帶空頭結點，所以棧頂元素一直為head->next
public:
	Stack(int size = 100);	//構造函數 分配空間,空頭結點
	~Stack();				//析構函數 回收空間
	void PrintStack();		//展示棧中所有元素
	void Clear();			//清空棧中所有元素
	void Push(T data);		//入棧操作 存儲元素data在棧頂
	T Pop();		 //出棧操作 彈出棧頂元素並將其在棧中刪除
	T Top();		 //取棧頂元素,不彈出
	int Size();		 //獲取堆棧元素數量
	bool IsEmpty();	 //判斷棧空與否
	bool IsFull();	 //判斷棧滿與否
};

//鏈棧操作類實現
//構造函數 分配空間,空頭結點
template <class T> Stack<T>::Stack(int size) : maxsize(size) {
	head = new SNode<T>;
	head->next = nullptr;
};

//析構函數 釋放空間
template <class T> Stack<T>::~Stack() {
	while (head->next) {
		Pop();
	}
	if (head)
		delete head;
}
//(1) 判斷棧空與否
template <class T> bool Stack<T>::IsEmpty() {
	if (head->next)
		return false;
	else
		return true;
}
//(2) 判斷棧滿與否
template <class T> bool Stack<T>::IsFull() {
	if (Size() < maxsize)
		return false;
	else
		return true;
}
//(3) 入棧操作
// 存儲元素data在棧頂
template <class T> void Stack<T>::Push(T data) {
	if (IsFull()) {
		cout << "error:Failed to Push,The Stack is Full!" << endl;
	}
	else {
		SNode<T>* p = new SNode<T>;
		p->Data = data;
		p->next = head->next;
		head->next = p;
	}
}
//(4) 取棧頂元素,不彈出
template <class T> T Stack<T>::Top() {
	if (IsEmpty()) {
		cout << "error:The Top isn't existed, The Stack is Empty!" << endl;
		return error;
	}
	else {
		T temp = head->next->Data;
		return temp;
	}
}
//(5) 獲取堆棧元素數量
template <class T> int Stack<T>::Size() {
	int cnt = 0;
	SNode<T>* p = head;
	while (p->next) {
		cnt++;
		p = p->next;
	}
	return cnt;
}
//(6) 出棧操作
// 彈出棧頂元素並將其在棧中刪除
template <class T> T Stack<T>::Pop() {
	if (IsEmpty()) {
		cout << "error:Failed to Pop, The Stack is Empty!" << endl;
		return error;
	}
	else {
		SNode<T>* temp = head->next;
		T TopData = temp->Data;
		head->next = temp->next;
		delete temp;
		return TopData;
	}
}
//(7) 展示棧中所有元素
template <class T> void Stack<T>::PrintStack() {
	if (IsEmpty())
		cout << "This Stack is empty!" << endl;
	SNode<T>* p = head;
	int cnt = 0;
	while (p->next) {
		++cnt;
		p = p->next;
		cout << "The " << cnt << "th Data is:";
		cout << p->Data << endl;
	}
	cout << "The Stack has " << Size() << " elements in total." << endl;
}
//(8) 清空棧中所有元素
template <class T> void Stack<T>::Clear() {
	while (head->next) {
		Pop();
	}
}
//主函數中調用的函數 (測試用)
template <class T> void Stack_Push(Stack<T>& S) {
	T data;
	cout << "請輸入要入棧的元素:";
	cin >> data;
	getchar();
	S.Push(data);
	cout << "------------- After Push, Stack S ---------------" << endl;
	S.PrintStack();
}
template <class T> void Stack_Pop(Stack<T>& S) {
	T data = S.Pop();
	if (data != error) {
		cout << "出棧元素為:";
		cout << data << endl;
	}
	cout << "------------- After Pop, Stack S ---------------" << endl;
	S.PrintStack();
}
template <class T> void Stack_Top(Stack<T>& S) {
	T data = S.Top();
	if (data != error) {
		cout << "棧頂元素為:";
		cout << data << endl;
	}
}
template <class T> void Stack_Size(Stack<T>& S) {
	cout << "該堆棧中元素個數為:" << S.Size() << endl;
}
template <class T> void Stack_PrintStack(Stack<T>& S) {
	cout << "---------------------- Stack S --------------------" << endl;
	S.PrintStack();
}
template <class T> void Stack_ClearStack(Stack<T>& S) {
	S.Clear();
	cout << "成功清空！" << endl;
}
int main() {
	int n;
	cout << "輸入n,建立長度為n的鏈棧:";
	cin >> n;
	Stack<int> S(n);
	cout << "輸入n個元素:" << endl;
	for (int i = 0; i < n; ++i) {
		int data;
		cin >> data;
		S.Push(data);
	}
	cout << "1 入棧操作" << endl;
	cout << "2 出棧操作" << endl;
	cout << "3 取棧頂元素" << endl;
	cout << "4 取堆棧元素個數" << endl;
	cout << "5 輸出棧中所有元素" << endl;
	cout << "6 清空棧中所有元素" << endl;
	cout << "7 結束" << endl;
	while (1) {
		int choice;
		cout << "菜單選擇:";
		cin >> choice;
		getchar();
		switch (choice) {
			case 1: Stack_Push(S); break;
			case 2: Stack_Pop(S); break;
			case 3: Stack_Top(S); break;
			case 4: Stack_Size(S); break;
			case 5: Stack_PrintStack(S); break;
			case 6: Stack_ClearStack(S); break;
			case 7: break;
			default: cout << "輸入錯誤，請重新輸入";
		}
		if (choice == 7)
			exit(0);
		cout << "按回車鍵繼續…" << endl;
		getchar();
	};
	return 0;
}
載入中......
此文章數據所有權由區塊鏈加密技術和智能合約保障僅歸創作者所有。