任务描述
本关任务是实现 step1/SeqStack.cpp 中的SS_IsFull、SS_IsEmpty、SS_Length、SS_Push和SS_Pop五个操作函数，以实现判断栈是否为满、是否为空、求栈元素个数、进栈和出栈等功能。
相关知识
栈的基本概念
栈是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算，这一端被称为栈顶。栈既可以采用顺序存储，也可以采用链接存储来实现。下面给出了一种基于顺序存储的栈的实现方案：
如图 1 所示：该栈存储了 4 个元素 {56,77,15,12} ，其中 12 是栈顶元素。
这种实现方案将栈元素存储在一片连续的空间中，栈相关的三个属性元素data、top和max介绍如下：
data: 给出栈存储空间的起始地址；top: 存放栈顶元素的位置编号；max: 指明栈存储空间中最多可存储的数据元素个数。
特别说明：空间的开始地址为
data，连续空间里的位置编号从data所指的开始位置起，到该空间的结束位置，编号依次是0,1,2,…,max-1。在图 1 的示例中max=6。栈顶元素的位置编号由top给出。
栈结构的定义（C）
基于data、top、max组织成的栈结构如下所示：
struct SeqStack{T* data; // 数据元素指针int top; // 栈顶元素编号int max; // 最大结点数};
为了讨论简单，我们假设栈元素的数据类型为整数：
typedef int T; // 栈元素的数据类型
据此，只要给定指向该结构的一指针 ss ，就可对栈进行进栈出栈操作。
- 进行进栈操作时，新进栈的元素保存在 top+1 位置，进栈后 top 加 1 ，这时的状态则如图 2 所示。
- 进行出栈操作时，将位置编号为 top 的元素出栈，出栈后 top 减去 1 ，这时的状态则如图 3 所示。
顺序栈的操作
以顺序存储的栈为例，我们定义如下操作：
-
创建栈：创建一个最多可以存储 maxlen 个元素的顺序栈。具体操作函数定义如下：
SeqStack* SS_Create(int maxlen)； -
释放栈空间：释放栈所占用的空间。具体操作函数定义如下：
void SS_Free(SeqStack* ss)； -
清空一个栈：将栈中元素清空。具体操作函数定义如下：
void SS_MakeEmpty(SeqStack* ss)； -
判断栈是否为满：若栈为满，则返回
true,否则返回false。具体操作函数定义如下：bool SS_IsFull(SeqStack* ss)； -
判断栈是否为空：若栈为空，则返回
true，否则返回false。具体操作函数定义如下：bool SS_IsEmpty(SeqStack* ss)； -
求栈元素个数：获取栈元素个数。具体操作函数定义如下：
int SS_Length(SeqStack* ss)； -
将元素 x 进栈：将 x 进栈，若满栈则无法进栈，返回
false，否则返回true。具体操作函数定义如下：bool SS_Push(SeqStack* ss, T x)； -
出栈：出栈的元素放入 item 。若出栈成功(栈不为空)，则返回
true；否则(空栈)，返回false。具体操作函数定义如下：bool SS_Pop(SeqStack* ss, T &item)； -
获取栈顶元素：获取栈顶元素放入 item 中。若获取失败(空栈)，则返回
false，否则返回true。具体操作函数定义如下：bool SS_Top(SeqStack* ss, T & item)； -
打印栈中元素：从栈底到栈顶打印出所有元素。具体操作函数定义如下：
void SS_Print(SeqStack* ss)。
编程要求
本关任务是实现 step1/SeqStack.cpp 中的SS_IsFull、SS_IsEmpty、SS_Length、SS_Push和SS_Pop五个操作函数，以实现判断栈是否为满、是否为空、求栈元素个数、进栈和出栈等功能。具体要求如下：
-
SS_IsFull：判断栈是否为满，若栈为满，则返回true，否则返回false； -
SS_IsEmpty：判断栈是否为空，若栈为空，则返回true，否则返回false； -
SS_Length：获取栈元素个数； -
SS_Push：将元素 x 进栈，若满栈则无法进栈，返回false，否则返回true； -
SS_Pop：若出栈成功(栈不为空)，则返回true；否则(空栈)，返回false； -
输入输出格式请参见后续说明及测试样例。
注意：本关必读中提及的其他操作已经由平台实现，你在实现本关任务的五个操作函数时，在函数体内可调用其他操作。
本关涉及的代码文件 SeqStack.cpp 中的 5 个操作函数的代码框架如下：
bool SS_IsFull(SeqStack* ss)// 判断栈是否为满。为满返回true，否则返回false。{// 请在这里补充代码，完成本关任务/********** Begin *********//********** End **********/}
bool SS_IsEmpty(SeqStack* ss)// 判断栈是否为空。为空返回true，否则返回false。{// 请在这里补充代码，完成本关任务/********** Begin *********//********** End **********/}
int SS_Length(SeqStack* ss)// 获取栈元素个数{// 请在这里补充代码，完成本关任务/********** Begin *********//********** End **********/}
bool SS_Push(SeqStack* ss, T x)// 将元素x进栈，若满栈则无法进栈，返回false，否则返回true{// 请在这里补充代码，完成本关任务/********** Begin *********//********** End **********/}
bool SS_Pop(SeqStack* ss, T &item)// 出栈的元素放入item。若出栈成功(栈不为空)，则返回true；否则(空栈)，返回false。{// 请在这里补充代码，完成本关任务/********** Begin *********//********** End **********/}
测试说明
本关的测试文件是 step1/Main.cpp ，负责对你实现的代码进行测试。具体代码如下：
#include <stdio.h>#include <stdlib.h>#include <string.h>#include "SeqStack.h"#pragma warning(disable:4996)void main(){int max;scanf("%d", &max);SeqStack* ss = SS_Create(max);char dowhat[100];while(true) {scanf("%s", dowhat);if (!strcmp(dowhat,"push")) {T x;scanf("%d", &x);SS_Push(ss,x);}else if (!strcmp(dowhat,"pop")) {T item;SS_Pop(ss, item);}else {break;}}int length = SS_Length(ss);printf("Stack length: %d\n", length);SS_Print(ss);SS_Free(ss);system("PAUSE");}
注意：step1/Main.cpp 的代码不能被修改。
输入输出说明： 输入格式： 首先输入一个正整数 max ，创建一个最多可存储 max 个元素的栈。然后输入多个操作：如果输入 “push” ，则后面跟一个数 x ，表示 x 进栈；如果输入 “pop” ，表示出栈操作；如果输入 “end” ，表示输入结束。
输出格式： 输出栈的长度，然后从栈底到栈顶依次输出各元素。
以下是平台对 step1/Main.cpp 的测试样例： 样例输入: 6 push 56 push 15 push 12 push 13 pop end 样例输出 Stack length: 3 stack data (from bottom to top): 56 15 12
开始你的任务吧，祝你成功！
就算孤独，也不能一个人哭泣，无论走在哪，都要高傲地挺立；就算高压，也不能情愿地趴下，只有仰视生活，膝盖才不至于卑微；就算挫败，也不能窝囊地依靠，无论在何时，都要倔强地站起。前面的路过于平坦，惬意久了难以找到方向；唯有脚下布满了荆棘，前方或许才是生机。
如果你有收获，请在下面点赞。
- //顺序存储的栈 实现文件
- /
- #include <stdio.h>
- #include <stdlib.h>
- #include "SeqStack.h"
-
- /*创建一个栈*/
- SeqStack* SS_Create(int maxlen)
- {
- SeqStack* ss=(SeqStack*)malloc(sizeof(SeqStack));
- ss->data=(T*)malloc(maxlen*sizeof(T));
- ss->top=-1;
- ss->max=maxlen;
- return ss;
- }
-
- /*释放一个栈*/
- void SS_Free(SeqStack* ss)
- {
- free(ss->data);
- free(ss);
- }
-
- /*清空一个栈*/
- void SS_MakeEmpty(SeqStack* ss)
- {
- ss->top=-1;//入栈时会+1，这样第一个元素top正好指向0
- }
-
- /*判断栈是否为满*/
- bool SS_IsFull(SeqStack* ss)
- {
- /*请在BEGIN和END之间实现你的代码*/
- /*****BEGIN*****/
- return ss->top+1>=ss->max;
- /******END******/
- }
-
- /*判断栈是否为空*/
- bool SS_IsEmpty(SeqStack* ss)
- {
- /*请在BEGIN和END之间实现你的代码*/
- /*****BEGIN*****/
- return ss->top<=-1;
-
- /******END******/
- }
-
- /*获取栈元素个数*/
- int SS_Length(SeqStack* ss)
- {
- /*请在BEGIN和END之间实现你的代码*/
- /*****BEGIN*****/
- return ss->top+1;
-
- /******END******/
- }
-
- /*将x进栈,满栈则无法进栈(返回false)*/
- bool SS_Push(SeqStack* ss, T x)
- {
- /*请在BEGIN和END之间实现你的代码*/
- /*****BEGIN*****/
- if(SS_IsFull(ss)) return false;
- else{
- ss->top++;
- ss->data[ss->top]=x;
- return true;
- }
-
- /******END******/
- }
-
- /*出栈，出栈的元素放入item,空栈则返回false*/
- bool SS_Pop(SeqStack* ss, T &item)
- {
- /*请在BEGIN和END之间实现你的代码*/
- /*****BEGIN*****/
- if(SS_IsEmpty(ss)) return false;
- else{
- item=ss->data[ss->top];
- ss->top--;
- }
-
- /******END******/
- }
-
- /*获取栈顶元素放入item中,空栈则返回false*/
- bool SS_Top(SeqStack* ss, T & item)
- {
- if (SS_IsEmpty(ss)) {
- return false;
- }
- item = ss->data[ss->top];
- return true;
- }
-
- /*从栈底到栈顶打印出所有元素*/
- void SS_Print(SeqStack* ss)
- {
- if (SS_IsEmpty(ss)) {
- printf("stack data: Empty!\n");
- return;
- }
- printf("stack data (from bottom to top):");
- int curr=0;
- while(curr<=ss->top) {
- printf(" %d", ss->data[curr]);
- curr++;
- }
- //printf("\n");
- }
