上海网站建设方案,北京网站策划公司,下载的asp网站怎么打开,设计制作小车教学视频之前我们就讲过队列#xff0c;栈的基础知识#xff0c;笔者之前有过详细的介绍#xff0c;感兴趣的可以根据笔者的个人主页进行查找#xff1a;https://blog.csdn.net/weixin_64308540/?typelately225. 用队列实现栈请你仅使用两个队列实现一个后入先出#xff08;LIFO栈的基础知识笔者之前有过详细的介绍感兴趣的可以根据笔者的个人主页进行查找https://blog.csdn.net/weixin_64308540/?typelately225. 用队列实现栈请你仅使用两个队列实现一个后入先出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 都保证栈不为空 进阶你能否仅用一个队列来实现栈。首先我们需要知道的是队列先进先出 栈先进后出模式所以一个队列不能实现栈只能用两个队列我们在MyStack文件首先我们需要定义一个两个队列 private QueueInteger qu1;private QueueInteger qu2; 然后我们需要对这两个队列进行初始化 //初始化两个队列public MyStack(){qu1new LinkedList();qu2new LinkedList();}接下来我们就需要进入真正的主题了将元素压入栈 // 将元素压入栈 找不为空的队列public void push(int x){if (!qu1.isEmpty()){qu1.offer(x);}else if (!qu2.isEmpty()){qu2.offer(x);}else {qu1.offer(x);}}
将元素压入栈这个思路很简单主要还是要找不为空的队列qu1与qu2两个队列哪个队列不为空就放哪个如果两个队列都为空则放qu1队列移除并且返回栈顶元素 //移除并且返回栈顶元素//出栈并返回出size-1个元素到另一个队列中public int pop(){if (empty()){return -1;//如果两个队列都为空则说明当前栈为空}if (!qu1.isEmpty()){int sizequ1.size();for (int i 0; i size-1; i) {int valqu1.poll();qu2.offer(val);}return qu1.poll();//最后qu1剩余1个就是我们想要移除的}else {int sizequ2.size();for (int i 0; i size-1; i) {int valqu2.poll();qu1.offer(val);}return qu2.poll();//最后qu2剩余1个就是我们想要移除的}}在这个思路中我们需要将第一个栈不为空的size个元素移到第二个栈为空的里面最后所剩余的哪一个就是我们想要移除的元素在这里我们用到了判断栈是否为空 //如果栈是空的则返回true,否则返回falsepublic boolean empty(){return qu1.isEmpty() qu2.isEmpty();//确保两个队列都不为空}返回栈顶元素peek()偷看//返回栈顶元素peek()偷看public int pop(){if (empty()){return -1;}if (!qu1.isEmpty()){int sizequ1.size();int val-1;for (int i 0; i size; i) {valqu1.poll();qu2.offer(val);}return val;}else {int sizequ2.size();int val-1;for (int i 0; i size; i) {valqu2.poll();qu1.offer(val);}return val;}}主要的思路判断是否为空若qu1不为空则通过val将qu1中的数据全部转移到qu2中最后一次转移的值就是我们想要的232. 用栈实现队列请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty实现 MyQueue 类void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空返回 true 否则返回 false说明你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque双端队列来模拟一个栈只要是标准的栈操作即可。 示例 1输入[MyQueue, push, push, peek, pop, empty]
[[], [1], [2], [], [], []]输出[null, null, null, 1, 1, false]解释MyQueue myQueue new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false 提示1 x 9最多调用 100 次 push、pop、peek 和 empty假设所有操作都是有效的 例如一个空的队列不会调用 pop 或者 peek 操作 进阶你能否实现每个操作均摊时间复杂度为 O(1) 的队列换句话说执行 n 个操作的总时间复杂度为 O(n) 即使其中一个操作可能花费较长时间。初始准备阶段:准备两个栈 private StackInteger stack1;private StackInteger stack2;然后我们在对准备好的两个栈进行初始化 public MyQueue() {stack1new Stack();stack2new Stack();}下面我们就开始步入正轨将元素x 推到队列的队尾 //将元素x推到队列的末尾public void push(int x){stack1.push(x);//往栈中放入元素全部放入第一个栈中}从队列的开头移除并返回元素 //从队列的开头移除并返回元素public int pop(){if (empty()){return -1;}if (stack2.empty()){while (!stack1.empty()){stack2.push(stack1.pop());}}return stack2.pop();//将第2个栈的栈顶元素出栈}在这个过程中我们规定第一个栈输入栈第二个栈输出栈当第二个栈为空时则将第一个栈的所有元素都导入第二个栈中在这个代码中我们自己定义了一个判断栈是否为空的函数 //如果队列为空返回true,否则返回falsepublic boolean empty(){return stack1.empty() stack2.empty();}返回队列开头的元素偷看 //返回队列开头的元素偷看public int peek(){if (empty()){return -1;}if (stack2.empty()){while (!stack1.empty()){stack2.push(stack1.pop());}}//偷看第2个栈的栈顶元素return stack2.peek();}在上述的两个列题中我们分别用用队列实现栈用栈实现队列作为两个小小的列题我们最后可以得出一下规律- 用队列实现栈 - 优点因为栈是后进先出的结构用队列可以有效的实现这一性质即添加元素为一个队列的末端而移除元素只允许从另一个队列的末端移除。 - 缺点实现较为复杂需要两个队列来进行实现还需要额外的空间来存储数据。- 用栈实现队列 - 优点实现简单只需要用一个栈来存储数据另一个栈仅仅用于存储另一个栈的临时元素。 - 缺点由于栈只能实现先进后出的结构它不能有效的实现队列的先进先出的特性。
