雁過無痕

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

若不使用C++新標準的右值引用，DeQueue的實現是低效的，因為要返回的元素只能通過賦值操作，而不能通過引用。（書上的實現代碼，竟然少了對EnQueue的實現！）

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

如果某個元素入隊時，輔助隊列有m次出隊操作，則這所對應的m個元素在入隊時，輔助隊列沒有執行出隊操作，平均下來，每個元素入隊時，輔助隊列入隊操作1次，出隊操作1次，時間復雜度為O(1)。）

為方便起見，函數名用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;
};

上面是隊列的實現，如果換成棧，則要更簡單：元素入棧時，如果比輔助棧的頂部元素大，就在輔助棧添加該元素，元素出棧時，如果與輔助棧的頂部元素所指的元素是同一個元素（不是相等），輔助棧就執行出棧操作。

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

優點：可以將所用容器改為vector，并且可以直接用一個對象對另一個對象賦值；

缺點：下標方式訪問元素相對較慢，特別是在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
//輔助棧記錄最大元素在棧內的相對位置
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;
};