队列的操作实现——C++类封装

Knuth学徒

队列先进先出，我若用数组来模拟的话，势必造成过度移动而效率低下，如果只用指针的话，势必会造成大量空间浪费。

      这里暂时不考虑资源浪费了，就用数组模拟下，实在不行就用STL库函数吧。
   
      queue.h代码:
      
      template <class T>
      class queue{
               private:
                        int head;
                        int tail;
                        T val[MAX];
               public:
                        queue();
                        ~queue();
                        void push_back(T data);
                        T  front ();
                        void pop();
                        bool empty();
                        int size();
       }

       ////////////////////////////////////////////////////
       //    函数名：queue()
       //    参数：none
       //    前提：none
       //    用法：none
       //    描述：构造函数
       ////////////////////////////////////////////////////
       template <class T>
       queue<T>:: queue(){
               head = 0;
               tail = 0;
               memset(val,0,sizeof(val));
       }
      
       ////////////////////////////////////////////////////
       //    函数名：push_back()
       //    参数：data
       //    前提：none
       //    用法：对象名.push_back(xx);
       //    描述：压入队列的尾部
       ////////////////////////////////////////////////////
       template <class T>
       void queue<T>:: push_back( T data)
       {
                tail ++;
                val[tail] = data;
        }


       ////////////////////////////////////////////////////
       //    函数名：pop()
       //    参数：none
       //    前提：none
       //    用法：对象名.pop();
       //    描述：弹出队首元素
       ////////////////////////////////////////////////////
       template <class T>
       void queue<T>:: pop(){
                 head ++;
       }
         
       ////////////////////////////////////////////////////
       //    函数名：front()
       //    参数：none
       //    前提：none
       //    用法：对象名.front();
       //    描述：读出队首元素
       ////////////////////////////////////////////////////
       template <class T>
       T  queue<T>:: front(){
                  return val[head];
       }

       ////////////////////////////////////////////////////
       //    函数名：size()
       //    参数：none
       //    前提：none
       //    用法：对象名.size();
       //    描述：队列大小
       ////////////////////////////////////////////////////
       template <class T>
       int  queue<T>::size(){
                   return (tail - head);
       }

       ////////////////////////////////////////////////////
       //    函数名：empty()
       //    参数：none
       //    前提：none
       //    用法：对象名.empty();
       //    描述：判断队列是否为空
       ////////////////////////////////////////////////////
       template <class T>
       bool  queue<T>:: empty()
       {
                    return tail - head  == 0 ;
       }


       这样的话，栈和队列的类我全部都写了，以后出现 stack和queue就不再唐突。

       基本的 Depth_First_Search 和 Breadth_First_Search 代码就可以用这两个已经封装好的类.

Knuth学徒

队列的应用虽然没有栈那么具有本质性，但是应用也非常广泛，比如操作系统中的消息队列，进程优先级队列……等