栈的典型算法实现
一、实验目的及要求
1.掌握栈的表示与实现
2.掌握栈的入栈、出栈等操作
二、实验内容
编写及实现顺序栈的定义及基本操作函数编写一个程序sqstack.cpp，实现顺序栈（假设栈的基本元素类型为char）的各种基本运算，并在此基础上设计一个程序完成下述功能。
（1）初始化栈s。
（2）判断栈s是否非空。
（3）依次进栈元素a、b、c、d、e。
（4）判断栈s是否非空。
（5）输出出栈序列。
（6）判断栈s是否非空。
（7）释放栈s。
三、实验设备与环境
Windows 11系统
codeblocks
四、实验设计方案
实验步骤：
1.定义顺序栈的数据结构，包括栈顶指针和栈中元素。
2.实现初始化栈的函数，用于创建一个空栈。
3.实现判断栈是否非空的函数，用于判断栈是否为空。
4.实现进栈的函数，用于将元素依次压入栈中。
5.实现判断栈是否非空的函数，用于判断栈是否为空。
6.实现出栈的函数，用于弹出栈顶元素并返回其值。
7.实现释放栈的函数，用于释放栈所占用的内存空间。
8.在主函数中调用以上函数，完成顺序栈的操作和功能测试。
设计思想：
本实验的设计思想是使用C++语言实现顺序栈的基本操作，包括初始化、判断是否为空、进栈、出栈和释放等操作。顺序栈是一种基于数组实现的栈，其特点是存取速度快，但空间利用率较低。在设计顺序栈时，需要考虑如何初始化、判断是否为空、进栈、出栈和释放等操作的具体实现方式。
算法描述：
1.定义一个结构体或类，包含一个指向栈顶元素的指针和栈中元素数组。
2.初始化栈时，将指针指向数组的起始位置，并清空数组。
3.判断栈是否非空时，检查指针是否指向数组的起始位置。
4.进栈时，将元素插入到数组的起始位置，并将指针向后移动一位。
5.出栈时，将指针指向数组的起始位置，并返回该位置的元素值。
6.释放栈时，清空数组和指针即可。
开发流程：
1.定义顺序栈的数据结构。
2.实现初始化、判断是否非空、进栈、出栈和释放等函数。
3.在主函数中调用以上函数，完成顺序栈的操作和功能测试。
4.编译并运行程序，检查输出结果是否符合预期。
五、实验结果
六、附录
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
char w;
typedef char ElemType;
typedef struct linknode
{
ElemType data; //数据域
struct linknode *next; //指针域
} LiStack;
//链栈类型定义
void InitStack(LiStack *&s)
{
s=(LiStack *)malloc(sizeof(LiStack));
s->next=NULL;
}
void DestroyQueue(LiStack *&s)
{
LiStack *p=s->next;
while (p!=NULL)
{
free(s);
s=p;
p=p->next;
}
free(s); //s指向尾结点,释放其空间
}
int StackLength(LiStack *s)
{
int i=0;
LiStack *p;
p=s->next;
while (p!=NULL)
{
i++;
p=p->next;
}
return(i);
}
bool StackEmpty(LiStack *s)
{
return(s->next==NULL);
}
void Push(LiStack *&s,ElemType e)
{ LiStack *p;
p=(LiStack *)malloc(sizeof(LiStack));
p->data=e; //新建元素e对应的节点*p
p->next=s->next; //插入*p节点作为开始节点
s->next=p;
}
bool Pop(LiStack *&s,ElemType &e)
{ LiStack *p;
if (s->next==NULL) //栈空的情况
return false;
p=s->next; //p指向开始节点
e=p->data;
s->next=p->next; //删除*p节点
free(p); //释放*p节点
return true;
}
bool GetTop(LiStack *s,ElemType &e)
{ if (s->next==NULL) //栈空的情况
return false;
e=s->next->data;
return true;
}
int main()
{
LiStack *s;
printf("(1)初始化栈s \n");
InitStack(s);
printf("(2)判断栈s是否非空: %s\n",(StackEmpty(s)?"空":"非空"));
printf("(3)依次进栈元素a、b、c、d、e \n");
Push(s,'a');
Push(s,'b');
Push(s,'c');
Push(s,'d');
Push(s,'e');
printf("(4)判断栈s是否非空: %s\n",(StackEmpty(s)?"空":"非空"));
printf("(5)输出出栈序列: ");
while(!StackEmpty(s))
{
Pop(s,w);
printf("%c",w);
}
printf("\n");
printf("(6)判断栈s是否非空: %s\n",(StackEmpty(s)?"空":"非空"));
printf("(7)释放栈 \n");
DestroyQueue(s);
return 0;
}