首页 > C++的STL队列实现栈

C++的STL队列实现栈

使用C++的队列STL实现一个栈的数据结构

实现以下四个函数:

1.push(x) : 将元素x压入栈中

2.pop() : 弹出(移除)栈顶元素

3.top() : 返回栈顶元素

4.empty() : 判断栈是否是空

队列的数据结构为先入先出,栈的数据结构为先入后出;

即队列的元素顺序与栈中元素的顺序是相反的,所以只需要保证后面插入的元素是在前面的元素之前能够被弹出即可。

在这里插入图片描述

转换成栈之后的存储形态,弹出队列头部的元素即类似与弹出栈顶元素

在这里插入图片描述

这里插入元素时维护一个临时队列,即可将原先队列中的元素顺序做一个逆置调整。

实现算法如下(文末有测试代码):

void push(int x) { queue<int> tmp_queue;tmp_queue.push(x);/*对所有原队列的元素做顺序调整*/while (!data.empty()){ tmp_queue.push(data.front());data.pop();}/*将调整后的顺序放入原队列,此时该队列元素顺序已经为栈存储的元素顺序*/while (!tmp_queue.empty()){ data.push(tmp_queue.front());tmp_queue.pop();}
}

实现如下:

#include 
#include 
#include using namespace std;
class My_stack { private:queue<int> data;public:void push(int x) { queue<int> tmp_queue;tmp_queue.push(x);while (!data.empty()){ tmp_queue.push(data.front());data.pop();}while (!tmp_queue.empty()){ data.push(tmp_queue.front());tmp_queue.pop();}}/*弹出元素,即弹出队列头部元素*/int pop() { int x = data.front();data.pop();return x;}/*此时队列中的元素已经和栈存储的元素同步了,直接返回对头元素*/int top() { return data.front();}   bool empty(){ return data.empty();}
};int main() { My_stack s;cout << "construct the stack " << endl;int tmp;for (int i = 0;i < 5; ++i) { cin >> tmp;s.push(tmp);}cout << "top " << s.top() << endl;cout << "pop " << s.pop() << endl;cout << "top " << s.top() << endl;s.push(10);cout << "top after push '10' " << s.top() << endl;return 0;
}

输出如下:

construct the stack 
1 3 4 5 2
top 2
pop 2
top 5
top after push '10' 10

更多相关:

  • 栈stack:stack 后入先出(LIFO) q.top()获取栈顶元素(并不删除)q.pop()删除栈顶元素q.push(x)向栈中加入元素q.empty()判断栈是否为空 队列queue:先入先出(FIFO)   q.front()获取队首元素(并不删除)q.pop()删除队首元素q.push(x)向队列中加入元素q....

  • resize(),设置大小(size); reserve(),设置容量(capacity); size()是分配容器的内存大小,而capacity()只是设置容器容量大小,但并没有真正分配内存。 打个比方:正在建造的一辆公交车,车里面可以设置40个座椅(reserve(40);),这是它的容量,但并不是说它里面就有了40个座椅,只能说...

  • v-for="(index,$i) in total" :key="$i":style="{left:`${itemWidth*((index-1)%rowItemCount)}px`,top:`${itemHeight*(Math.ceil(index/rowItemCount)-1)}px`}" //total是显示总数量 //l...

  •   技巧一(推荐指数★★★★★) 采用top、right、bottom、left,可以不在乎父元素的宽度和高度,对GPU损耗低于技巧三,但是对浏览器内存的消耗高于技巧三 .子元素 {/*父元素需要position: relative|absolute;*/position: absolute;margin: auto;to...

  • 设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。 push(x) – 将元素 x 推入栈中。pop() – 删除栈顶的元素。top() – 获取栈顶元素。getMin() – 检索栈中的最小元素。 示例: MinStack minStack = new MinStack(); minStack...

  • 使用内部存储结构为栈的方法实现一个队列,要求实现该队列的如下方法: 1.push(x) : 将元素x压入队列中 2.pop() : 弹出(移除)队列头部元素 3.peek() : 返回队列头部元素(即为front) 4.empty() : 判断队列是否是空 栈的数据结构为先入后出,队列的数据结构为先入先出 使用栈来实现队列,同样想要...

  • 使用队列实现栈的下列操作: push(x) – 元素 x 入栈pop() – 移除栈顶元素top() – 获取栈顶元素empty() – 返回栈是否为空 队列的特点:先入先出 栈的特点:后入先出 即我们每次添加元素到队列时,想要达到栈的效果,则需要调整当前元素到队列头部 方法一:双队列 一个临时队列保存push进去的元素,将...

  • Queue除了前面介绍的实现外,还有一种双向的Queue实现Deque。这种队列允许在队列头和尾部进行入队出队操作,因此在功能上比Queue显然要更复杂。下图描述的是Deque的完整体系图。需要说明的是LinkedList也已经加入了Deque的一部分(LinkedList是从jdk1.2 开始就存在数据结构)。   Deque在Q...

  • 网络流量队列优先级相关知识点 Qdisc(quick disconnect)快速分离,断开;是一种排队规则,实现对流量的优先级管理.   涉及随机公平队列,令牌桶过滤器,分层令牌桶,FIFO, /*  *CopyRight (c) 2014-02-05 by Ruiy use to CopyLift!!!!  * */   ...