栈和队列算法总结

知识概览

在数据结构中，栈和队列都属于线性表。栈是先进后出（FILO）的，队列是先进先出（FIFO）的。

代码模板

#include <iostream>

using namespace std;

const int N = 100010;

// ********************** 栈
int stk[N], tt;

// 插入
stk[++tt] = x;

// 弹出
tt--;

// 判断栈是否为空
if (tt > 0) not empty
else empty

// 栈顶
stk[tt];

// ********************** 队列

// 在队尾插入元素，在对头弹出元素
int q[N], hh, tt = -1;

// 插入
q[++tt] = x;

// 弹出
hh++;

// 判断队列是否为空
if (hh <= tt) not empty
else empty

// 取出队头元素
q[hh];

栈

题目链接

https://www.acwing.com/problem/content/830/

代码（数组模拟）

#include <iostream>

using namespace std;

const int N = 100010;

int stk[N], tt;

int main()
{
    int m;
    cin >> m;
    
    while (m--)
    {
        int x;
        string op;
        
        cin >> op;
        if (op == "push")
        {
            cin >> x;
            stk[++tt] = x;
        }
        else if (op == "pop")
        {
            tt--;
        } 
        else if (op == "empty")
        {
            if (tt > 0) cout << "NO" << endl;
            else cout << "YES" << endl;
        }
        else if (op == "query")
        {
            cout << stk[tt] << endl;
        }
    }
    
    return 0;
}

代码（STL）

#include <iostream>
#include <stack>

using namespace std;

stack<int> stk;

int main()
{
    int m;
    cin >> m;
    
    while (m--)
    {
        int x;
        string op;
        
        cin >> op;
        if (op == "push")
        {
            cin >> x;
            stk.push(x);
        }
        else if (op == "pop")
        {
            stk.pop();
        } 
        else if (op == "empty")
        {
            if (stk.empty()) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
        else if (op == "query")
        {
            cout << stk.top() << endl;
        }
    }
    
    return 0;
}

队列

题目链接

https://www.acwing.com/problem/content/831/

代码（数组模拟）

#include <iostream>

using namespace std;

const int N = 100010;

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

int main()
{
    int m;
    cin >> m;
    
    while (m--)
    {
        int x;
        string op;
        
        cin >> op;
        if (op == "push")
        {
            cin >> x;
            q[++tt] = x;
        }
        else if (op == "pop")
        {
            hh++;
        }
        else if (op == "empty")
        {
            if (hh <= tt) cout << "NO" << endl;
            else cout << "YES" << endl;
        }
        else if (op == "query")
        {
            cout << q[hh] << endl;
        }
    }
    
    return 0;
}

代码（STL）

#include <iostream>
#include <queue>

using namespace std;

queue<int> q;

int main()
{
    int m;
    cin >> m;
    
    while (m--)
    {
        int x;
        string op;
        
        cin >> op;
        if (op == "push")
        {
            cin >> x;
            q.push(x);
        }
        else if (op == "pop")
        {
            q.pop();
        }
        else if (op == "empty")
        {
            if (!q.empty()) cout << "NO" << endl;
            else cout << "YES" << endl;
        }
        else if (op == "query")
        {
            cout << q.front() << endl;
        }
    }
    
    return 0;
}