雁過無(wú)痕

《編程之美》讀書筆記18： 3.7 隊(duì)列中取最大數(shù)操作問題

若不使用C++新標(biāo)準(zhǔn)的右值引用，DeQueue的實(shí)現(xiàn)是低效的，因?yàn)橐祷氐脑刂荒芡ㄟ^賦值操作，而不能通過引用。（書上的實(shí)現(xiàn)代碼，竟然少了對(duì)EnQueue的實(shí)現(xiàn)！）

思路：用一個(gè)輔助隊(duì)列來(lái)記錄最大元素（為節(jié)省空間，只記錄其地址），當(dāng)有一個(gè)元素入隊(duì)，就將輔助隊(duì)列尾端不大于該元素的全部出隊(duì)后（注意相等的也要出隊(duì)），再將該元素壓入輔助隊(duì)列，這樣就保證，輔助隊(duì)列從頭到尾的元素是遞減的，輔助隊(duì)列頭元素是當(dāng)前隊(duì)列的最大值。當(dāng)有一個(gè)元素出隊(duì)時(shí)，就與輔助隊(duì)列的頭部第一個(gè)元素所指的元素比較，如果是同一個(gè)元素（注意不是相等），輔助隊(duì)列頭部就執(zhí)行出隊(duì)操作。

如果某個(gè)元素入隊(duì)時(shí)，輔助隊(duì)列有m次出隊(duì)操作，則這所對(duì)應(yīng)的m個(gè)元素在入隊(duì)時(shí)，輔助隊(duì)列沒有執(zhí)行出隊(duì)操作，平均下來(lái)，每個(gè)元素入隊(duì)時(shí)，輔助隊(duì)列入隊(duì)操作1次，出隊(duì)操作1次，時(shí)間復(fù)雜度為O(1)。）

為方便起見，函數(shù)名用push、pop、max，而不是EnQueue、DeQueue、MaxElement。

queue

template<typename T>
class Queue{
 public:
  Queue(){ }
  size_t size() const{ return qa.size();}
  bool empty() const { return qa.empty();}
  const T& max() const {
    assert (!qa.empty());
    assert (!qb.empty());
    return *qb.front();
  }

  void push(const T& value)
  {
    qa.push_back(value); 
    while (!qb.empty() && value >= *qb.back()) qb.pop_back();
    qb.push_back(&qa.back());  
  }

  T pop()
  {
    assert(!qa.empty());
    assert(!qb.empty());
    if (qb.front() == &qa.front()) qb.pop_front();
    T tmp=qa.front();
    qa.pop_front();
    return tmp;
  }

 private:
   Queue (const Queue&);
   Queue& operator=(const Queue&);
   deque<T> qa;
   deque<T*> qb;
};

上面是隊(duì)列的實(shí)現(xiàn)，如果換成棧，則要更簡(jiǎn)單：元素入棧時(shí)，如果比輔助棧的頂部元素大，就在輔助棧添加該元素，元素出棧時(shí)，如果與輔助棧的頂部元素所指的元素是同一個(gè)元素（不是相等），輔助棧就執(zhí)行出棧操作。

輔助棧可以記錄最大元素的地址或在棧中的相對(duì)位置，后者相比前者，

優(yōu)點(diǎn)：可以將所用容器改為vector，并且可以直接用一個(gè)對(duì)象對(duì)另一個(gè)對(duì)象賦值；

缺點(diǎn)：下標(biāo)方式訪問元素相對(duì)較慢，特別是在deque容器。

stack_1

//輔助棧記錄最大元素的地址
template<typename T>
class Stack_p{
 public:
  Stack_p() { }
  size_t size() const{ return qa.size();}
  bool empty() const { return qa.empty();}
  const T& max() const {
    assert (!qa.empty());
    assert (!qb.empty());
    return *qb.back();
  }

  void push(const T& value)
  {
    qa.push_back(value);
    if (qb.empty() || value> *qb.back()) qb.push_back(&qa.back());
  }

  T pop()
  {
    assert(!qa.empty());
    assert(!qb.empty());
    if ( qb.back() == &qa.back()) qb.pop_back();
    T tmp=qa.back();
    qa.pop_back();
    return tmp;
  }

 private:
   Stack_p (const Stack_p&);
   Stack_p& operator=(const Stack_p&);
   deque<T> qa;
   deque<T*> qb;
};

stack_2
//輔助棧記錄最大元素在棧內(nèi)的相對(duì)位置
template<typename T>
class Stack{
 public:
  size_t size() const{ return qa.size();};
  bool empty() const { return qa.empty();};
  const T& max() const 
  { 
    assert (!qa.empty());
    assert (!qb.empty());
    return qa[qb.back()];
  }

  void push(const T& value)
  {
    qa.push_back(value);
    if (qb.empty() || value> qa[qb.back()]) qb.push_back(qa.size()-1);
  }

  T pop()
  {
    assert(!qa.empty());
    assert(!qb.empty());
    if ( qa.size() == qb.back()+1) qb.pop_back();
    T tmp=qa.back();    
    qa.pop_back();
    return tmp;
  }

 private:
   deque<T> qa;
   deque<size_t> qb;
};