数据结构（九）——队列

数据结构（九）——队列

一、队列简介

队列是一种特殊的线性表，仅能在两端进行操作，队头可以进行区数据操作，队尾进行插入数据操作。
队列的特性是先进先出。

队列的操作包括创建队列、销毁队列、入队、出队、清空队列、获取队头元素、获取队列的长度。

二、队列的实现

1、队列的抽象类

 template <typename T>
  class Queue:public Object
  {
  public:
    virtual void add(const T& value) = 0;//进队列
    virtual void remove() = 0;//出队列
    virtual T front()const = 0;//获取队头元素
    virtual void clear() = 0;//清空队列
    virtual int length()const = 0;//队列长度
  };

2、队列的顺序存储结构实现

队列可以使用顺序存储结构的内存空间实现，其内存空间分布如下：

根据存储空间的分配方式可以分为使用原生数组实现的静态队列和使用动态分配的堆空间实现的动态队列。
静态队列的实现要点如下：
A、类模板实现
B、使用原生数组作为队列的存储空间
C、使用模板参数决定队列的容量大小
静态队列的实现如下：

template <typename T, int N>
  class StaticQueue:public Queue<T>
  {
  protected:
    T m_space[N];//队列存储空间，N为模板参数
    int m_front;//队头标识
    int m_rear;//队尾标识
    int m_length;//队列长度
  public:
    StaticQueue()
    {
      m_front = 0;
      m_rear = 0;
      m_length = 0;
    }

    int capacity()const
    {
      return N;
    }

    void add(const T &value)//入队
    {
      if(m_length < N)
      {
          m_space[m_rear] = value;
          m_rear = (m_rear + 1) % N;
          m_length++;
      }
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "No enough memory...");
      }
    }

    void remove()//出队
    {
      if(m_length > 0)
      {
          m_front = (m_front + 1) % N;
          m_length--;
      }
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "No element...");
      }
    }

    T front() const//取队头元素
    {
      if(m_length > 0)
      {
          return m_space[m_front];
      }
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "No element...");
      }
    }
   void clear()//清空队列
   {
     m_length = 0;
     m_front = 0;
     m_rear = 0;
   }

   int length() const
   {
     return m_length;
   }
   bool isEmpty()const
   {
     return (m_length == 0) && (m_front == m_rear);
   }

   bool isFull()const
   {
     return (m_length == N) && (m_front == m_rear);
   }
  };

静态队列的缺陷：
当存储的元素类型为类类型时，创建静态队列时会多次调用元素类型的类构造函数，影响效率。

3、队列的链式存储结构实现

队列使用链式存储结构实现的内容空间分布如下：

链式队列的实现要点：
A、类模板实现，继承自抽象父类Queue
B、内部使用链式结构实现元素的存储
C、只在链表的头部和尾部进行操作
链式队列的实现：

 template <typename T>
  class LinkedQueue:public Queue<T>
  {
  protected:
    LinkedList<T> m_list;
  public:
    LinkedQueue()
    {
    }
    void add(const T& value)//入队
    {
      m_list.insert(value);
    }

    void remove()//出队
    {
      if(m_list.length() > 0)
         m_list.remove(0);
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "No enough memory...");
      }
    }
    T front()const//获取队头元素
    {
      if(m_list.length() > 0)
         return m_list.get(0);
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "No elemnet...");
      }
    }

    void clear()//清空队列
    {
      m_list.clear();
    }

    int length() const
    {
      return m_list.length();
    }
  };

三、栈和队列的相互实现

1、栈实现队列

用栈实现队列，用栈的后进先出的特性实现队列的先进先出的特性。
用栈实现队列需要使用两个栈，解决方案如下：

新元素入队时，将元素压入stack_in栈，

template <typename T>
class StackToQueue:public Queue<T>
{
protected:
  mutable LinkedStack<T> m_stack_in;
  mutable LinkedStack<T> m_stack_out;
public:
  void add(const T& value)//入队
  {
    m_stack_in.push(value);
  }
  void remove()//出队
  {
    //出栈为空，则将入栈的所有元素压入出栈并弹出入栈的元素
    if(m_stack_out.size() == 0)
    {
        while(m_stack_in.size() > 0)
        {
            m_stack_out.push(m_stack_in.top());
            m_stack_in.pop();//弹出入栈的元素
        }
    }
    //出栈不为空，将出栈栈顶元素弹出
    if(m_stack_out.size() > 0)
    {
        m_stack_out.pop();
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationException, "No element...");
    }
  }
  T front() const
  {
    if(m_stack_out.size() == 0)
    {
        while(m_stack_in.size() > 0)
        {
            m_stack_out.push(m_stack_in.top());
            m_stack_in.pop();
        }
    }
    //弹出出栈栈顶元素
    if(m_stack_out.size() > 0)
    {
        return m_stack_out.top();
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationException, "No element...");
    }
  }

  void clear()
  {
     m_stack_in.clear();
     m_stack_out.clear();
  }

  int length()const
  {
     return m_stack_in.size() + m_stack_out.size();
  }
};

2、队列实现栈

用队列实现栈，用队列的先进先出的特性实现栈的后进先出的特性。
用队列实现栈需要使用两个队列，解决方案如下：

template <typename T>
class QueueToStack:public Stack<T>
{
protected:
  LinkedQueue<T> m_queue1;
  LinkedQueue<T> m_queue2;
  LinkedQueue<T>* m_pIn;//入队列
  LinkedQueue<T>* m_pOut;//出队列
  //将入队列前n-1个元素移动到出队列
  void move()const
  {
    int n = m_pIn->length() - 1;
    for(int i = 0; i < n; i++)
    {
        m_pOut->add(m_pIn->front());
        m_pIn->remove();//从入队列出队
    }
  }
  //交换
  void swap()
  {
    LinkedQueue<T>* temp = NULL;
    temp = m_pIn;
    m_pIn = m_pOut;
    m_pOut = temp;
  }
public:
  QueueToStack()
  {
    m_pIn = &m_queue1;
    m_pOut = &m_queue2;
  }
  //压栈
  void push(const T& value)
  {
    m_pIn->add(value);//将元素入队列
  }
  void pop()//出栈
  {
    if(m_pIn->length() > 0)
    {
        move();//移动前n-1个元素
        m_pIn->remove();//将入队列的最后一个元素出队
        swap();//交换
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationException, "No element...");
    }
  }

  void clear()
  {
    m_queue1.clear();
    m_queue2.clear();
  }

  T top() const
  {
    if(m_pIn->length() > 0)
    {
        move();//移动
        return m_pIn->front();
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationException, "No element...");
    }
  }

  int size()const
  {
    return m_queue1.length() + m_queue2.length();
  }
};