栈与队列 - 南叶の小窝

南叶酱

摸鱼ing...

统计加载中...

公告

评论不能用！！！其他里的东西暂时还没改，不是我的！！问题反馈和建议请加qq420883290 主页很乱，想看相关内容请看分类

Learn More

711 字

4 分钟

栈与队列

2025-11-08

算法

统计加载中...

栈#

栈的特点就是先入后出

定义#

1
stack<int> st;            // 默认底层容器是 deque<int>
2
stack<string> s2;
3
stack<int, vector<int>> s3;  // 指定底层容器（如 vector / list / deque）

手写栈#

1
struct stack
2
{
3
    vector<int> data;
4
    int t=0;
5
    bool empty()
6
    {
7
        return t==0;
8
    }
9
    void push(int x)
10
    {
11
        data.push_back(x);
12
        t++;
13
    }
14
    void pop()
15
    {
16
        if(!empty())
17
        {
18
            data.pop_back();
19
            t--;
20
        }
21
    }
22
    int top()
23
    {
24
        if(!empty())
25
        {
26
            return data[t-1];
27
        }
28
        return -1; // or throw an exception
29
    }
30
};

成员函数#

1
`push()`//入栈 O(1)
2
`pop()`//出栈 O(1)
3
`top()`//返回栈顶的元素引用 O(1)
4
`empty()`//判断栈是否为空 O(1)

括号匹配#

1
bool check(string s){
2
    stack<char> st;
3
    for (char c: s){
4
        if (c=='('||c=='['||c=='{') st.push(c);
5
        else {
6
            if (st.empty()) return false;
7
            char t=st.top(); st.pop();
8
            if ((c==')'&&t!='(')||(c==']'&&t!='[')||(c=='}'&&t!='{')) return false;
9
        }
10
    }
11
    return st.empty();
12
}

表达式求值（中缀转后缀）#

1
void solve()
2
{
3
    string s, ts;
4
    cin >> s;
5
    stack<int> a;
6
for (int i = 0; i < s.length(); i++)
7
{
8
    if (isdigit(s[i])) {
9
        ts += s[i];
10
    } else if (s[i] == '.')
11
    {
12
        if (!ts.empty())
13
        {
14
            a.push(atoi(ts.c_str()));
15
            ts.clear();
16
        }
17
    }
18
    else if(s[i]=='+')
19
    {
20
        int x = a.top(); a.pop();
21
        int y = a.top(); a.pop();
22
        a.push(x + y);
23
    }
24
    else if(s[i]=='-')
25
    {
26
        int x = a.top(); a.pop();
27
        int y = a.top(); a.pop();
28
        a.push(y - x);
29
    }
30
    else if(s[i]=='*')
31
    {
32
        int x = a.top(); a.pop();
33
        int y = a.top(); a.pop();
34
        a.push(x * y);
35
    }
36
    else if(s[i]=='/')
37
    {
38
        int x = a.top(); a.pop();
39
        int y = a.top(); a.pop();
40
        a.push(y / x);
41
    }
42
    else if(s[i]=='@')
43
    {
44
        cout<<a.top()<<endl;
45
    }
46
}
47
}

队列#

队列就是先入先出

实现#

一般有链队列和循环队列
链队列实际上就是单项链表
循环队列是一种顺序表，用两个指针head和tail指向队头和队尾
- 循环主要为了解决溢出问题

极简代码#

1
const int N=1e5;
2
int que[N],head,tail;
3
head++;//弹出队头
4
que[head];//读取队头数据
5
que[++tail] = data;//data入队

stl的queue#

方法	说明	时间复杂度
`q.push(x)`	入队（放到队尾）	O(1)
`q.pop()`	出队（删除队首）	O(1)
`q.front()`	返回队首元素引用	O(1)
`q.back()`	返回队尾元素引用	O(1)
`q.empty()`	判空，返回 bool	O(1)
`q.size()`	队列中元素个数	O(1)
`q.swap(q2)`	与另一个队列交换内容	O(1)

手写队列#

1
const int N = 1e5 + 10;
2
int q[N];
3
int head = 0, tail = 0;   // 队头队尾
4

5
bool empty() {
6
    return head == tail;
7
}
8

9
bool full() {
10
    return (tail + 1) % N == head;
11
}
12

13
void push(int x) {
14
    if (full()) return;       // 可自行处理溢出
15
    q[tail] = x;
16
    tail = (tail + 1) % N;
17
}
18

19
int front() {
20
    return q[head];
21
}
22

23
void pop() {
24
    if (!empty())
25
        head = (head + 1) % N;
26
}

双端队列和单调队列#

双端队列
- 能在两端进行插入和删除
单调队列（用双端实现）
- 队列中的元素单调有序
- 两端都能入队和出队

单调队列

1
int q[N],head,tail; //单调队列记录最小值的位置，方便后面判断某元素是否已经离开窗口
2
...
3
head=1,tail=0; //清空队列
4
for(int i=1;i<=n;i++) //枚举窗口右端
5
{
6
  while(head<=tail && i-q[head]+1>k) q[head++]=0; //弹出已经离开窗口的元素
7
  while(head<=tail && a[q[tail]]>a[i]) q[tail--]=0; //从队尾踢掉之前所有不小于当前元素的数
8
  q[++tail]=i; //当前元素自己加入队尾
9
  if(i>=k) res[i-k+1]=q[head]; //完成以上操作后，队头即为最小值
10
}

栈与队列

https://www.nanye404.top/posts/stack/

作者

南叶酱

发布于

2025-11-08

许可协议

CC BY-NC-SA 4.0

部分信息可能已经过时

算法竞赛入门

递归，分治

欢迎来到南叶の小窝

栈#

定义#

手写栈#

成员函数#

括号匹配#

表达式求值（中缀转后缀）#

队列#

实现#

极简代码#

stl的queue#

手写队列#

双端队列和单调队列#