计算机与信息工程学院实验报告
姓名：杨馥瑞 学号：2212080042 专业：数据科学与大数据技术
年级：2022
课程：数据结构 主讲教师：袁彩虹老师 辅导教师：_______
实验时间：2024年 __月 ___日 __午__时至__时，实验地点_413_
实验题目：栈和队列的操作
实验目的：本实验项目可以支撑“实验目标1. 熟练掌握线性表（包括顺序表、链表、栈和队列）的存储方式及其操作实现。”。
本实验通过验证方式引导学生掌握顺序栈和链栈的基本操作，循环队列和链队列的基本操作，为后续学习打下基础，以便更好地达成后续更高层次的课程目标。
实验环境（硬件和软件）Dev c++ & windows11 x64
实验内容：
（1）编程实现顺序栈和链栈的基本操作：建栈，取栈顶元素，入栈，出栈；
（2）编程实现循环队列和链队列的基本操作：建队列，取队头元素，入队，出队。
实验步骤：
实验内容（1）顺序栈：
结构体预定义顺序栈
顺序栈的初始化
判断是否为空栈
这里定义成了布尔类型
进栈
出栈
读取栈顶元素
返回栈长度
制空栈
销毁栈
测试主函数
实验内容（2）链栈：
感觉再比这顺序栈写听没新意的，来用c++规范的类来实现吧！
结构体预定义链栈
声明一个链栈类，并构造函数初始化
判断是否为空
进栈
出栈
得到头节点
制空栈
得到栈长度
析构函数销毁栈
测试主函数
实验数据记录：
顺序栈的：
链栈的：
结果经验吗！就是感觉涉及到内存处理，感觉还是java爽，每次写链式的无论是链表还是链栈都要将结点释放，不像java可以自动处理，无指向的结点。
还有吗！等听完课再补充吧，目前没啥想法，感觉用c++类实现更酷一点，但是费脑细胞
源代码：
#include<bits/stdc++.h>
using namespace std;
#define MaxSize 50
#define ElemType int
typedef struct{
ElemType *data;//存放元素
int top;
}SqStack;
//初始化栈
void InitStack(SqStack &S){
if(S.data!=NULL){
printf("出错！栈已创建");
}else{
S.top = -1;
S.data = new int[MaxSize];
}
}
//判断栈是否为空
bool StackEmpty(SqStack S){
if(S.top == -1){
return true;//空
}else
return false;//非空
}
//进栈
bool Push(SqStack &S,ElemType x){
if(S.top==MaxSize-1){
return false;//栈满了
}
S.data[++S.top]=x;//指针加一接着入栈
return true;
}
//出栈
bool Pop(SqStack &S,ElemType &x){
if(S.top==-1)
return false;//空栈无法出栈
x = S.data[S.top--];
return true;//先出栈再减一
}
//读取栈顶元素
ElemType GetTop(SqStack S){
if(S.top==-1){
return -1;//空栈
}
return S.data[S.top];
}
//返回栈长度
int Length(SqStack S){
return S.top+1;
}
//制空栈
int ClearStack(SqStack &S){
S.top = -1;
}
//销毁栈
void DestoryStack(SqStack &S){
S.top = -1;
free(S.data);
S.data = NULL;
}
int main(){
SqStack S;
S.data = NULL;
//初始化
InitStack(S);
//判断是否为空
if(StackEmpty(S)){
printf("栈为空！\n");
} else{
printf("栈非空！\n");
}
//将 1-5 进栈
if(Push(S,1)&&Push(S,2)&&Push(S,3)&&Push(S,4)&&Push(S,5)){
printf("已经进栈\n");
}else{
printf("出错！\n");
}
//输出此时栈长度
printf("栈长度为 %d\n",Length(S));
//输出此时的栈顶元素
printf("栈顶元素为 %d\n",GetTop(S));
//出栈两个元素
ElemType x1,x2;
if(Pop(S,x1)&&Pop(S,x2)){
printf("已经出栈成功！\n");
printf("出栈元素为 %d,%d\n",x1,x2);
} else{
printf("出错！\n");
}
//输出此时栈长度
printf("栈长度为 %d\n",Length(S));
//销毁栈
DestoryStack(S);
//看看销好了么
if(StackEmpty(S)){
printf("栈为空！\n");
} else{
printf("栈非空！\n");
}
return 0;
}
#include <iostream>
using namespace std;
#define ElemType int
struct Node {
int data;
Node* next;
Node(int value) : data(value), next(NULL) {}//构造函数初始化一下
};
class LinkedStack {
private:
Node* top;//结点指针
int length;//长度
public:
LinkedStack() : top(NULL), length(0) {}
//判断是否为空
bool isEmpty() {
return top == NULL;
}
//进栈
void push(int value) {
Node* newNode = new Node(value);
newNode->next = top;
top = newNode;
length++;
}
//出栈
bool pop(ElemType &x) {
if (isEmpty()) {
return false;
}
Node* temp = top;
x = top->data;
top = top->next;
delete temp;
length--;
return true;
}
//得到头节点元素
int getTop() {
if (isEmpty()) {
return -1; // 空栈
}
return top->data;
}
//制空栈
void clearStack() {
while (!isEmpty()) {
Node* temp = top;
top = top->next;
delete temp;
}
}
//得到栈长度
int getLength(){
return length;
}
//析构函数
~LinkedStack() {
clearStack();
}
};
int main() {
LinkedStack stack;
if (stack.isEmpty()) {
cout << "栈为空！" << endl;
} else {
cout << "栈非空！" << endl;
}
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
cout << "已经进栈" << endl;
cout << "栈顶元素为 " << stack.getTop() << endl;
int x1, x2;
if (stack.pop(x1) && stack.pop(x2)) {
cout << "已经出栈成功！" << endl;
cout << "出栈元素为 " << x1 << ", " << x2 << endl;
} else {
cout << "出错！" << endl;
}
cout << "栈长度为 " << stack.getLength() << endl;
stack.clearStack();
if (stack.isEmpty()) {
cout << "栈为空！" << endl;
} else {
cout << "栈非空！" << endl;
}
return 0;
}
