DSP

用两个栈实现一个队列

2019-07-13 18:14发布

站内文章 / DSP
12205 0 1111
设有栈A、B。 入队： 直接将元素push到A中。 出队： 若栈B不为空，从B中pop； 若B为空，将A中元素逐个pop，并push到B中；然后B中pop出栈顶元素。 直观上，是将A栈的栈底和和B栈的栈底对接，从形成了队列的性质。 本质上：用两个栈的pop、push实现队列的enqueue、dequeue 操作。 用C++描述，题目大致是这样的： 已知下面Stack类及其3个方法Push、Pop和 Count，请用2个Stack实现Queue类的入队(Enqueue)出队(Dequeue)方法。 class Stack{…public:         void Push(int x); // Push an element in stack;         int Pop();  // Pop an element out of stack;         int Count() const;     // Return the number of the elements in stack;…}; class Queue{…public:         void Enqueue(int x);         int Dequeue(); private:         Stack s1;         Stack s2;…}; 分析：从上面的类的声明中，我们发现在队列中有两个栈。因此这道题实质上 是要求我们用两个栈来实现一个队列。相信大家对栈和队列的基本性质都非常了解了：栈是一种后入先出的数据容器，因此对队列进行的插入和删除操作都是在栈顶 上进行；队列是一种先入先出的数据容器，我们总是把新元素插入到队列的尾部，而从队列的头部删除元素。 我们通过一个具体的例子来分析往该队列插入和删除元素的过程。首先插入一个元素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_stack1m_stack2append 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() <= 0) { while(m_stack1.size() > 0) { 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(); }

热门文章