堆栈伪码比较

Question

我需要检查两个队列，（a和b）以查看它们是否相同（相同顺序的相同元素）。最后，两个队列需要看起来和开始一样。仅使用push，pop，top和EmptyStack。

这就是我所拥有的，但对我来说没有意义。

boolean ABSimilar(A,B){
    if (A.EmptyStack() != B.EmptyStack()) return false; // stacks same
    if (A.EmptyStack() && B.EmptyStack()) return true; // stacks are the same
    A_element = A.pop(); // grab elements
    B_element = B.pop();
    if A_element == null && B_element != null {
      A.push(A_element); // if !=, restore them and return false
      B.push(B_element);
      return false;
    }
    answer = ABASimilar(A, B); // compare
    A.push(A_element);  // restore
    B.push(B_element);
    return answer; // return answer
}

Answer 1

你的逻辑几乎是对的。

您缺少的是正在从A中删除的元素与从B中删除的元素的正确比较。

您只检查A_element是否为空且B_element不是，并且在这种情况下返回false。

如果A_element不为null且B_element为null，或者它们都不为null，但彼此不相等，则还应返回false。

只有当它们彼此相等时（无论是null还是两者都不为null和相等），你应该进行递归调用，这将比较其余的堆栈。

boolean isABSimilar(A,B){
    if (A.isEmptyStack() != B.isEmptyStack()) 
        return false; // stacks same
    if (A.isEmptyStack() && B.isEmptyStack()) 
        return true; // stacks are the same
    A_element = A.pop(); // grab elements
    B_element = B.pop();
    if ((A_element == null && B_element != null) || (A_element != null && !A_element.equals(B_element))) {
        A.push(A_element); // if !=, restore them and return false
        B.push(B_element);
        return false;
    }
    answer = isABASimilar(A, B); // compare
    A.push(A_element);  // restore
    B.push(B_element);
    return answer; // return answer
}

Answer 2

你的代码有一些小问题。试试这样：

boolean isABSimilar(A,B){
    if (A.isEmptyStack() && B.isEmptyStack()) return true; // stacks are the same

    if (A.isEmptyStack()) return false;  // stacks are different
    if (B.isEmptyStack()) return false;
    if (A.top() != B.top()) return false;

    A_element = A.pop(); // grab elements
    B_element = B.pop();

    answer = isABASimilar(A, B); // ckech remaining stack

    A.push(A_element);  // restore
    B.push(B_element);

    return answer; // return answer
}

请注意，只有当您知道堆栈的大小非常小时才会使用上述类似的递归方法。

另请注意，由于多种原因，上述“代码”无法编译为C代码。例：

1. boolean isABSimilar(A,B)不是有效的函数原型
2. A_element和B_element和answer未定义

您需要在编译之前修复它。

在C中没有内置的堆栈类型，因此我假设它是代码中的自定义类型。就像是：

struct Stack
{
    ... Member function pointers
    ... Member data
};

在这种情况下，您的函数应如下所示：

int isABSimilar(struct Stack A, struct Stack B){
    int answer;
    int A_element;  // I just assume that data type is int
    int B_element;  // but it can be other types (OP never told us)

    ... the code from above