Сравните очередь и содержимое стека
Предположим, что мы имеем в C ++, используя STL Stack и Queue
Stack: [1 2 3 4 5] <=>
Queue: => [5 4 3 2 1] =>
Какой самый элегантный способ рекурсивной проверки того, что записи данных одинаковы с точки зрения содержания и порядка? Скажем, стек и очередь, показанные выше, имеют одинаковые данные и одинаковый порядок.
У меня проблема с концептуальным пониманием того, что делать, потому что данные pop () в обратном порядке.
Решение
Частично рекурсивное решение состоит в том, чтобы рекурсивно вытолкнуть все элементы из очереди во вспомогательный стек, а затем проверить, совпадают ли вспомогательный стек и исходный стек. Эта проверка может быть выполнена также рекурсивно.
Другие решения
Нет необходимости в рекурсии, это было бы бесполезной тратой ресурсов. Не нужно мутировать ваш queue а также stack либо (другими словами, это работает даже на const«S).
Предполагая ваш std::stack а также std::queue оба используют один и тот же тип нижележащего контейнера (который должен быть std::dequeue если вы использовали значение по умолчанию), то вы можете получить доступ к защищенным членам c (ваши настоящие контейнеры) обоих queue а также stack и сравнить их с помощью оператора ==:
#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;
}
Теперь, если вы используете разные типы контейнеров в качестве базовой реализации queue а также stack, вы все еще можете использовать то же самое getContainer() Техника для получения контейнеров, которые отсортированы в том же порядке: оба queue::push() а также stack::push() вызвать базовый контейнер push_back() метод, это только когда ты pop() (и аналогичные операции), для которых происходит реверсирование stack, Поскольку эти нижележащие контейнеры будут в том же порядке, вы сможете легче сравнивать вещи (оставьте читателю в качестве упражнения;)).
Кредит: Я был слишком ленив, чтобы снова переопределить защищенный элемент доступа, поэтому я бессовестно копировал и изменял этот.
Если под рекурсией вы подразумеваете не рекурсивный вызов функции, а просто зацикливание, то вот ответ. Функция сначала проверяет, совпадают ли размер стека и очереди. Если они не одинакового размера, функция возвращает false. Функция имеет локальный объект стека, который получает элементы параметра стека, для того, чтобы получить в обратном порядке как параметр стека, который передается внутрь. Затем цикл проверяет каждый передний / верхний элемент стека и очереди на равенство. Если равен, цикл продолжается до следующей итерации. Если не равно, функция возвращает false. Если цикл завершается без возврата false, функция возвращает 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;
}
Вы можете не вытолкнуть их одновременно, вы можете попытаться вытолкнуть один (использовать что-то запишите) ADT (не выдвигать очередь, всплывающий стек) и в базу (размер == 1), и вы сравните и внесли некоторые изменения в очередь и возвращается. Затем сделайте что-нибудь с рекордером и передней частью текущей очереди после каждого вызова рекурсии, вы найдете ответ.
detector