Suppose we have in c++, using STL Stack and Queue
Stack: [1 2 3 4 5] <=>
Queue: => [5 4 3 2 1] =>
What is the most elegant way to recursively check that the data entries are the same in terms of content and order? Say the stack and queue shown above have the same data and same order.
I'm having a problem conceptually understanding what to do because the data pop() in opposite order.
A partially recursive solution would be to recursively pop all the elements from the queue in an auxiliary stack and then check if the auxiliary stack and the original stack are the same. This check can be done also recursively.
No need for recursion, this would be a useless waste of resources. No need to mutate your queue and stack either (in other words, this works even on const's).
Assuming your std::stack and std::queue both internally use the same type of underlying container (which should be std::dequeue if you used the default) then you can access the protected members c (your real containers) of both queue and stack and compare them using operator ==:
#include <iostream>
#include <queue>
#include <stack>
template<typename Adapter>
typename Adapter::container_type const& getContainer(const Adapter& adapter) {
struct AccessProtected : private Adapter {
static typename Adapter::container_type const& getContainer(const Adapter& adapter) { return adapter.*&AccessProtected::c; }
};
return AccessProtected::getContainer(adapter);
}
int main() {
std::queue<int> queue;
std::stack<int> stack;
for (int i = 0; i < 10; ++i) {
queue.push(i);
stack.push(i);
}
std::cout << (getContainer(queue) == getContainer(stack) ? "equal" : "not equal") << std::endl;
return 0;
}
Now, if you use different containers types as the underlying implementation of queue and stack, you can still use that same getContainer() technique to obtain containers that are sorted in the same order: both queue::push() and stack::push() call the underlying container's push_back() method, it's only when you pop() (and similar operations) that the reversing happens for stack. Since those underlying containers will be in the same order, you can then compare things more easily (left as an exercise to the reader ;)).
Credit: I was too lazy to reimplement a protected member accessor again, so I shamelessly copied and modified this one.
If by recursion, you do not mean a recursive function call, but just looping, then here's an answer. The function first checks if the stack and queue are the same size. If they aren't the same size, the function returns false. The function has a local stack object that gets the stack parameter's elements, in order to be popped in the reverse order as the stack parameter that is passed in. Then a loop checks each front/top element of stack and queue for equality. If equal, the loop continues to the next iteration. If not equal, the function returns false. If the loop finishes without returning false, the function returns true.
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
bool check(stack<int> stackPar, queue<int> queuePar)
{
if (stackPar.size() != queuePar.size())
{
return false;
}
stack<int> reverseStack;
for (int i = 0, initialSize = stackPar.size(); i < initialSize; ++i)
{
reverseStack.push(stackPar.top());
stackPar.pop();
}
for (int i = 0; i < reverseStack.size(); ++i)
{
if (reverseStack.top() == queuePar.front())
{
reverseStack.pop();
queuePar.pop();
}
else
{
return false;
}
}
return true;
}
int main()
{
stack<int> myStack;
queue<int> myQueue;
for(int i = 1; i <= 5; ++i)
{
myStack.push(i);
myQueue.push(i);
}
cout << "Stack and queue are ";
cout << ( check(myStack, myQueue) ? "equal." : "not equal." ) << endl;
return 0;
}
U may not pop them simultaneously, u can try to pop one(use something record it) ADT(dont pop queue, pop stack), and to the base(size==1), and u compare and made some change to the queue, and returns. Then do something with the recorder and the currently queue's front after every recursion calls, you will find the answer.
