记一次腾讯面试，我挂在了最熟悉不过的队列上

面试官问：你了解队列和链表的区别吗？

我：了解，blabla

面试官又问：你能自己实现队列吗？具体讲讲怎么实现？

我当时说了用链表来实现队列的存储，并实现push和pop的操作，但回答的不具体，面试官有些摇头。今天结合一道力扣题来实现队列

题目

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。若队列为空，pop_front 和 max_value 需要返回 -1。

示例 1：

输入:

["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]

[[],[1],[2],[],[],[]]

输出: [null,null,null,2,1,2]

解题思路：双链表实现

max_value()

如果MAXQueueHead == MAXQueueTail 表示队列中没有元素，返回-1。在MAXQueue的头指针的位置保存的就是此时队列中的最大值，直接的取值就可以，时间复杂度是O(1)

push_back():

Queue数组正常的进行添加数据，Queue[QueueTail++] = value;

在进行入队的时候，在MAXQueue中需要进行判断，时间复杂度均摊下来也是O(1)：比value小的值，一定会在value出栈前，先出栈，队列中的最大值最少都是value，就没有保存比value小的值的必要了，MAXQueueTail指向的索引，在数组MAXQueue中还没被赋值，判断的时候需要使用MAXQueueTail-1

MAXQueue[MAXQueueTail-1] < value

pop_front()

Queue中Head的值 与 MAXQueue中Head的值相等，则两个数组中的head都要 ++ ，因为最大值已经变了。不然，就是常规的Queue中的head++，时间复杂度是O(1)

解题代码(java)

class MaxQueue {

List<Integer> list;

int listHead = 0;

int listTail = 0;

List<Integer> MAXlist;

int MAXlistHead = 0;

int MAXlistTail = 0;

public MaxQueue() {

list = new ArrayList<>();

MAXlist = new ArrayList<>();

}

public int max_value() {

if(MAXlistHead == MAXlistTail){

// 头尾相等的时候，表示此时队列为空，没有最大值

return -1;

}

return MAXlist.get(MAXlistHead);

}

public void push_back(int value) {

list.add(listTail++, value);

while(MAXlistHead != MAXlistTail && MAXlist.get(MAXlistTail-1) < value){

// MAXlistTail-1 因为MAXlistTail处的值是0，还没有被初始化

// 比value小的值，一定会在value出栈前，先出栈，

// 队列中的最大值最少都是value，就没有保存比value小的值的必要了

MAXlistTail--;

}

MAXlist.add(MAXlistTail++,value);

}

public int pop_front() {

if(listHead == listTail){

// 队列为空

return -1;

}

int res = list.get(listHead);

if(res == MAXlist.get(MAXlistHead)){

MAXlistHead++;

}

listHead++;

return res;

}

}

如果有收获？希望老铁们来个三连，点赞、收藏、转发

创作不易，别忘点个赞，可以让更多的人看到这篇文章，顺便鼓励我写出更好的博客