在 C++ 的 STL（Standard Template Library，标准模板库） 中，queue 和 stack 都属于 容器适配器（Container Adapters），它们并不是独立的数据结构，而是基于其他底层容器（如 deque 或 list）封装出来的特定用途的数据结构。
两者的区别对比
| 特性 |
queue |
stack |
| 数据访问模式 |
FIFO（先进先出） |
LIFO（后进先出） |
| 插入位置 |
队尾（back） |
栈顶（top） |
| 删除位置 |
队首（front） |
栈顶（top） |
| 底层默认容器 |
deque |
deque |
| 常用场景 |
BFS（广度优先搜索）、任务队列等 |
DFS（深度优先搜索）、函数调用栈等 |
queue（队列）
queue 是先进先出（FIFO, First In First Out） 的数据结构。
元素只能从队尾（back）插入，从队首（front）移出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #ifndef MY_QUEUE_H
#define MY_QUEUE_H
#include "my_deque.h"
#include "my_utility.h"
#include "my_algorithm.h"
namespace mystl{
template <typename T, class Container = mystl::MyDeque<T>>
class MyQueue{
public:
using value_type = T;
using container_type = Container;
using size_type = typename Container::size_type;
using reference = typename Container::reference;
using const_reference = typename Container::const_reference;
protected:
container_type c;
public:
MyQueue() = default;
explicit MyQueue(const container_type& cont) : c(cont){}
explicit MyQueue(container_type&& count) : c(mystl::move(count)) {}
bool empty() const noexcept {return c.empty();}
size_type size() const noexcept {return c.size();}
reference front() {return c.front();}
const_reference front() const {return c.front();}
reference back() {return c.back();}
const_reference back() const {return c.back();}
void push(const value_type& value){c.push_back(value);}
void push(value_type&& value) {c.push_back(mystl::move(value));}
void pop(){c.pop_front();}
void swap(MyQueue& other) noexcept{
mystl::swap(c, other.c);
}
friend bool operator==(const MyQueue& lhs, const MyQueue& rhs){
return lhs.c == rhs.c;
}
friend bool operator!=(const MyQueue& lhs, const MyQueue& rhs){
return !(lhs == rhs);
}
};
}
#endif
|
stack（栈）
stack 是后进先出（LIFO, Last In First Out） 的数据结构。
元素只能从栈顶（top）插入和删除。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #ifndef MY_STACK_H
#define MY_STACK_H
#include "my_deque.h"
#include "my_utility.h"
namespace mystl{
template <typename T, class Container = mystl::MyDeque<T>>
class MyStack{
public:
using value_type = T;
using container_type = Container;
using size_type = typename Container::size_type;
using reference = typename Container::reference;
using const_reference = typename Container::const_reference;
protected:
container_type c;
public:
MyStack() = default;
explicit MyStack(const container_type& cont) : c(cont){}
explicit MyStack(container_type&& cont) : c(mystl::move(cont)) {}
bool empty() const noexcept {return c.empty();}
size_type size() {return c.size();}
reference top() {return c.back();}
const_reference top() const {return c.back();}
void push(const value_type& value){c.push_back(value);}
void push(value_type&& value){c.push_back(mystl::move(value));}
void pop(){c.pop_back();}
void swap(MyStack& other) noexcept{
mystl::swap(c, other.c);
}
friend bool operator==(const MyStack& lhs, const MyStack& rhs){
return lhs.c == rhs.c;
}
friend bool operator!=(const MyStack& lhs, const MyStack& rhs){
return !(lhs == rhs);
}
};
}
#endif
|
