大纲
stack 容器
stack 容器的概念
stack 是一种先进后出(First In Last Out,FILO)的数据结构,它只有一个出口。stack 容器允许新增元素、移除元素、取得栈顶元素,但是除了最顶端的元素外,没有任何其他方法可以存取 stack 中的其他元素。stack 没有迭代器,容器中所有元素的进出都必须符合 “先进后出” 的规则,只有 stack 最顶端的元素,才有机会被外界取用。换言之,stack 不提供遍历功能,也不提供迭代器。deque 是双向开口的数据结构,若以 deque 为底部结构并封闭其头端开口,便轻而易举地形成一个 stack。因此,SGI STL 便以 deque 作为缺省情况下的 stack 底部结构。由于 stack 以底部容器完成其所有工作,而具有这种 “修改某物接口,形成另一种风貌” 的性质者,称为 adapter(配接器)
,因此,STL stack 往往不被归类为 container(容器)
,而被归类为 container adapter(容器配接器)
。
![]()
stack 容器的使用
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
| #include<iostream> #include<stack>
using namespace std;
void printStack(stack<int> &s) { while (!s.empty()) { cout << s.top() << " "; s.pop(); } cout << endl; }
int main() { stack<int> s1;
s1.push(5); s1.push(12); s1.push(24); s1.push(35); s1.push(46);
printStack(s1);
stack<int> s2 = s1;
return 0; }
|
程序运行输出的结果如下:
queue 容器
queue 容器的概念
queue 是一种先进先出(First In First Out,FIFO)的数据结构,它有两个出口。queue 容器允许从一端新增元素,从另一端移除元素。queue 所有元素的进出都必须符合 ” 先进先出” 的规则,只有 queue 的顶端元素,才有机会被外界取用。queue 不提供遍历功能,也不提供迭代器。由于 queue 以底部容器完成其所有工作,因此,STL queue 往往也不被归类为 container(容器)
,而被归类为 container adapter(容器配接器)
。
![]()
queue 容器的使用
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
| #include<iostream> #include<queue>
using namespace std;
void printQueue(queue<int> &q) { while (!q.empty()) { cout << "大小: " << q.size() << endl; cout << "队头: " << q.front() << endl; cout << "队尾: " << q.back() << endl; q.pop(); }
}
int main() { queue<int> q1;
q1.push(1); q1.push(3); q1.push(5); q1.push(7); q1.push(9); cout << "size = " << q1.size() << endl;
cout << "first = " << q1.front() << endl;
cout << "last = " << q1.back() << endl;
printQueue(q1);
queue<int> q2 = q1;
return 0; }
|
程序运行输出的结果如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| size = 5 first = 1 last = 9 大小: 5 队头: 1 队尾: 9 大小: 4 队头: 3 队尾: 9 大小: 3 队头: 5 队尾: 9 大小: 2 队头: 7 队尾: 9 大小: 1 队头: 9 队尾: 9
|