题目描述

c++ 的写法

C++ 代码

# include <assert.h>
# include <iostream>
using namespace std;

template <class T>
class Queue{
    public:
    Queue(){};                                 // 构造函数
    ~Queue(){};                                 // 析构函数
    virtual bool push(const T& x) = 0;       // 新元素进队列
    virtual bool pop() = 0;             // 队头元素出队列
    virtual bool getFront(T& x)const = 0;            // 读取队头元素的值
    virtual bool empty()const = 0;            // 判断队列空否
    virtual bool full()const = 0;             // 判断队列满否
    virtual int  size()const = 0;             // 求队列元素个数
};



template <class T>
class SeqQueue:public Queue<T> {             // 循环队列的类定义
public:
    SeqQueue(int sz = 1000);                   // 构造函数
    ~SeqQueue(){delete[] elements;}          // 析构函数
    bool push(const T& x);
    // 若队列不满，则将x进队，否则队溢出处理。
    bool pop();
    // 若队列不空，则退出队头元素x并由函数返回true，否则队空，返回false
    bool getFront(T& x)const;
    // 若队列不为空，则函数返回true及队头元素的值，否则返回false。
    void makeEmpty(){front = rear = 0;}
    // 置空操作：队头指针和队尾指针置0
    bool empty()const {return(front == rear)?true:false;}
    // 判断列空否。若队列空，则函数返回true，否则返回false
    bool full()const{return ((rear + 1)% maxSize == front)?true:false;}
    // 判断队列满否。若队列满，则函数返回true,否则返回false
    int size()const{return (rear-front+maxSize)% maxSize;}
    // 求队列元素个数


        // 输出队列中元素的重载操作<<
protected:
    int rear,front;                           // 队尾与队头指针
    T * elements;                             // 存放队列元素的数组
    int maxSize;                              // 队列最大可容纳元素个数
};

template <class T>
SeqQueue<T>::SeqQueue(int sz):rear(0),front(0),maxSize(sz) {
    // 建立一个最大具有maxSize个元素的空队列。
    elements = new T[maxSize];              // 创建队列空间
    assert(elements != NULL);               // 断言：动态存储分配成功与否
};

template <class T>
bool SeqQueue<T>::push(const T& x) {
    // 若队列不满，则将元素x插入到该队列的队尾，否则出错处理。
    // if(full() == true)return false;                  // 队列满则插入失败，返回
    elements[rear] = x;                                // 按照队尾指针指示位置插入
    rear = (rear+1)% maxSize;                          // 队尾指针加1
    return true;                                       // 插入成功，返回
};

template <class T>
bool SeqQueue<T>::pop(){
    // 若队列不空则函数退掉一个队头元素并返回true,否则函数返回false
    if(empty() == true) return false;           // 若队列空则函数返回空指针
    front = (front+1) % maxSize;                  // 队头指针加1
    return true;                                  // 删除成功，返回
};

template<class T>
bool SeqQueue<T>::getFront(T& x)const{
    // 若队列不空则函数返回该队列队头元素的值
    if(empty() == true) return false;                // 若队列空则函数返回空指针
    x = elements[front];                               // 返回队头元素的值
    return true;
};



int main(){
  SeqQueue<int> queue;
  int m;
  cin>>m;
  while(m--){
      string op;
      int x;
      cin>>op;
      if(op=="push")
      {
          cin>>x;
          queue.push(x);  
      }
      else if(op=="pop") queue.pop();
      else if(op=="empty") cout<<((queue.empty()) ? "YES" : "NO")<<endl;
      else  if(op == "query")
      {
          int val ;
          queue.getFront(val);
          cout<<val<<endl;
      }
  }
  return 0;
}