banner
cos

cos

愿热情永存，愿热爱不灭，愿生活无憾
github
tg_channel
bilibili
主页归档关于♪歌单NFT作品集

模板类封装(2)——顺序栈和链式栈

#数据结构#栈#c++125
AI 生成的摘要
这篇文章介绍了如何使用C++实现顺序栈和链式栈。文章首先介绍了栈的基本操作，包括入栈、出栈、取栈顶元素、判断栈空、判断栈满、获取栈中元素个数、展示栈中所有元素和清空栈中所有元素。然后，文章详细介绍了顺序栈的实现，包括构造函数、析构函数、判断栈空栈满、入栈操作和出栈操作。最后，文章提到了链式栈的实现和相关操作。

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;
}
加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。