栈是一种动态集合,栈的实现是一种后进先出策略,其中被删除的是最近插入的元素.
栈的操作:
- 判断栈是否为空
- 将一个元素压人(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;
}
一些题目: