c - 如何检查给定的两个堆栈在 C 中是否相等？

Question

我有一个作业问题，我必须检查两个堆栈并查看它们是否相等(如果它们包含相同顺序的相同数字)。

我的方法是

- Find the size of the stacks
 - If (size of stack 1 > size of stack 2 || size of stack 1 < size of stack 2)
 - Tell the user it doesn't equal
 - Set a to size of [n[ where en is the size of each stack, and pop all the elements of stack 1 to array1 and do the same for stack 2, but assign to stack2. 
 - then using a for loop check if a[I] = b[I]

我们只是被告知

您无法对堆栈的实现方式做出假设。如果你想使用任何其他功能，你需要实现它。

typedef​ ​struct​ { 
... ​// not known
} stack_t;

// creates a new stack
   stack_t* stack_create();



// pushes a given item to the stack

void​ stack_push(stack_t* s, ​int​ item);

// pops the top element from the stack // 
int​ stack_pop(stack_t* s);

 // checks if the stack is empty
bool​ stack_is_empty(stack_t* s); 

// frees the stack
void​ stack_free(stack_t* s);

Answer 1

在 O(n) 中不计算堆栈的大小，处理堆栈为空而不是另一个堆栈的特殊情况。

类似(提示算法)

bool are_equal(stack1, stack2) {
    while ( 1 ) {
       bool e1 = is_empty(stack1);
       bool e2 = is_empty(stack2);
       if (e1 && e2) return true;                    // equal
       if (e1 || e2) return false;                   // not equal
       if (pop(stack1) != pop(stack2)) return false; // not equal
    }
}