队列

基础知识

先进先出。STL中与队列对应的类模板为queue ，常用操作：front()返回第一个元素；back()返回最后一个元素；push()向队尾插入元素；pop()删除第一个元素；empty()检查容器是否为空；size()返回容器的元素数。所有操作都在O(1)时间内完成。 关于队列的实现方式,详见: 栈与队列-顺序队列与链队列类模板的实现（数据结构基础 第3周）

应用：两个栈实现队列

题目：用两个栈实现一个队列。请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入节点和在队列头部删除结点的功能。 分析：相关题目：用两个队列实现一个栈。 代码实现

template<typename T> class CQueue { public: CQueue(void); ~CQueue(void); void appendTail(const T& node); T deleteHead(); private: stack<T> stack1; stack<T> stack2; }; template<typename T> CQueue<T>::CQueue(void) {} template<typename T> CQueue<T>::~CQueue(void) {} template<typename T> void CQueue<T>::appendTail(const T& node) { stack1.push(node); } template<typename T> T CQueue<T>::deleteHead() { if(stack2.empty()) { while(!stack1.empty()) { T data=stack1.top(); stack1.pop(); stack2.push(data); } } if(stack2.empty()) throw "The queue is empty."; T head=stack2.top(); stack2.pop(); return head; }

测试用例

应用：滑动窗口的最大值

题目：给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，它们的最大值分别为{4,4,6,6,6,5}，如表8.3所示。 分析方法1，笨方法，老老实实滑动；方法2，对方法1找冗余，一句话核心思想：维护一个队列，一直保持队列的头元素为滑动至当前位置时滑窗内的最大元素；方法3，我们实现过用 O(1) 时间得到最大值的栈，也实现过用两个栈实现队列，把这两者结合起来就是能够在 O(1) 时间获得最大值的队列。 代码实现

//笨方法，时间复杂度$O(nk)$ int SlidingWindowMaximum_1(const vector<int>& input, int windowSize, vector<int>& result) { int dataSize = input.size(); if (windowSize < 1) return 1; if (dataSize < windowSize) return 1; deque<int> cache(input.begin(), input.begin()+ windowSize-1); for (int i = windowSize - 1; i<dataSize; i++) { cache.push_back(input.at(i)); result.push_back(*max_element(cache.begin(), cache.end())); //此句时间复杂度为O(K) cache.pop_front(); } return 0; } //找冗余，时间复杂度$O(n)$ //核心思想：维护一个队列，一直保持队列的头元素为滑动至位置i时滑窗内的最大元素。 int SlidingWindowMaximum_2(const vector<int>& input, int windowSize, vector<int>& result) { int dataSize = input.size(); if (windowSize < 1) return 1; if (dataSize < windowSize) return 1; deque<int> cache(input.begin(), input.begin() + windowSize - 1); for (int i = windowSize - 1; i<dataSize; i++) { if (cache.size() >= windowSize) { //队列已满 cache.pop_front(); //取出第一个 cache.push_back(input.at(i)); cache.erase(cache.begin(), max_element(cache.begin(), cache.end()) ); //队列中最大元素之前的元素已毫无意义 } else { if (!cache.empty() && input.at(i) > cache.front()) { //如果元素i大于队列中的最大元素（即头元素），则队列中已存的所有元素已毫无意义。此处一定要判断队列是否为空，要不然怎么能取头元素front()呢？ cache.clear(); } cache.push_back(input.at(i)); } result.push_back(cache.front()); //此句时间复杂度为O(K) } return 0; }

测试用例

vector<int> input = { 2, 3, 4, 2, 6, 2, 5, 1 };

应用：从上往下打印二叉树

题目： 从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。 分析： 也就是树的层序遍历了。 代码实现

int SequenceTraversalByQueue(BinaryTreeNode* root) { if(!root) return 1; queue<BinaryTreeNode*> q; q.push(root); BinaryTreeNode* p=NULL; while(!q.emtpy()){ p=q.front(); cout << p->value << " "; if(p->left) q.push(p->left); if(p->right) q.push(p->right); q.pop(); } return 0; }