字节真题-仅用递归反转栈📌

// 法一：栈顶弹出元素
 
const arr: number[] = [];
for (let i = 1; i < 6; i++) {
  arr.push(i);
}
 
console.log(arr);
console.log(reverseStack(arr));
 
function reverseStack(stack: number[]) {
  if (stack.length <= 1) {
    return stack;
  }
 
  let top = stack.pop() as number; //stack: 1,2,3,4
  stack = reverseStack(stack) as number[]; // stack:4,3,2,1
  stack = pushFirst(stack, top);
  return stack;
}
 
function pushFirst(stack: number[], top: number) {
  if (stack.length === 0) {
    stack.push(top);
    return stack;
  }
  let temp = stack.pop() as number; // stack: 4,3,2
  stack = pushFirst(stack, top);
  stack.push(temp);
  return stack;
}

// 法二：取出栈底元素
 
const arr: number[] = [];
for (let i = 1; i < 6; i++) {
  arr.push(i);
}
 
console.log(arr);
console.log(reverseStack1(arr));
 
function reverseStack1(stack: number[]) {
  if (stack.length <= 1) {
    return stack;
  }
 
  let last = getLast(stack); //stack: 2,3,4,5 last = 1
  stack = reverseStack1(stack) as number[]; // stack:4,3,2,1
  stack.push(last);
  return stack;
}
 
function getLast(stack: number[]): number {
  if (stack.length === 1) {
    return stack.pop() as number;
  }
  let temp = stack.pop() as number; // stack: 1,2,3,4 temp = 5
  let last = getLast(stack); // stack: 2,3,4
  stack.push(temp); // stack: 2,3,4,5
  return last;
}