[C++知识库] 6-1 反向输出整数序列 10分【数据结构·顺序栈模拟】

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> 6-1 反向输出整数序列 10分【数据结构·顺序栈模拟】 -> 正文阅读

[C++知识库]6-1 反向输出整数序列 10分【数据结构·顺序栈模拟】

老师留的课后作业，capacity开小了不行啊，坑死我了
（一）题目
6-1 反向输出整数序列 (10 分)
题目描述
输入一个整数序列（非负整数，只含正整数和 0 ）。序列以 -1 结束。要求反向输出这个非负整数序列。
要求定义一个栈来实现这个程序的功能。

输入
一个整数序列，每个数之间以空格隔开,非负整数，只含正整数和 0 。输入-1 表示输入结束。

输出
反向输出这个非负整数序列。

提示:
1、在C语言程序中使用 bool 类型，必须包含头文件 stdbool.h
2、题目要求创建栈时，栈空间有16个存储单元。但是服务器测试数据有超过50万个数据需要输入。因此，要求Push操作检查当前存储空间是否已满。若当前存储空间已满，则需要把容量（capacity）扩大为原来容量的2倍。
3、在Pop操作中，也要求检查容量。若弹出1个元素后，已用空间只有容量的三分之一，把容量减少为原来容量的一半。

函数接口定义：

栈的定义如下：
typedef int ElemType;
struct StackRecord;
typedef struct StackRecord *Stack;

struct StackRecord
{
    ElemType  *base;  //指向栈的元素存储空间
    int     top;      // 栈顶
    int   capacity;   //  当前已分配空间，以元素为单位
};

写出 createStack，push, pop,top,empty,destroy函数的定义。函数声明如下：

Stack createStack(void); //初始化一个空栈。空栈拥有16个元素的空间，栈顶值为 -1
void push(Stack pStack, ElemType x);//把 x 入栈
ElemType top(Stack pStack);//返回当前栈顶元素的值
void pop(Stack pStack); //当前栈顶元素出栈
bool empty(Stack pStack);//如果栈空，则返回 true，否则返回 false
void destroy(Stack pStack);//清空分配给栈的存储空间

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int ElemType;

struct StackRecord;
typedef struct StackRecord *Stack;

struct StackRecord
{
    ElemType  *base;  //指向栈的元素存储空间
    int     top;      // 栈顶
    int   capacity;   //  当前已分配空间，以元素为单位
};

Stack createStack();
void push(Stack pStack, ElemType x);
void pop(Stack pStack);
ElemType top(Stack pStack);
bool empty(Stack pStack);
void destroy(Stack pStack);

int main(void)
{
    Stack pStack;
    pStack = createStack();
    int x;
    scanf("%d", &x);
    while (x != -1)
    {
        push(pStack, x);
        scanf("%d", &x);
    }
    while (!empty(pStack))
    {
        x = top(pStack);
        printf("%d ", x);
        pop(pStack);
    }
    destroy(pStack);
    return 0;
}
/* 请在这里填写答案 */

输入样例：
在这里给出一组输入。例如：
3 127 64 1991 -1
输出样例：
在这里给出相应的输出。例如：
1991 64 127 3

（二）解答

（1）测试代码

#include <stdio.h>
#include <stdlib.h>
#include<stdbool.h>
 
typedef int ElemType;

typedef struct{
    int *base; 
    int top; 
    int capacity; //当前已分配空间
}*Stack;
 
Stack createStack();
void push(Stack pStack, int x);
void pop(Stack pStack);
int top(Stack pStack);
bool empty(Stack pStack);
void destroy(Stack pStack);
 
Stack createStack(){  
    Stack  s = (Stack )malloc(sizeof(Stack));
	s->capacity=16; //不能少，否则无答案输出？！ 16答案错误，9999999999答案正确了就 
    s->top = 0;
    s->base = (int *)malloc(sizeof(int) * s->capacity); 
    return s;
}
 
void push(Stack pStack, int x) //进栈,栈满return,这句挺必要的好像,没有段错误 
{
	if(pStack->top==pStack->capacity){ 
		return;
	}
    pStack->base[pStack->top++] = x;
//    if(pStack->top>pStack->capacity){
//    	pStack->capacity=2*pStack->capacity;
//    }
}

int top(Stack pStack) //取栈顶判空,空则return 
{
//	if(pStack->top==0){  //编译错误... 
//		return;
//	}
    return pStack->base[pStack->top - 1];
}

void pop(Stack pStack) //出栈判空,空则return 
{
	if(pStack->top==0){ 
		return;
	}
    pStack->top--;
//    if(pStack->top<=pStack->capacity/3){
//    	pStack->capacity=pStack->capacity/2;
//    }
}

bool empty(Stack pStack)
{
    return pStack->top == 0;
}

void destroy(Stack pStack)
{
    free(pStack->base);
}
 
int main(void)
{
    Stack pStack;
    pStack = createStack();
    int x;
    scanf("%d", &x);

    while (x != -1)
    {
        push(pStack, x);
        scanf("%d", &x);
    }
    while (!empty(pStack))
    {
        x = top(pStack);
        printf("%d ", x);
        pop(pStack);
    }
    destroy(pStack);
    return 0;
}

（2）提交AC代码

Stack createStack(){  
    Stack  s = (Stack )malloc(sizeof(Stack));
	s->capacity=9999999999; //不能少，否则无答案输出？！ 16答案错误，9999999999答案正确了就 
    s->top = 0;
    s->base = (int *)malloc(sizeof(int) * s->capacity); 
    return s;
}
 
void push(Stack pStack, int x) //进栈,栈满return,这句挺必要的好像,没有段错误 
{
	if(pStack->top==pStack->capacity){ 
		return;
	}
    pStack->base[pStack->top++] = x;
//    if(pStack->top>pStack->capacity){
//    	pStack->capacity=2*pStack->capacity;
//    }
}

int top(Stack pStack) //取栈顶判空,空则return 
{
//	if(pStack->top==0){  //编译错误... 
//		return;
//	}
    return pStack->base[pStack->top - 1];
}

void pop(Stack pStack) //出栈判空,空则return 
{
	if(pStack->top==0){ 
		return;
	}
    pStack->top--;
//    if(pStack->top<=pStack->capacity/3){
//    	pStack->capacity=pStack->capacity/2;
//    }
}

bool empty(Stack pStack)
{
    return pStack->top == 0;
}

void destroy(Stack pStack)
{
    free(pStack->base);
}

自己逼逼叨
其实我还想测试
（1）如果栈满栈空那些话去掉行不行，还能不能通过
（2）还有数据如果开小点capticity那个行不行，临界值是多少
（3）还有个关键想尝试的,就是上面代码中//中关于capticity信息的维护，加入后提交代码还能不能通过

到时候一定别忘再测试，尤其第（1）（3）点！！！
思考
s->capacity=99999999;这句代码为什么一定要加上，否则不能输出，因为后面push中的30-32行代码吗？！有个和这玩意比较，否则不能执行这话？！
if(pStack->top==pStack->capacity){
return;
}

我试了，如果把上述同时去掉，也可以测试样例通过
但如果像上面那样提交上去就是段错误，估计就是不能去掉30-32行那个判满代码
这启示我们，对于模拟栈的操作，别忘
入栈判满（出栈判空？！这题判空待测，起码这题不判满不行）