栈是一种动态集合,栈的实现是一种后进先出策略,其中被删除的是最近插入的元素.
栈的操作:
- 判断栈是否为空
- 将一个元素压人(push)栈
- 将一个元素弹出(pop)栈
- 返回栈顶元素
- 清空栈
一个有趣的笑话:问一个人PUSH的反义词是什么.回答PULL的是普通人,而回答POP的才是程序员.
刘汝佳紫书
用c++手写一个栈:
#include <bits/stdc++.h> #define N 100000 using namespace std; int stk[N]; int point; bool stack_empty() { if ( point == 0 ) return true; return false; } void stack_push( int num ) { point ++; stk[point] = num; } void stack_pop() { if ( stack_empty() ) printf("underflow\n"); else point --; } int stack_top() { return stk[point]; } void stack_clear() { point = 0; } int main() { point = 0; int n; scanf("%d",&n); int cmd, num; //对一个栈进行n次操作 //0压 1弹 2返回栈顶 stack_clear(); for ( int i = 0; i < n; i ++ ) { scanf("%d",&cmd); if ( cmd == 0 ) { scanf("%d",&num); stack_push(num); } else if ( cmd == 1 ) stack_pop(); else if ( cmd == 2 ) { int item = stack_top(); printf("%d\n",item); } } return 0; }
在STL中的栈
- stack<int> stk;声明一个栈
- stk.empty();判断栈是否为空
- stk.push(num);将num压入栈
- stk.pop();弹出一个元素
- stk.top();返回栈顶元素
- stk.size();返回当前栈内元素个数
#include <bits/stdc++.h> using namespace std; stack<int> stk; int main() { int n; scanf("%d",&n); int cmd, num; //对一个栈进行n次操作 //0压 1弹 2返回栈顶 while ( !stk.empty() ) stk.pop(); for ( int i = 0; i < n; i ++ ) { scanf("%d",&cmd); if ( cmd == 0 ) { scanf("%d",&num); stk.push(num); } else if ( cmd == 1 ) stk.pop(); else if ( cmd == 2 ) { int item = stk.top(); printf("%d\n",item); } } return 0; }
一些题目: