【C++研发面试笔记】16. 基本数据结构-队列queue与栈stack

【C++研发面试笔记】16. 基本数据结构-队列queue与栈stack

16.1 STL中stack实现

stack 模板类的定义在头文件中。栈中的数据是先进后出的（First In Last Out, FILO）。栈只有一个出口，允许新增元素（只能在栈顶上增加）、移出元素（只能移出栈顶元素）、取得栈顶元素等操作。
stack 模板类需要两个模板参数，一个是元素类型，一个容器类型，但只有元素类型是必要
的，在不指定容器类型时，默认的容器类型为deque。

16.1.1 定义

定义stack 对象的示例代码如下：

stack<int> s1;
stack<string> s2;

16.1.2 基本操作

入栈，如例：s.push(x);
出栈，如例：s.pop();注意，出栈操作只是删除栈顶元素，并不返回该元素。
访问栈顶，如例：s.top()
判断栈空，如例：s.empty()，当栈空时，返回true。
访问栈中的元素个数，如例：s.size()。

16.2 自定义stack实现

栈可以通过数组来实现，这里用得是vector

16.2.1 定义栈

16.2.2 判断是否为空

16.2.3 入栈

16.2.4 出栈

16.3 STL中queue实现

queue 模板类的定义在头文件中。与stack 模板类很相似，queue 模板类也需要两个模板参数，一个是元素类型，一个容器类型，元素类型是必要的，容器类型是可选的，默认为deque 类型。

16.3.1 定义

定义queue 对象的示例代码如下：

queue<int> q1;
queue<double> q2;

16.3.2 基本操作

入队：q.push(x); 将x 接到队列的末端。
出队：q.pop(); 弹出队列的第一个元素，但不会返回被弹出元素。
访问队首元素：q.front()，即最早被压入队列的元素。
访问队尾元素：q.back()，即最后被压入队列的元素。
判断队列空：q.empty()，当队列空时，返回true。
访问队列中的元素个数：q.size()