(C++)栈的链式存储结构(出栈、入栈、判空、遍历、销毁)(数据结构与算法)
链栈是运算受限的单链表、只能在链表头部进行操作
1.链表的头指针就是栈顶,链头为栈顶,链尾为栈底
2.栈的链式存储不需要附设头节点
3.基本不存在栈满的情况,不需要判断栈满,但要判空
4.空栈相当于头指针指向空
5.插入和删除仅在栈顶处执行
6.因为是动态分配空间,所以需要释放
#define MaxSize 100 //链栈的最大长度
typedef int SElemType; //链栈的数据元素类型假设为int整型
//创建链栈结构
typedef struct StackNode
{SElemType data; //结点数据域struct StackNode* next; //结点指针域
}StackNode, *LinkStack; //struct StackNode的结点形式、链栈形式别名LinkStack stack; //创建栈顶指针指向链栈的头结点
注意事项:
LinkStack temp1 = new StackNode;
这里 LinkStack 是一个指针类型别名,实际上是 StackNode* 的别名。
所以 temp1 是一个指针变量,指向 StackNode 类型的结点。
StackNode* temp2 = new StackNode;
这里直接声明了一个 StackNode* 类型的指针变量 temp2,指向 StackNode 类型的结点。
这两种声明方式是等价的。两者都创建了一个动态分配的 StackNode 类型的结点,并将它的地址赋给相应的指针变量。两者都可以通过 temp1->data 或 temp2->data 来访问结点的数据成员,以及 temp1->next 或 temp2->next 来访问结点的下一个结点的指针成员。
因此,在功能上,temp1 和 temp2 没有区别。不同的只是它们的声明方式,temp1 是通过别名 LinkStack 来声明的指针变量,而 temp2 是直接以 StackNode* 类型来声明的指针变量。
链栈存储结构及其实现如下:
#include<iostream>
using namespace std;#define MaxSize 100 //链栈的最大长度
typedef int SElemType; //链栈的数据元素类型假设为int整型
//创建链栈结构
typedef struct StackNode
{SElemType data; //结点数据域struct StackNode* next; //结点指针域
}StackNode, *LinkStack; //struct StackNode的结点形式、链栈形式别名LinkStack stack; //创建栈顶指针指向链栈的头结点bool InitStack(LinkStack& stack); //初始化链栈
bool StackEmpty(LinkStack& stack); //链栈判空
bool PushStack(LinkStack& stack, SElemType value); //入栈
bool PopStack(LinkStack& stack, SElemType& value); //出栈
SElemType GetTop(LinkStack& stack); //获取栈顶元素
bool StackPrint(LinkStack& stack); //遍历元素
void DestoryStack(LinkStack& stack); //销毁链栈,释放内存
int StackLength(LinkStack& stack); //计算链栈长度/元素个数//链栈的初始化
bool InitStack(LinkStack& stack)
{//构造一个空栈、栈顶指针置为空stack = NULL;return true;
}//判断链栈是否为空
bool StackEmpty(LinkStack& stack)
{if (stack == NULL){return true; }return false;
}//链栈的入栈
bool PushStack(LinkStack& stack, SElemType value) //不用判栈满
{StackNode* temp = new StackNode; //生成新结点temptemp->data = value; //将新节点数据域置为valuetemp->next = stack; //将新结点插入栈顶stack = temp; //更新栈顶指针return true;
}//链栈的出栈:首先判空
bool PopStack(LinkStack& stack, SElemType &value)
{if (StackEmpty(stack)){return false; }value = stack->data; //将栈顶数据域元素赋值给valueStackNode* temp = stack; //创建一个temp指针,并将其指向 stack 指针所指向的内存地址,以便找到出栈位置并释放。stack = stack->next; //令栈顶指针指向下一位结点,即更新栈顶指针delete temp; //释放temp所指向的空间,即出栈元素所占的内存空间,而temp本身会在函数结束后自动销毁。return true;
}//取栈顶元素
SElemType GetTop(LinkStack& stack)
{if (!StackEmpty(stack)) //若栈不为空{return stack->data; //返回栈顶元素}return false;
}
//获取栈顶长度
/*因为链表的最后一个节点的next指针是nullptr(或者说是NULL),代表链表的终止,
所以可以将链表的遍历条件设置为当前节点指针不等于nullptr,这样在遍历过程中,
当指针指向最后一个节点时,其next指针就会指向nullptr,循环条件就不再成立,
遍历结束,可以避免继续遍历下一个不合法的节点。*/
int StackLength(LinkStack& stack)
{int length = 0;StackNode* temp = stack;//创建临时指针temp与stack指向同一位置while (temp != nullptr){length++; //链栈长度即为栈中元素个数,循环一次,长度++temp = temp->next; //temp指针下移一位}return length; //返回链栈长度
}//遍历栈元素
bool StackPrint(LinkStack& stack)
{if (stack != nullptr){StackNode* temp = stack;//创建一个指针与stack指向同一位置cout << "出栈顺序:";while (temp != nullptr){cout << temp->data << " ";temp = temp->next; //temp向下移动一位}return true; //遍历完毕}cout << "栈为空!" << endl;return false;
}//销毁链栈,释放内存
void DestoryStack(LinkStack& stack)
{StackNode* temp = new StackNode;//创建一个指针while (stack != nullptr){temp = stack;//使该临时指针与stack指向同一位置stack = temp->next;//更新栈顶指针delete temp;//释放临时指针}stack = nullptr;return;
}//测试代码
int main()
{//创建链栈LinkStack stack;SElemType value;InitStack(stack);cout << "检查栈是否为空?" << (StackEmpty(stack) ? "\t是" : "\t否") << endl;int number = 0;//插入元素个数int num = 0; //插入元素值cout << "请输入需要插入的元素个数:";cin >> number;while ((number--) > 0) //计数{cin >> num;//输入数据PushStack(stack, num);//插入所输入元素}cout << "当前栈的元素个数:" << StackLength(stack) << endl; cout << "获取栈顶元素:" << GetTop(stack) << endl;StackPrint(stack); //遍历打印栈顶元素cout << endl;PopStack(stack, value); //出栈cout << "出栈一次后栈顶元素为:" << GetTop(stack) << endl;StackPrint(stack);//遍历打印链栈元素DestoryStack(stack);cout << endl << "栈已被销毁释放" << endl;cout << "销毁栈后打印输出结果:" <<" ";StackPrint(stack);cout << "销毁栈后遍历栈结果:" << " ";StackPrint(stack);system("pause");return 0;
}
结果: