62 lines
3.1 KiB
JavaScript
62 lines
3.1 KiB
JavaScript
/**
|
||
* @param {Stack} stack
|
||
* @description 将一个栈的所有元素按照从栈底到栈顶依此从小到大排列
|
||
* 思路：假设我们有一个栈[1,7,2,2,5,3]，我们把它想象成空的，第一步我们插入1，由于现在栈是空的，所以直接push(1)
|
||
* 即可，第二步，我们插入7,按照要求栈顶的元素应该要比栈底的元素小，所以7不能直接push，所以我们需要pop(1)，之后再
|
||
* 判断是否可以插入7，当1 弹出后由于没有元素直接push(7),之后我们再把弹出的1重新压入栈顶即可，此时栈里面有两个元素
|
||
* [7,1],我们继续来压入2，2比栈顶元素大所以弹出栈顶元素，此时发现栈顶元素比2大符合要求，所以直接push(2),之后再把之前
|
||
* 的1压入即可，此时栈里面有3个元素[7,2,1],继续压入2同理，之后压入5，我们比较栈顶元素和5，发现5比栈顶元素大，所以弹出
|
||
* 1，之后再比较，发现比此时的栈顶元素2大，所以弹出2，之后再比较2，发现还是大，所以继续弹出此时的栈顶元素2，之后发现没有7
|
||
* 大，所以此时直接push(5)即可，并且把之前弹出的元素依此push即可，此时栈里面的内容为[7,5,2,2,1]，最后一个元素3同理。
|
||
*
|
||
* 分析：上面的思路我们从栈底元素开始处理，再不借助另一个“后进先出”的数据结构，我们只能借助递归，递归本身就带空间，回溯的时候
|
||
* 处理即可，我们在插入的时候发现每次的弹出的数据都需要保留，并且还需要按着原顺序插入，在这里我们也需要一个递归的插入函数，原因
|
||
* 很简单，我们需要保留当前弹出的值，并且依此插入，所以创建两个函数，第一个函数sortStack,这个函数把整个栈弹出，从栈底元素开始处理
|
||
* 依此调用insertInSortedOrder把当前元素插入到正确的地方。
|
||
*/
|
||
import Stack from '../stack/index.js';
|
||
|
||
/**
|
||
* 排序栈
|
||
*
|
||
* @param {Stack} stack 要排序的栈
|
||
*/
|
||
function sortStack(stack) {
|
||
if (stack.isEmpty()) return; // 如果栈为空，递归终止
|
||
const cur = stack.pop(); // 保存栈顶元素
|
||
sortStack(stack); // 递归排序栈中的其他元素
|
||
// 将当前栈顶元素插入到已排序的栈中
|
||
insertInSortedOrder(stack, cur);
|
||
}
|
||
|
||
/**
|
||
* 将元素插入到已排序栈中
|
||
*
|
||
* @param {Stack} stack 要插入的栈
|
||
* @param {number} item 要插入的元素
|
||
*/
|
||
function insertInSortedOrder(stack, item) {
|
||
// 如果栈为空，或者栈顶元素大于等于当前元素，直接将当前元素插入栈中
|
||
if (stack.isEmpty() || stack.peek() >= item) {
|
||
stack.push(item);
|
||
} else {
|
||
// 如果栈顶元素小于当前元素，弹出栈顶元素
|
||
const cur = stack.pop();
|
||
// 递归插入当前元素
|
||
insertInSortedOrder(stack, item);
|
||
// 将弹出的栈顶元素重新压入栈中
|
||
stack.push(cur);
|
||
}
|
||
}
|
||
|
||
// 测试代码
|
||
const stack = new Stack([1, 7, 2, 2, 5, 3]);
|
||
|
||
console.log('Original Stack:');
|
||
stack.print(); // 输出: 1, 7, 2, 2, 5, 3
|
||
|
||
sortStack(stack); // 排序栈
|
||
|
||
console.log('Sorted Stack:');
|
||
stack.print(); // 输出: 1, 2, 2, 3, 5, 7
|