假设我们在C++中,使用STL Stack和Queue
Stack: [1 2 3 4 5] <=> Queue: => [5 4 3 2 1] =>
递归检查数据条目在内容和顺序方面是否相同的最佳方法是什么?假设上面显示的堆栈和队列具有相同的数据和相同的顺序。我在概念上理解该做什么有问题,因为数据pop()的顺序相反。
wsxa1bj11#
一个部分递归的解决方案是递归地将队列中的所有元素弹出到辅助堆栈中,然后检查辅助堆栈和原始堆栈是否相同。
7tofc5zh2#
不需要递归,这将是一种无用的资源浪费。也不需要突变你的queue和stack(换句话说,这甚至对const也有效)。假设您的std::stack和std::queue都在内部使用相同类型的底层容器(如果使用默认值,则应该是std::dequeue),那么您可以访问queue和stack的受保护成员c(您的真实的容器),并使用运算符==对它们进行比较:
queue
stack
const
std::stack
std::queue
std::dequeue
c
==
#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才会发生相反的情况。)).
getContainer()
queue::push()
stack::push()
push_back()
pop()
**优点:**我懒得再重新实现一个受保护的成员访问器,所以我无耻地复制并修改了this one。
1cklez4t3#
如果递归不是指递归函数调用,而是指循环,那么答案如下:函数首先检查堆栈和队列的大小是否相同。如果它们的大小不同,函数返回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; }
soat7uwm4#
U可以不同时弹出它们,u可以尝试弹出其中一个(使用记录它的东西)ADT(不弹出队列,弹出堆栈),并到基址(size==1),与u比较,对队列做一些修改,并返回。然后用记录器做一些事情,每次递归调用当前队列的前端后,你就会找到答案。
4条答案
按热度按时间wsxa1bj11#
一个部分递归的解决方案是递归地将队列中的所有元素弹出到辅助堆栈中,然后检查辅助堆栈和原始堆栈是否相同。
7tofc5zh2#
不需要递归,这将是一种无用的资源浪费。也不需要突变你的
queue
和stack
(换句话说,这甚至对const
也有效)。假设您的
std::stack
和std::queue
都在内部使用相同类型的底层容器(如果使用默认值,则应该是std::dequeue
),那么您可以访问queue
和stack
的受保护成员c
(您的真实的容器),并使用运算符==
对它们进行比较:现在,如果您使用不同的容器类型作为
queue
和stack
的底层实现,您仍然可以使用相同的getContainer()
技术来获得按相同顺序排序的容器:queue::push()
和stack::push()
都调用底层容器的push_back()
方法,只有当您执行pop()
(以及类似的操作)时,stack
才会发生相反的情况。)).**优点:**我懒得再重新实现一个受保护的成员访问器,所以我无耻地复制并修改了this one。
1cklez4t3#
如果递归不是指递归函数调用,而是指循环,那么答案如下:函数首先检查堆栈和队列的大小是否相同。如果它们的大小不同,函数返回false。函数有一个本地堆栈对象,用于获取堆栈参数的元素。然后循环检查栈和队列的每个前端/顶部元素是否相等。如果相等,则循环继续到下一次迭代。如果不相等,函数返回false。如果循环结束时没有返回false,函数返回true。
soat7uwm4#
U可以不同时弹出它们,u可以尝试弹出其中一个(使用记录它的东西)ADT(不弹出队列,弹出堆栈),并到基址(size==1),与u比较,对队列做一些修改,并返回。然后用记录器做一些事情,每次递归调用当前队列的前端后,你就会找到答案。