题目（单调队列的应用）：

用一个长度为k的窗口在长度为n的整数数列上从左往右滑动，每次滑动一个单位，求出每次滑动后每个窗口里面所包含的数的最大值。例如：当数列为[1, 3, -1, -3, 5, 3, 6, 7]，窗口大小k=3，可以得出，

窗口位置	窗口内最大值
[1    3    -1]   -3    5    3    6    7	3
1   [3    -1    -3]   5    3    6    7	3
1    3   [-1    -3    5]   3    6    7	5
1    3    -1   [-3    5    3]   6    7	5
1    3    -1    -3   [5    3    6]   7	6
1    3    -1    -3    5   [3    6    7]	7

 

样例输入：

8 3（分别为n和k）

1    3   -1    -3    5   3    6    7（整数数列）

输出样例：

3    3    5    5    6    7（窗口内最大值）

 

//单调队列的应用
//author:Mitchell_Donovan
//date:2021.3.22
#include<iostream>
using namespace std;

class arrayQueue {
private:
	int size;
	int front;
	int tail;
	int** queue;
public:
	arrayQueue(int sizeValue) {
		size = sizeValue + 1;
		queue = new int*[size];
		for (int i = 0; i < size; i++) {
			queue[i] = new int[2];
			queue[i][0] = queue[i][1] = INT_MAX;
		}
		front = 0;
		tail = 0;
	}
	~arrayQueue() {
		for (int i = 0; i < size; i++) {
			delete[]queue[i];
		}
		delete[]queue;
	}
	bool push(int rank,int numberValue) {
		if (((tail + 1) % size) == front) {
			cout << "The queue has been full!" << endl;
			return false;
		}
		tail = (tail + 1) % size;
		queue[tail-1][0] = rank;
		queue[tail-1][1] = numberValue;
		return true;
	}
	bool poptail() {
		if (front == tail) {
			cout << "The queue is empty!" << endl;
			return false;
		}
		queue[tail-1][0] = queue[tail-1][1] = INT_MAX;
		tail = (size + tail - 1) % size;
		return true;
	}
	bool popfront() {
		if (front == tail) {
			cout << "The queue is empty!" << endl;
			return false;
		}
		queue[front][0]= queue[front][1] = INT_MAX;
		front = (front + 1) % size;
		return true;
	}
	bool getmax(int* array,int arraySize,int testSize) {
		for (int i = 0; i < testSize - 1; i++) {
			if (array[i] >= queue[(size + tail - 1) % size][1]) {
				while (array[i] >= queue[(size + tail - 1) % size][1]) {
					poptail();
				}
			}
			push(i, array[i]);
		}
		for (int i = testSize - 1; i < arraySize; i++) {
			if (i - queue[front][0] >= testSize) {
				popfront();
			}//清空已经过期的元素
			if (array[i] >= queue[(size + tail - 1) % size][1]) {
				while (array[i] >= queue[(size + tail - 1) % size][1]) {
					poptail();
				}
			}
			push(i, array[i]);
			cout << queue[front][1] << " ";
		}
		return true;
	}
};


int main() {
	int arraySize, testSize;
	cout << "Please input the length of array : ";
	cin >> arraySize;
	cout << "Please input the length of testwindow : ";
	cin >> testSize;
	int* array = new int[arraySize];
	cout << "Please input the value of each number : ";
	for (int i = 0; i < arraySize; i++) {
		cin >> array[i];
	}
	arrayQueue test(testSize);
	test.getmax(array, arraySize, testSize);
}