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

时间:2022-09-12 17:40:35

【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 定义栈

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

16.2.2 判断是否为空

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

16.2.3 入栈

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

16.2.4 出栈

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


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()