1
\$\begingroup\$

Is there a nondestructive way to check whether two queues or stacks contain identical values? For example:

foo=ds_queue_create();
ds_queue_enqueue(foo, 1);
ds_queue_enqueue(foo, 2);

bar=ds_queue_create();
ds_queue_enqueue(bar, 3);
ds_queue_enqueue(bar, 1);
ds_queue_enqueue(bar, 2);
ds_queue_dequeue(bar);

return(equality_test(foo, bar));

should return true

Options I know of:

  • foo == bar returns false, presumably because it's checking whether they point to the same queue as opposed to having the same values.
  • ds_queue_write(foo) == ds_queue_write(bar) seems to be sensitive to the queues' histories. If I just enqueue [1,2] on each queue, it gives true. But because I added and then dequeued an irrelevant value on bar, the serialized strings differ even though the current values are identical.
  • Iterating through the items one at a time and checking equality works for arrays, but doing this using ds_queue_dequeue destroys the queues. Is there a nondestructive way to read elements of a queue, other than the head and tail?
  • Per liggiorgio's comment below, I could duplicate the queues with ds_queue_copy and destructively iterate over the duplicates -- is this the best way?

As far as I know the same issues apply to stacks.

\$\endgroup\$
1
  • \$\begingroup\$ Your third approach is fine, you could create a copy of each data structure you need and then check their respective values: the original data is fine since you're working on clones. \$\endgroup\$ – liggiorgio Feb 5 '19 at 0:10
1
\$\begingroup\$

Your third approach is just fine, apart from being 'destructive' towards original data. But you can easily copy and clone the data to separate structures, and use these instead to check equality among values.

You may want to use simple ds_lists and take advantage of the function ds_list_find_value() to search for L1's values in L2's.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for the suggestion! I had some unrelated reasons for preferring a queue, but using a list does sound like it might be less of a faff. \$\endgroup\$ – octern Feb 5 '19 at 0:18
  • \$\begingroup\$ Then you can keep a copy of a ds_queue to dequeue the next value from, and copy & convert the other data in a ds_list to exploit its function ds_list_find_value and avoid implementing a search feature yourself. \$\endgroup\$ – liggiorgio Feb 5 '19 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.