深圳建网站信科,荆门网站开发公司,wordpress 版本查询,网页设计服务目录
1. 用队列实现栈
2. 判断是否能组成三角形
3. 只出现一次的数字 II
附录
栈#xff08;Stack#xff09;和队列#xff08;Queue#xff09;的异同
1. 栈和队列的相同点
2. 栈和队列的不同点 1. 用队列实现栈
请你仅使用两个队列实现一个后入先出#xff08;…
目录
1. 用队列实现栈
2. 判断是否能组成三角形
3. 只出现一次的数字 II
附录
栈Stack和队列Queue的异同
1. 栈和队列的相同点
2. 栈和队列的不同点 1. 用队列实现栈
请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。
实现 MyStack 类
void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的返回 true 否则返回 false 。
注意
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。你所使用的语言也许不支持队列。 你可以使用 list 列表或者 deque双端队列来模拟一个队列 , 只要是标准的队列操作即可。
示例
输入
[MyStack, push, push, top, pop, empty]
[[], [1], [2], [], [], []]
输出
[null, null, null, 2, 2, false]解释 MyStack myStack new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False
提示
1 x 9最多调用100 次 push、pop、top 和 empty每次调用 pop 和 top 都保证栈不为空
进阶你能否实现每种操作的均摊时间复杂度为 O(1) 的栈换句话说执行 n 个操作的总时间复杂度 O(n) 尽管其中某个操作可能需要比其他操作更长的时间。你可以使用两个以上的队列。
代码
#include bits/stdc.h
using namespace std;
class MyStack
{
public:MyStack(){}void push(int x){std::queueint temp_queue;temp_queue.push(x);while (!_data.empty()){temp_queue.push(_data.front());_data.pop();}while (!temp_queue.empty()){_data.push(temp_queue.front());temp_queue.pop();}}int pop(){int x _data.front();_data.pop();return x;}int top(){return _data.front();}bool empty(){return _data.empty();}
private:std::queueint _data;
};int main()
{MyStack myStack;myStack.push(1);myStack.push(2);cout myStack.top() endl;cout myStack.pop() endl;cout myStack.empty() endl;return 0;
}
输出 2 2 0 2. 判断是否能组成三角形
根据输入的三角形的三边判断是否能组成三角形若可以则输出它的周长和三角的类型
代码
#includestdlib.h
#includestdio.hint main(void)
{int num1,num2,num3;printf(请输入第一条边);scanf(%d,num1);printf(请输入第二条边);scanf(%d,num2);printf(请输入第三条边);scanf(%d,num3);if(num1num2num3num2num3num1num1num3num2){if (num1*num1num2*num2num3*num3||num2*num2num3*num3num1*num1||num1*num1num3*num3num2*num2){printf ( %d、%d和%d可以组成直角三角形。,num1,num2,num3);printf (\n三角形周长:%d\n,num1num2num3);}else if (num1*num1num2*num2num3*num3||num2*num2num3*num3num1*num1||num1*num1num3*num3num2*num2){printf (%d、%d和%d可以组成钝角三角形。,num1,num2,num3);printf (\n三角形周长:%d\n,num1num2num3);}else{printf (%d、%d和%d可以组成锐角三角形,num1,num2,num3);printf (\n三角形周长:%d\n,num1num2num3);}}elseprintf(%d, %d和%d不能组成三角形。,num1,num2,num3);system(PAUSE);return 0;
}
输入输出 请输入第一条边3 请输入第二条边3 请输入第三条边3 3、3和3可以组成锐角三角形 三角形周长:9 请按任意键继续. . . 3. 只出现一次的数字 II
给你一个整数数组 nums 除某个元素仅出现 一次 外其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
示例 1
输入nums [2,2,3,2]
输出3示例 2
输入nums [0,1,0,1,0,1,99]
输出99提示
1 nums.length 3 * 104-231 nums[i] 231 - 1nums 中除某个元素仅出现 一次 外其余每个元素都恰出现 三次
进阶你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗 代码
#include bits/stdc.h
using namespace std;
class Solution
{
public:int singleNumber(vectorint nums){sort(nums.begin(), nums.end());int res 0;int i 0;for (int j 1; j nums.size(); j){if (nums[j] ! nums[i]){if (j - i 1){res nums[i];break;}else{i j;}}}if (i nums.size() - 1){res nums[i];}return res;}
};int main()
{Solution s;vector int vect {2,2,3,2};cout s.singleNumber(vect) endl;vect {0,1,0,1,0,1,99};cout s.singleNumber(vect) endl; return 0;
} 输出 3 99 附录
栈Stack和队列Queue的异同
线性表线性表是一种线性结构它是一个含有n0和结点的有限序列同一个线性表中的数据元素类型相同并且满足“一对一”的逻辑关系。
“一对一”的逻辑关系指的是除了表头和表尾的结点外其余每个结点有且仅有一个前驱和一个后继结点。
栈和队列是两种操作受限的线性表。
1. 栈和队列的相同点
1都是线性结构。 2插入操作都是限定在表尾进行。栈的栈顶队列的队尾 3都可以通过顺序存储结构和链式存储结构实现。 4插入和删除的时间复杂度都是O(1)在空间复杂度上两者也一样。 5多链栈和多链队列的管理模式可以相同。
2. 栈和队列的不同点
1删除元素的位置不同栈的操作在表尾进行队列的删除操作在表头进行。 2应用场景常见的栈的应用场景有括号问题的求解表达式的转换和求值函数调用和递归实现深度优先搜索遍历等常见的队列的应用场景包括计算机系统中各种资源的管理消息缓冲器的管理和广度优先遍历、还可用于实现打印机打印的冲突以及多个客户访问服务器的文件时满足先来先服务的原则等。 3顺序栈能够实现多栈空间共享而顺序队列不能。
