栈和队列

发布时间:2024年01月07日

目录

模拟栈

表达式求值

模拟队列


模拟栈

题目如下:

数组模拟栈:

  • 用top表示栈顶所在的索引。初始时,top = -1。表示没有元素。
  • push x :栈顶所在索引往后移动一格,然后放入x。st[++top] = x。
  • pop : top 往前移动一格。top–。
  • empty :top 大于等于 0 栈非空,小于 0 栈空。top == -1 ? “YES” : “NO”
  • query : 返回栈顶元素。st[top]

解题代码:

#include <iostream>

using namespace std;

const int N = 100010;

int m;
int stk[N], tt;

int main()
{
    cin >> m;
    while (m -- )
    {
        string op;
        int x;

        cin >> op;
        if (op == "push")
        {
            cin >> x;
            stk[ ++ tt] = x;
        }
        else if (op == "pop") tt -- ;
        else if (op == "empty") cout << (tt ? "NO" : "YES") << endl;
        else cout << stk[tt] << endl;
    }

    return 0;
}

算法板子

// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空,如果 tt > 0,则表示不为空
if (tt > 0)
{

}

表达式求值

题目如下:

解题代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <unordered_map>

using namespace std;

stack<int> num;
stack<char> op;

void eval()
{
    auto b = num.top(); num.pop();
    auto a = num.top(); num.pop();
    auto c = op.top(); op.pop();
    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    num.push(x);
}

int main()
{
    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i ++ )
    {
        auto c = str[i];
        if (isdigit(c))
        {
            int x = 0, j = i;
            while (j < str.size() && isdigit(str[j]))
                x = x * 10 + str[j ++ ] - '0';
            i = j - 1;
            num.push(x);
        }
        else if (c == '(') op.push(c);
        else if (c == ')')
        {
            while (op.top() != '(') eval();
            op.pop();
        }
        else
        {
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
            op.push(c);
        }
    }
    while (op.size()) eval();
    cout << num.top() << endl;
    return 0;
}

模拟队列

模拟思路:

  • 用一个数组 q 保存数据。
  • 用 hh 代表队头,q[hh] 就是队头元素, q[hh + 1] 就是第二个元素。
  • 用 tt 代表队尾, q[tt] 就是队尾元素, q[tt + 1] 就是下一次入队,元素应该放的位置。
  • [hh, tt] 左闭右闭,代表队列中元素所在的区间。
  • 出队pop:因为 hh 代表队头,[hh, tt] 代表元素所在区间。所以出队可以用 hh++实现,hh++后,区间变为[hh + 1, tt]。
  • 入队push:因为 tt 代表队尾,[hh, tt] 代表元素所在区间。所以入出队可以用 tt++实现,tt++后,区间变为[hh, tt + 1], 然后在q[tt+1]位置放入入队元素。
  • 是否为空empty:[hh, tt] 代表元素所在区间,当区间非空的时候,对列非空。也就是tt >= hh的时候,对列非空。
  • 询问队头query:用 hh 代表队头,q[hh] 就是队头元素,返回 q[hh] 即可。
#include <iostream>

using namespace std;

const int N = 100010;

int m;
int q[N], hh, tt = -1;

int main()
{
    cin >> m;

    while (m -- )
    {
        string op;
        int x;

        cin >> op;
        if (op == "push")
        {
            cin >> x;
            q[ ++ tt] = x;
        }
        else if (op == "pop") hh ++ ;
        else if (op == "empty") cout << (hh <= tt ? "NO" : "YES") << endl;
        else cout << q[hh] << endl;
    }

    return 0;
}

算法板子:

普通队列

// hh 表示队头,tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空,如果 hh <= tt,则表示不为空
if (hh <= tt)
{

}

循环队列

// hh 表示队头,tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空,如果hh != tt,则表示不为空
if (hh != tt)
{

}

文章来源:https://blog.csdn.net/qq_61553520/article/details/135446635
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。