數(shù)據(jù)結(jié)構(gòu)（九）——隊(duì)列-創(chuàng)新互聯(lián)-四川平武建站

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案

數(shù)據(jù)結(jié)構(gòu)（九）——隊(duì)列-創(chuàng)新互聯(lián)

數(shù)據(jù)結(jié)構(gòu)（九）——隊(duì)列

一、隊(duì)列簡(jiǎn)介

隊(duì)列是一種特殊的線性表，僅能在兩端進(jìn)行操作，隊(duì)頭可以進(jìn)行區(qū)數(shù)據(jù)操作，隊(duì)尾進(jìn)行插入數(shù)據(jù)操作。
隊(duì)列的特性是先進(jìn)先出。
數(shù)據(jù)結(jié)構(gòu)（九）——隊(duì)列
隊(duì)列的操作包括創(chuàng)建隊(duì)列、銷毀隊(duì)列、入隊(duì)、出隊(duì)、清空隊(duì)列、獲取隊(duì)頭元素、獲取隊(duì)列的長(zhǎng)度。

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來(lái)自于我們對(duì)這個(gè)行業(yè)的熱愛。我們立志把好的技術(shù)通過(guò)有效、簡(jiǎn)單的方式提供給客戶，將通過(guò)不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長(zhǎng)期合作伙伴，公司提供的服務(wù)項(xiàng)目有：域名申請(qǐng)、雅安服務(wù)器托管、營(yíng)銷軟件、網(wǎng)站建設(shè)、敖漢網(wǎng)站維護(hù)、網(wǎng)站推廣。

二、隊(duì)列的實(shí)現(xiàn)

1、隊(duì)列的抽象類

 template 
  class Queue:public Object
  {
  public:
    virtual void add(const T& value) = 0;//進(jìn)隊(duì)列
    virtual void remove() = 0;//出隊(duì)列
    virtual T front()const = 0;//獲取隊(duì)頭元素
    virtual void clear() = 0;//清空隊(duì)列
    virtual int length()const = 0;//隊(duì)列長(zhǎng)度
  };

2、隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)

隊(duì)列可以使用順序存儲(chǔ)結(jié)構(gòu)的內(nèi)存空間實(shí)現(xiàn)，其內(nèi)存空間分布如下：
數(shù)據(jù)結(jié)構(gòu)（九）——隊(duì)列
根據(jù)存儲(chǔ)空間的分配方式可以分為使用原生數(shù)組實(shí)現(xiàn)的靜態(tài)隊(duì)列和使用動(dòng)態(tài)分配的堆空間實(shí)現(xiàn)的動(dòng)態(tài)隊(duì)列。
靜態(tài)隊(duì)列的實(shí)現(xiàn)要點(diǎn)如下：
A、類模板實(shí)現(xiàn)
B、使用原生數(shù)組作為隊(duì)列的存儲(chǔ)空間
C、使用模板參數(shù)決定隊(duì)列的容量大小
靜態(tài)隊(duì)列的實(shí)現(xiàn)如下：

template 
  class StaticQueue:public Queue
  {
  protected:
    T m_space[N];//隊(duì)列存儲(chǔ)空間，N為模板參數(shù)
    int m_front;//隊(duì)頭標(biāo)識(shí)
    int m_rear;//隊(duì)尾標(biāo)識(shí)
    int m_length;//隊(duì)列長(zhǎng)度
  public:
    StaticQueue()
    {
      m_front = 0;
      m_rear = 0;
      m_length = 0;
    }

    int capacity()const
    {
      return N;
    }

    void add(const T &value)//入隊(duì)
    {
      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()//出隊(duì)
    {
      if(m_length > 0)
      {
          m_front = (m_front + 1) % N;
          m_length--;
      }
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "No element...");
      }
    }

    T front() const//取隊(duì)頭元素
    {
      if(m_length > 0)
      {
          return m_space[m_front];
      }
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "No element...");
      }
    }
   void clear()//清空隊(duì)列
   {
     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);
   }
  };

靜態(tài)隊(duì)列的缺陷：
當(dāng)存儲(chǔ)的元素類型為類類型時(shí)，創(chuàng)建靜態(tài)隊(duì)列時(shí)會(huì)多次調(diào)用元素類型的類構(gòu)造函數(shù)，影響效率。

3、隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)

隊(duì)列使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)的內(nèi)容空間分布如下：
數(shù)據(jù)結(jié)構(gòu)（九）——隊(duì)列
鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)要點(diǎn)：
A、類模板實(shí)現(xiàn)，繼承自抽象父類Queue
B、內(nèi)部使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)元素的存儲(chǔ)
C、只在鏈表的頭部和尾部進(jìn)行操作
鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)：

 template 
  class LinkedQueue:public Queue
  {
  protected:
    LinkedList m_list;
  public:
    LinkedQueue()
    {
    }
    void add(const T& value)//入隊(duì)
    {
      m_list.insert(value);
    }

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

    void clear()//清空隊(duì)列
    {
      m_list.clear();
    }

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

三、棧和隊(duì)列的相互實(shí)現(xiàn)

1、棧實(shí)現(xiàn)隊(duì)列

用棧實(shí)現(xiàn)隊(duì)列，用棧的后進(jìn)先出的特性實(shí)現(xiàn)隊(duì)列的先進(jìn)先出的特性。
用棧實(shí)現(xiàn)隊(duì)列需要使用兩個(gè)棧，解決方案如下：
數(shù)據(jù)結(jié)構(gòu)（九）——隊(duì)列
新元素入隊(duì)時(shí)，將元素壓入stack_in棧，

template 
class StackToQueue:public Queue
{
protected:
  mutable LinkedStack m_stack_in;
  mutable LinkedStack m_stack_out;
public:
  void add(const T& value)//入隊(duì)
  {
    m_stack_in.push(value);
  }
  void remove()//出隊(duì)
  {
    //出棧為空，則將入棧的所有元素壓入出棧并彈出入棧的元素
    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、隊(duì)列實(shí)現(xiàn)棧

用隊(duì)列實(shí)現(xiàn)棧，用隊(duì)列的先進(jìn)先出的特性實(shí)現(xiàn)棧的后進(jìn)先出的特性。
用隊(duì)列實(shí)現(xiàn)棧需要使用兩個(gè)隊(duì)列，解決方案如下：
數(shù)據(jù)結(jié)構(gòu)（九）——隊(duì)列

template 
class QueueToStack:public Stack
{
protected:
  LinkedQueue m_queue1;
  LinkedQueue m_queue2;
  LinkedQueue* m_pIn;//入隊(duì)列
  LinkedQueue* m_pOut;//出隊(duì)列
  //將入隊(duì)列前n-1個(gè)元素移動(dòng)到出隊(duì)列
  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();//從入隊(duì)列出隊(duì)
    }
  }
  //交換
  void swap()
  {
    LinkedQueue* 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);//將元素入隊(duì)列
  }
  void pop()//出棧
  {
    if(m_pIn->length() > 0)
    {
        move();//移動(dòng)前n-1個(gè)元素
        m_pIn->remove();//將入隊(duì)列的最后一個(gè)元素出隊(duì)
        swap();//交換
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationException, "No element...");
    }
  }

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

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

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

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

分享文章：數(shù)據(jù)結(jié)構(gòu)（九）——隊(duì)列-創(chuàng)新互聯(lián)
文章來(lái)源：http://www.ef60e0e.cn/article/csihgg.html

99热在线精品一区二区三区_国产伦精品一区二区三区女破破_亚洲一区二区三区无码_精品国产欧美日韩另类一区