栈排序

栈排序

栈排序

栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：​​push​​​、​​pop​​​、​​peek​​​和​​isEmpty​​​。当栈为空时，​​peek​​​返回​​-1​​。

示例

输入：["SortedStack", "push", "push", "peek", "pop", "peek"][[], [1], [2], [], [], []]输出：[null,null,null,1,null,2]

输入： ["SortedStack", "pop", "pop", "push", "pop", "isEmpty"][[], [], [], [1], [], []]输出：[null,null,null,null,null,true]

题解

var SortedStack = function() { this.stack = []; this.auxStack = [];};/** * @param {number} val * @return {void} */SortedStack.prototype.push = function(val) { if(this.stack.length){ while(true){ var topValue = this.stack.pop(); if(topValue > val || topValue === undefined){ if(topValue !== undefined) this.stack.push(topValue); this.stack.push(val); while(this.auxStack.length) this.stack.push(this.auxStack.pop()); break; }else{ this.auxStack.push(topValue); } } }else{ this.stack.push(val); }};/** * @return {void} */SortedStack.prototype.pop = function() { return this.stack.pop();};/** * @return {number} */SortedStack.prototype.peek = function() { if (this.stack.length === 0) return -1; return this.stack[this.stack.length - 1];};/** * @return {boolean} */SortedStack.prototype.isEmpty = function() { return this.stack.length === 0;};/** * Your SortedStack object will be instantiated and called as such: * var obj = new SortedStack() * obj.push(val) * obj.pop() * var param_3 = obj.peek() * var param_4 = obj.isEmpty() */

思路

本题有一些限制条件，必须使用栈结构进行排序，且最多只能使用一个其他的临时栈存放数据，在调用方式上是使用​​new​​​实例化构造函数，那么在​​SortedStack​​​构造函数上拓展原型以供调用，首先在构造函数中定义两个栈数组，分别为排序的主栈以及辅助栈，这两个栈数组只调用其相关的栈操作方法。在入栈的​​push​​​操作时就对值进行排序，如果栈中没有值，那么就直接入栈，如果存在值则首先出栈栈顶值，判断该值与入栈的值的大小，如果栈顶的值大于入栈的值或者主栈中已经出栈完毕，那么首先判断出栈的值是否有效，有效则就将出栈的值首先入栈，然后将入栈的值进栈，然后将辅助栈中的值依次出栈并压入主栈，直到辅助栈空，然后结束循环，如果栈顶的值小于出栈的值且主栈并未出栈完毕，那么将该出栈的值压入辅助栈。由于主栈在入栈时就已经有序，那么出栈的​​pop​​​操作直接调用​​pop()​​​方法即可。对于​​peek​​​操作则首先判断栈长度，如果长度为​​0​​​则返回​​-1​​​，否则返回栈顶元素的值。对于​​isEmpty​​​操作则直接判断主栈长度是否为​​0​​即可。

每日一题

https://github.com/WindrunnerMax/EveryDay

题源

https://leetcode-cn.com/problems/sort-of-stacks-lcci

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。