4441: 【例15-3】栈-手写栈函数
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
洗盘子(1)小止是餐厅里的洗碗工,她身边有一叠餐盘要洗。客人们吃完饭之后,要洗的盘子会放在这叠餐盘的顶端;而小止洗盘子的时候,总会取出这叠餐盘最顶上的盘子来洗。
最开始桌子上没有餐盘。一位客人吃完饭了,依次把1、2、3这3个盘子放在了桌子上。现在小止取出了最顶端的3号盘子洗,洗完之后取出现在的顶端盘子2号。又有一个客人吃完了饭,依次放进了4、5这两个盘子。在这之后,小止依次洗完了5、4、1这3个盘子,结束了工作。研究这一叠盘子,把“放盘子”和“取盘子”视为事件,那么在每一次事件之后,这叠盘子会是什么状态呢?洗盘子的顺序如图15-2所示。
观察图15-2可以发现,越靠下的元素就越“顽固”,越靠上的元素就越容易改变?不难发现:对于这叠餐盘,如果a比b早加入,那a一定比b后退出。这种数据结构就是栈。栈是一种“后进先出(Last In First Out, LIFO)”的线性表,其限制是仅允许在表的一端进行插人和删除运算。
最后再看一眼“盘子状态”那一列表格,是不是觉得长得很像连绵的山,或是金字塔?请记住这个图像。这种“感性”的理解,有时候也很重要,这有助于提升联想能力。
样例输入 复制
样例输出 复制
Wash[3]
Wash[2]
Wash[5]
Wash[4]
Wash[1]提示
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 1010
int stack[MAXN]; //开辟栈需要的数组空间，其中MAXN是栈的最大支持的大小
int p = 0; //栈顶指针，指向下一个待插入的数组位置
void push(int x) { //压栈，需要判断栈是否溢出
if (p >= MAXN)
printf("Stack overflow.");
else {
stack[p] = x;
p += 1;
}
}
void pop() { //弹出栈顶元素，需要判断是否栈为空
if (p == 0)
printf("Stack is empty");
else
p -= 1;
}
int top() { //查询栈顶元素，需要判断是否栈为空
if (p == 0) {
printf("Stack is empty");
return -1;
} else
return stack[p - 1]; //注意按照定义方式，p-1才是栈顶
}
int main() {
push(1);push(2);push(3);
printf("Wash[%d]\n", top());pop();
printf("Wash[%d]\n", top());pop();
push(4);push(5);
printf("Wash[%d]\n", top());pop();
printf("Wash[%d]\n", top());pop();
printf("Wash[%d]\n", top());pop();
return 0;
}