考研数据结构代码实现之顺序栈（基于王道书）

代码实现基于王道书上给的代码，代码如有缺陷之处，欢迎指正~

说明：

· .h文件用于声明

· .cpp文件用于定义

· main.cpp 用于测试

注：代码在VS2022调试测试

顺序栈：

Sqstack.h

#pragma once #include<stdio.h> #include<stdlib.h> // 基本操作 //• InitStack(&S) :初始化一个空栈S。 //• StackEmpty(S) : 判断栈是否为空。若栈S为空，返回true；否则返回false。 //• Push(&S, x) : 入栈操作；若栈未满，则x成为新的栈顶元素。 //• Pop(&S, &x) : 出栈操作；若栈非空，则弹出栈顶元素，并通过x返回该值。 //• GetTop(S, &x) : 读取栈顶元素但不出栈；若栈非空，则通过x返回栈顶元素。 //• DestroyStack(&S) : 销毁栈S，并释放其所占用的存储空间(&表示引用调用)。 #define MaxSize 50 #define ElemType int typedef struct { ElemType data[MaxSize]; int top; // 栈顶指针 }Sqstack; void InitStack(Sqstack& s); bool StackEmpty(Sqstack s); bool Push(Sqstack& s, ElemType x); bool Pop(Sqstack& s, ElemType& x); bool GetTop(Sqstack s, ElemType& x);

Sqstack.cpp

#include "Sqstack.h" void InitStack(Sqstack& s) { s.top = -1; // 初始栈顶指针为-1 } 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; } bool GetTop(Sqstack s, ElemType& x) { if (s.top == -1) return false; // 栈空 x = s.data[s.top]; return true; }

main.cpp

#include "Sqstack.h" #include <stdio.h> // 测试代码 int main() { Sqstack s; ElemType e; int i; // 1. 初始化栈 InitStack(s); printf("初始化栈完成。\n"); // 2. 判断栈是否为空 printf("栈是否为空？%s\n\n", StackEmpty(s) ? "是" : "否"); // 3. 入栈操作：压入1~10 printf("开始入栈："); for (i = 1; i <= 10; i++) { if (Push(s, i)) printf("%d ", i); else printf("\n入栈失败：%d (栈满)\n", i); } printf("\n\n"); // 4. 取栈顶元素（不出栈） if (GetTop(s, e)) printf("当前栈顶元素为：%d\n", e); else printf("取栈顶失败（栈空）\n"); printf("\n"); // 5. 出栈操作：弹出3个元素 printf("开始出栈："); for (i = 1; i <= 3; i++) { if (Pop(s, e)) printf("%d ", e); else printf("\n出栈失败\n"); } printf("\n\n"); // 6. 再次取栈顶 if (GetTop(s, e)) printf("出栈3个元素后，栈顶元素变为：%d\n", e); else printf("取栈顶失败（栈空）\n"); printf("\n"); // 7. 继续入栈直到栈满（测试边界） printf("继续入栈直到栈满：\n"); i = 11; while (Push(s, i)) { printf("入栈 %d 成功。\n", i); i++; } printf("栈已满，无法再入栈元素：%d\n\n", i); // 8. 测试栈空 / 栈满状态下的非法操作 printf("尝试在栈满时继续入栈："); if (!Push(s, 999)) printf("失败（栈满）\n"); else printf("成功？异常\n"); printf("尝试从栈中弹出所有元素："); while (Pop(s, e)) printf("%d ", e); printf("\n"); printf("尝试在栈空时出栈："); if (!Pop(s, e)) printf("失败（栈空）\n"); else printf("成功？异常\n"); printf("尝试在栈空时取栈顶："); if (!GetTop(s, e)) printf("失败（栈空）\n"); else printf("成功？异常\n"); // 9. 最终判空 printf("\n最终栈是否为空？%s\n", StackEmpty(s) ? "是" : "否"); return 0; }