0

我正在尝试用两个堆栈实现一个队列，以便更好地理解这两种数据结构。我有以下内容，主要功能用作测试：

#include <iostream>
#include <stack>
using namespace std;

template <class T>
class _Stack : public stack<T> {
   public:
T pop(){
    T tmp=stack::top();
    stack::pop();
    return tmp;
}
};

 template <class T>

 class QueueS {

 public:
QueueS(){}

bool isEmpty() const{ 

return pool.empty();

}


void enqueue(const T& el){

    while( !output.empty()) {
        input.push(output.pop());
    }

    input.push(el);

}

T dequeue(){

    while(!input.empty()){
         output.push(input.pop());
     }

     return output.pop();

}


T firstElement(){

    if(output.empty()) {

               return NULL;

    }

     return output.top();

}

 private:
_Stack<T> pool;
_Stack<T> input;
_Stack<T> output;

 };

 int main(){

QueueS<int> n_QueueS;

//fill the queue of integers 0-9
for(int i=0; i<10;i++)
    n_QueueS.enqueue(i);    

// add another number to the queue
n_QueueS.enqueue(50);

//retrieve the first element without removing it
cout<<"front of the queue: "<<n_QueueS.firstElement()<<endl;

// removing the first 5 elements from the queue
cout<<"deleting first five elements of the queue: ";
for(int i=0; i<5;i++)
    cout<<n_QueueS.dequeue()<<" ";

 //removing the remainder of the queue and displaying the result
//should see 5 6 7 8 9 50 - see nothing!
cout<<endl<<"deleting remainder of the queue: ";
while(!n_QueueS.isEmpty())
    cout<<n_QueueS.dequeue()<<" ";

if(n_QueueS.isEmpty())
    cout<<endl<<"Queue is now empty";
else 
    cout<<endl<<"Error in emptying the queue";

system("pause");

return 0;
}

到目前为止它工作得很好。但是，当我运行测试时，删除前五个元素可以正常工作，并且它们显示正常。正如预期的那样，它显示“删除队列的前五个元素：”行，后跟 0 1 2 3 4。

但是，删除后半部分不会像前面的测试用例那样显示文本“删除队列的剩余部分”之后的值。我假设问题很小，但我无法通过调试找到它。也许我忽略了一些东西？

任何帮助将不胜感激！

4

1 回答 1

2

首先，你的空支票应该是这样的：

bool isEmpty() const{
   return input.empty() && output.empty();
}

在 enqueue 中，只需推送到输入堆栈：

void enqueue(const T& el){
   input.push(el);    
}

在入队和出队中，如果输出为空，则将输入移动到输出：

T dequeue(){
    if (output.empty())
       while(!input.empty()){
         output.push(input.pop());
       }
    // throw exception of output.empty() ??
    return output.pop();
}

T firstElement(){
   if (output.empty())
     while(!input.empty()){
        output.push(input.pop());
     }
   if(output.empty()) {
      return T(0);   // throw exception?
   }
   return output.top();
}
于 2013-06-09T22:42:49.963 回答