将堆栈中的 A B C D 反转，最少需要多少次 push 操作？

Question

我在 Javascript

中使用 push 和 pop 操作编码来反转 ABCD 字符串

var count = 0;
function reverse(str) {
    let stack = [];
    // push letter into stack
    for (let i = 0; i < str.length; i++) {
        stack.push(str[i]);
        count++
    }
    // pop letter from the stack
    let reverseStr = '';
    while (stack.length > 0) {
        reverseStr += stack.pop();
    }
    return reverseStr;
}

console.log(reverse("ABCD") + count);

逆向ABCD最小推数是多少？

Answer 1

如果你使用 JS，你甚至不需要推送操作 str.split('').reverse().join('') 顺便说一句，它只需要 3 次推送操作。

Answer 2

推送操作的最小数量等于字符串的长度，因为堆栈遵循后进先出顺序。

Answer 3

最大数量应为 3 或 4，具体取决于您的操作方式。首先，你应该使用 unshift() 而不是 push() 因为你真的只需要 push 一个字符到数组的 front 。所以：

let count;
function reverse(str) {
    count = 0;
    let stack = [];
    // push letter into stack
    for (let i = 0; i < str.length; i++) {
        stack.unshift(str[i]);
        count++
    }
    return stack.join("");
}

let stringA = "ABCD";

console.log(stringA + " => " + reverse(stringA) + ": " + count);

但是，正如其他人所建议的那样，您可以移动个字母，从最后一个字符之前的字母向后移动，并将它们移动到末尾：

let count;

function reverse2(str) {
  count = 0;
  let str2 = str.split("");
  let sLength = str2.length;
  for (let i = (sLength - 2); i >= 0; i--) {
    let s = str2.splice(i, 1).toString();
    str2.push(s);
      count++
  }
  return str2.join("");
}
let stringB = "ABCD";

console.log(stringB + " => " + reverse2(stringB) + ": " + count);

在这两种情况下，您可以检查匹配的连续字符 - 例如，在 good 中，您有两个 o。但这会使事情复杂化，因为您会不断检查它。

将堆栈中的 A B C D 反转，最少需要多少次 push 操作？

What is the minimum number of push operation in reversing A B C D in stack?

javascript

queue

stack

push

data-structures