Posted by

栈是一种动态集合,栈的实现是一种后进先出策略,其中被删除的是最近插入的元素.

栈的操作:

  1. 判断栈是否为空
  2. 将一个元素压人(push)栈
  3. 将一个元素弹出(pop)栈
  4. 返回栈顶元素
  5. 清空栈

一个有趣的笑话:问一个人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;
}

一些题目:

单调栈模板:https://www.luogu.com.cn/problem/P5788

题解:https://scheng52123.com/index.php/2020/02/04/luogup5788/

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注