stack和queue

# stack

# 介绍

栈，先进后出（FILO），且只能访问到栈顶元素（top）

包括两个部分：

栈顶-进行数据的插入和删除操作
栈底-不做操作

原则：先进后出，后进先出，类似于弹夹
两个基础操作：

入栈：栈的插入操作，也叫压栈/进栈，入数据在栈顶
出栈：栈的删除操作，出数据在栈顶

# 定义

template <class T, class Container = deque<T> > class queue;

使用默认适配器定义

queue<int> q1;

使用自定义适配器定义

queue<int, vector<int>> q2;
queue<int, list<int>> q3;

1
2

# 使用

成员函数	函数功能
empty	判断栈是否为空
size	输出栈的有效元素个数
push	栈顶插入数据（入栈）
pop	栈顶删除数据（出栈）
top	输出栈顶元素
swap	交换两个栈的数据

    stack<int>s;
    s.push(100);
    s.push(200);
    s.push(1);
    s.push(10);
    while(!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }

1
2
3
4
5
6
7
8
9

# queue

# 介绍

队列，先进先出（FIFO）

原则：先进先出，后进后出，类似于排队
两个基本操作：

入队列：进行插入数据操作，在队尾的一端
出队列：进行删除数据操作，在队头的一端

# 定义

使用默认适配器定义

stack<int> st1;

使用自定义适配器定义

stack<int, vector<int>> st2;
stack<int, list<int>> st3;

1
2

# 使用

成员函数	函数功能
empty	判断队列是否为空
size	输出队列的有效数据个数
front	获取队头元素
back	获取队尾元素
push	队尾插入数据（入队）
pop	队头删除数据（出队）
swap	交换两个队列的数据

    queue<int>q;
    q.push(100);
    q.push(2);
    q.push(4);
    q.push(10);
    q.push(300);
    while(!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }

1
2
3
4
5
6
7
8
9
10

# deque

上面讲到，如果没有为stack、queue指定特定的底层容器，默认情况下使用deque
deque既可以对头尾进行增删，又支持下标随机访问（结合了vector和list的优点）
但是，deque的缺点就是：大量的operator[]效率低下，遍历相对复杂

# from cen

#笔记

上次更新: 2024/10/26, 21:27:03

← list priority_queue→