#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define MaxSize 100
typedef int ElemType;
//定义栈_顺序栈
struct Stack
{
ElemType* top;
ElemType* base;
int stacksize;
};
int IsFull(Stack s);
int IsEmpty(Stack s);
//初始化
int InitStack(Stack& s)
{
s.base = new ElemType[MaxSize];
if (!s.base)
return ERROR;
s.top = s.base;
s.stacksize = MaxSize;
return OK;
}
//入栈
int PushbackStack(Stack& s, ElemType e)
{
//判断栈是否满
if (IsFull(s))
return ERROR;
*(s.top) = e;//error
s.top++;
return OK;
}
//出栈
int Popback(Stack& s, ElemType& e)
{
//判断栈是否空
if (IsEmpty(s))
return ERROR;
s.top--;
return OK;
}
//判满
int IsFull(Stack s)
{
if (s.top - s.base == s.stacksize)
return 1;
return 0;
}
//判空
int IsEmpty(Stack s)
{
if (s.base == s.top)
return 1;
return 0;
}
//获取栈顶元素
ElemType StackTop(Stack s)
{
//判断栈是否空
if (IsEmpty(s))
return ERROR;
return *(s.top - 1);
}
//清除栈
int ClearStack(Stack& s)
{
s.top = s.base;
return OK;
}
int Destroy(Stack& s)
{
delete s.base;
s.top = s.base = NULL;
return OK;
}
//构造栈——并按要求输出
int CreateStack(Stack& s, int n)
{
InitStack(s);
ElemType e;
for (int i = 0; i < n; i++)
{
cin >> e;
if (e == -1)
{
ElemType tmp = StackTop(s);
if (!tmp)
{
cout << "POP ERROR" << endl;
break;
}
else//输出栈顶元素并将其出栈
{
Popback(s, tmp);
cout << tmp << endl;
}
continue;
}
//进栈
PushbackStack(s, e);
}
return OK;
}
//输入一个整数序列a1,a2,a3...,an。当ai不等于-1时将ai进栈
//对于每一组数据输出若干行。每行为相应的出栈元素。当出栈异常时,输出“POP ERROR”并结束本组数据的输出。
void test1()
{
Stack s;
int n = 0;
while (1)
{
cin >> n;
if (n == 0)
return;
CreateStack(s, n);
Destroy(s);
}
return;
}
int main()
{
test1();
return 0;
}
上面的代码有错误,在读入第二组数据之后,n的值为2,不是预期中的0
这是因为再从缓冲中读取第二组数是,遇到两个-1后跳出循环,而第二组数据剩下的2 2还留在缓冲区中,于是再次读取时,n=2
改正方法:
1.将缓冲区的数强制入栈,不让其停留在缓冲区,这样虽可以解决上述问题,但是不符合题目要求,因为如果输入的是:
7
1 2 -1 -1 -1 2 -1
那么输出:1 2 2,预期输入:1 2
其代码如下
//构造栈——并按要求输出
int CreateStack(Stack& s, int n)
{
InitStack(s);
ElemType e;
for (int i = 0; i < n; i++)
{
cin >> e;
if (e == -1)
{
ElemType tmp = StackTop(s);
if (!tmp)
{
cout << "POP ERROR" << endl;
//std::flush 是C++标准库 中的一个操作符,用于刷新输出流。
//刷新输出流表示将缓冲区中的数据立即发送到关联的输出设备(例如屏幕或文件)
cout << flush;//刷新缓冲区
//break;
}
else//输出栈顶元素并将其出栈
{
Popback(s, tmp);
cout << tmp << endl;
}
continue;
}
//进栈
PushbackStack(s, e);
}
return OK;
}
//输入一个整数序列a1,a2,a3...,an。当ai不等于-1时将ai进栈
//对于每一组数据输出若干行。每行为相应的出栈元素。当出栈异常时,输出“POP ERROR”并结束本组数据的输出。
void test1()
{
Stack s;
int n = 0;
while (1)
{
cin >> n;
if (n == 0)
return;
CreateStack(s, n);
Destroy(s);
}
return;
}
改正方法2:设置一个标志变量,当读入元素为-1且栈空后,将后面的元素继续入栈,但是不进行判断处理
//构造栈——并按要求输出
int CreateStack(Stack& s, int n)
{
int flag = 1;
InitStack(s);
ElemType e;
for (int i = 0; i < n; i++)
{
cin >> e;
if (e == -1&&flag!=0)
{
ElemType tmp = StackTop(s);
if (!tmp)
{
cout << "POP ERROR" << endl;
flag = 0;
continue;
//break;
}
else//输出栈顶元素并将其出栈
{
Popback(s, tmp);
cout << tmp << endl;
}
continue;
}
//进栈
PushbackStack(s, e);
}
return OK;
}
改进方法3:将输入的数存入数组,从数组中读取数据
//构造栈——并按要求输出
int CreateStack(Stack& s, int n)
{
//int flag = 1;
InitStack(s);
ElemType arr[MaxSize];
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
int i = 0;
while(i<n)
{
if (arr[i] == -1)
{
ElemType tmp = StackTop(s);
if (!tmp)
{
cout << "POP ERROR" << endl;
cout << flush;
//flag = 0;
//continue;
break;
}
else//输出栈顶元素并将其出栈
{
Popback(s, tmp);
cout << tmp << endl;
}
i++;
continue;
}
//进栈
PushbackStack(s, arr[i]);
i++;
}
return OK;
}
标签:return,OJ,int,ElemType,top,北林,base,243,Stack
From: https://blog.51cto.com/u_15805257/7960151