banner
cos

cos

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

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

#数据结构#栈#c++116
AI-generated summary
This is a tutorial on implementing stack data structures in C++. It covers the implementation of a sequential stack and a linked stack. The tutorial provides instructions on how to create a stack, push elements into the stack, pop elements from the stack, and perform other typical stack operations. The tutorial also includes code snippets for each operation.

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;
}
Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.