程序员面试题精选100题(18)-用两个栈实现队列[数据结构] |
您所在的位置:网站首页 › laravel面试题 › 程序员面试题精选100题(18)-用两个栈实现队列[数据结构] |
本文转自: http://zhedahht.blog.163.com/blog/static/2541117420073293950662/ 题目:某队列的声明如下: template class CQueue { public: CQueue() {} ~CQueue() {} void appendTail(const T& node); // append a element to tail void deleteHead(); // remove a element from head private: T> m_stack1; T> m_stack2; };
分析:从上面的类的声明中,我们发现在队列中有两个栈。因此这道题实质上是要求我们用两个栈来实现一个队列。相信大家对栈和队列的基本性质都非常了解了:栈是一种后入先出的数据容器,因此对队列进行的插入和删除操作都是在栈顶上进行;队列是一种先入先出的数据容器,我们总是把新元素插入到队列的尾部,而从队列的头部删除元素。 我们通过一个具体的例子来分析往该队列插入和删除元素的过程。首先插入一个元素a,不妨把先它插入到m_stack1。这个时候m_stack1中的元素有{a},m_stack2为空。再插入两个元素b和c,还是插入到m_stack1中,此时m_stack1中的元素有{a,b,c},m_stack2中仍然是空的。 这个时候我们试着从队列中删除一个元素。按照队列先入先出的规则,由于a比b、c先插入到队列中,这次被删除的元素应该是a。元素a存储在m_stack1中,但并不在栈顶上,因此不能直接进行删除。注意到m_stack2我们还一直没有使用过,现在是让m_stack2起作用的时候了。如果我们把m_stack1中的元素逐个pop出来并push进入m_stack2,元素在m_stack2中的顺序正好和原来在m_stack1中的顺序相反。因此经过两次pop和push之后,m_stack1为空,而m_stack2中的元素是{c,b,a}。这个时候就可以pop出m_stack2的栈顶a了。pop之后的m_stack1为空,而m_stack2的元素为{c,b},其中b在栈顶。 这个时候如果我们还想继续删除应该怎么办呢?在剩下的两个元素中b和c,b比c先进入队列,因此b应该先删除。而此时b恰好又在栈顶上,因此可以直接pop出去。这次pop之后,m_stack1中仍然为空,而m_stack2为{c}。 从上面的分析我们可以总结出删除一个元素的步骤:当m_stack2中不为空时,在m_stack2中的栈顶元素是最先进入队列的元素,可以pop出去。如果m_stack2为空时,我们把m_stack1中的元素逐个pop出来并push进入m_stack2。由于先进入队列的元素被压到m_stack1的底端,经过pop和push之后就处于m_stack2的顶端了,又可以直接pop出去。 接下来我们再插入一个元素d。我们是不是还可以把它push进m_stack1?这样会不会有问题呢?我们说不会有问题。因为在删除元素的时候,如果m_stack2中不为空,处于m_stack2中的栈顶元素是最先进入队列的,可以直接pop;如果m_stack2为空,我们把m_stack1中的元素pop出来并push进入m_stack2。由于m_stack2中元素的顺序和m_stack1相反,最先进入队列的元素还是处于m_stack2的栈顶,仍然可以直接pop。不会出现任何矛盾。 我们用一个表来总结一下前面的例子执行的步骤: 操作 m_stack1 m_stack2 append a {a} {} append b {a,b} {} append c {a,b,c} {} delete head {} {b,c} delete head {} {c} append d {d} {c} delete head {d} {} 总结完push和pop对应的过程之后,我们可以开始动手写代码了。参考代码如下: /// // Append a element at the tail of the queue /// template void CQueue::appendTail(const T& element) { // push the new element into m_stack1 m_stack1.push(element); } /// // Delete the head from the queue /// template void CQueue::deleteHead() { // if m_stack2 is empty, and there are some // elements in m_stack1, push them in m_stack2 if(m_stack2.size() T& data = m_stack1.top(); m_stack1.pop(); m_stack2.push(data); } } // push the element into m_stack2 assert(m_stack2.size() > 0); m_stack2.pop(); } 扩展:这道题是用两个栈实现一个队列。反过来能不能用两个队列实现一个栈?如果可以,该如何实现? 拓展题目答案: 解法: 1.有两个队列q1和q2,先往q1内插入a,b,c,这做的都是栈的push操作。 2.现在要做pop操作,即要得到c,这时可以将q1中的a,b两个元素全部dequeue并存入q2中,这时q2中元素为a,b,对q1再做一次dequeue操作即可得到c。 3.如果继续做push操作,比如插入d,f,则把d,f插入到q2中, 4.此时若要做pop操作,则做步骤2 5.以此类推,就实现了用两个队列来实现一个栈的目的。 注意在此过程中,新push进来的元素总是插入到非空队列中,空队列则用来保存pop操作之后的那些元素,那么此时空队列不为空了,原来的非空队列变为空了,总是这样循环。 对于push和pop操作,其时间为O(n). #include #include #include using namespace std; // 两个队列实现一个栈 template class CStack { public: CStack() {} ~CStack() {} void mypush(const T& element); void mypop(); private: deque m_queue1; deque m_queue2; }; template void CStack::mypop() { if (m_queue1.size() == 0) { while (m_queue2.size() > 1) { T& data = m_queue2.front(); m_queue2.pop_front(); m_queue1.push_back(data); } assert(m_queue2.size() == 1); //确保队列2内有一个元素 T& result = m_queue2.front(); m_queue2.pop_front(); cout |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |