如果您不介意存储一些额外的数据，那么存储最小值应该很简单。如果新的或删除的元素是最小值，Push 和 pop 可以更新该值，并且返回最小值就像获取变量的值一样简单。

这是在假设 get _ min ()不改变数据的情况下; 如果您希望使用 pop _ min ()(即删除最小元素) ，您可以简单地存储指向实际元素及其前面的元素(如果有的话)的指针，并相应地使用 push _ behind ()和 pop _ front ()更新这些指针。

评论后编辑:

显然，在这些操作的最小更改情况下，这将导致 O (n)推和弹出，因此严格来说不能满足需求。

可以用 O (1) pop ()、 push ()和 get _ min ()实现堆栈: 只需将当前最小值与每个元素一起存储。因此，例如，堆栈 [4,2,5,1](顶部的1)变成了 [(4,4), (2,2), (5,2), (1,1)]。

然后你可以 使用两个堆栈来实现队列。推到一个堆栈，从另一个堆栈弹出; 如果弹出过程中第二个堆栈为空，则将所有元素从第一个堆栈移动到第二个堆栈。

例如，对于 pop请求，从第一个堆栈 [(4,4), (2,2), (5,2), (1,1)]移动所有元素，第二个堆栈将是 [(1,1), (5,1), (2,1), (4,1)]。现在从第二个堆栈返回 top 元素。

要找到队列的最小元素，请查看单个 min 堆栈中最小的两个元素，然后取这两个值中的最小值。(当然，这里还有一些额外的逻辑，如果其中一个栈是空的，但这并不太难处理)。

它将有 O (1) get_min()和 push()和摊销的 O (1) pop()。

好的-我想我有一个答案，在 分期付款 O (1)中给出了所有这些操作，这意味着任何一个操作都可以用到 O (n) ，但任何 n 个操作的序列都需要用到 O (1)次 每次行动。

其思想是将数据存储为 笛卡尔树。这是一个二叉树，遵循 min-stack 属性(每个节点都不大于它的子节点) ，并且按照这样的顺序排列: 对节点的无序遍历将返回节点，其顺序与添加节点的顺序相同。例如，下面是序列 2 1 4 3 5的笛卡尔树:

       1
/   \
2      3
/ \
4   5

可以使用以下过程在 O (1)分期时间内将一个元素插入笛卡尔树。看看这棵树的右边的树脊(从树根到最右边的叶子的路径总是走向右边)。从最右边的节点开始，沿着这条路径向上扫描，直到找到比正在插入的节点小的第一个节点。
更改该节点，使其右子节点为此新节点，然后将该节点以前的右子节点设置为刚才添加的节点的左子节点。例如，假设我们想将2的另一个副本插入到上面的树中。我们沿着右脊柱走过5号和3号，但是停在1号以下，因为1 < 2。然后我们把树变成这样:

       1
/   \
2      2
/
3
/ \
4   5

注意，无序遍历给出214352，这是我们添加值的序列。

这在分摊的 O (1)中运行，因为我们可以创建一个势函数等于树的右边脊柱中的节点数。插入一个节点所需的实际时间是1加上我们考虑的脊柱中的节点数(称为 k)。一旦我们找到插入节点的位置，脊柱的大小就会缩小 k-1的长度，因为我们访问的每个 k 节点都不再在右侧脊柱上，新的节点就在它的位置上。这给出了1 + k + (1-k) = 2 = O (1)的分摊费用，对于分摊的 O (1)插入。从另一个角度来看，一旦一个节点从右脊柱移开，它就再也不是右脊柱的一部分了，所以我们再也不用移动它了。由于每个 n 个节点最多只能移动一次，这意味着 n 个插入最多只能移动 n 个步骤，因此对于每个元素分摊的 O (1) ，总运行时最多为 O (n)。

要执行一个 dequeue 步骤，我们只需从笛卡尔树中删除最左边的节点。如果这个节点是一片叶子，我们就完了。否则，该节点只能有一个子节点(右子节点) ，因此我们将该节点替换为其右子节点。假设我们跟踪最左边节点的位置，那么这个步骤需要 O (1)时间。但是，在删除最左边的节点并将其替换为其右边的子节点之后，我们可能不知道新的最左边的节点在哪里。为了解决这个问题，我们只需沿着树的左脊向下走，从刚刚移动到最左边子节点的新节点开始。我声称这仍然运行在 O (1)的摊销时间。为了查看这一点，我声明在这些传递中的任何一个传递期间最多访问一个节点以查找最左边的节点。要看到这一点，请注意一旦以这种方式访问了一个节点，我们可能需要再次查看它的唯一方法是将它从最左边节点的子节点移动到最左边节点。但是所有访问的节点都是最左边节点的父节点，因此这种情况不会发生。因此，在这个过程中每个节点最多只被访问一次，并且弹出在 O (1)中运行。

我们可以在 O (1)中执行 find-min，因为笛卡尔树使我们可以免费访问树的最小元素; 它是树的根。

最后，要查看节点是否按照插入时的顺序返回，请注意笛卡尔树总是存储其元素，以便顺序遍历按照排序顺序访问它们。因为我们总是在每个步骤中删除最左边的节点，而这是顺序遍历的第一个元素，所以我们总是按照插入节点的顺序返回它们。

简而言之，我们得到了 O (1)摊销推送和弹出，以及 O (1)最坏情况下的 find-min。

如果我能想出一个最糟糕的 O (1)实现，我一定会发布它。这是一个很大的问题，谢谢你发布它！

好吧，这里有一个解决办法。

首先，我们需要在0(1)中提供 push _ back ()、 push _ front ()、 pop _ back ()和 pop _ front ()。使用数组和2个迭代器很容易实现。第一个迭代器指向前面，第二个指向后面。让我们称之为公平。

下面是伪代码:

class MyQueue//Our data structure
{
deque D;//We need 2 deque objects
deque Min;


push(element)//pushing element to MyQueue
{
D.push_back(element);
while(Min.is_not_empty() and Min.back()>element)
Min.pop_back();
Min.push_back(element);
}
pop()//poping MyQueue
{
if(Min.front()==D.front() )
Min.pop_front();
D.pop_front();
}


min()
{
return Min.front();
}
}

说明:

例如，让我们把数字[12,5,10,7,11,19]和我们的 MyQueue

1)推12

D [12]
Min[12]

2)推动5

D[12,5]
Min[5] //5>12 so 12 removed

3)快10岁了

D[12,5,10]
Min[5,10]

4)按7

D[12,5,10,7]
Min[5,7]

6)快11岁了

D[12,5,10,7,11]
Min[5,7,11]

7)快19岁了

D[12,5,10,7,11,19]
Min[5,7,11,19]

现在调用 pop _ front ()

我们有

 D[5,10,7,11,19]
Min[5,7,11,19]

最低限度是5

让我们再次调用 pop _ front ()

说明: pop _ front 将从 D 中移除5，但是它也会弹出 Min 的 front 元素，因为它等于 D 的 front 元素(5)。

 D[10,7,11,19]
Min[7,11,19]

最小值是7:)

我们知道推和弹出是常量时间运算[ O (1)是精确的]。

但是，当我们考虑 get _ min ()[即查找队列中当前的最小数目]时，通常首先想到的是每次发出对最小元素的请求时搜索整个队列。但这永远不会给出恒定的时间运算，这是问题的主要目的。

这个问题在面试中经常被问到，所以你一定知道诀窍

为了做到这一点，我们必须使用另外两个队列来保持最小元素的跟踪，我们必须继续修改这两个队列，因为我们在队列上做推和弹出操作，以便在 O (1)时间内获得最小元素。

下面是基于上述方法的自描述伪代码。

    Queue q, minq1, minq2;
isMinq1Current=true;
void push(int a)
{
q.push(a);
if(isMinq1Current)
{
if(minq1.empty) minq1.push(a);
else
{
while(!minq1.empty && minq1.top < =a) minq2.push(minq1.pop());
minq2.push(a);
while(!minq1.empty) minq1.pop();
isMinq1Current=false;
}
}
else
{
//mirror if(isMinq1Current) branch.
}
}
     

int pop()
{
int a = q.pop();
if(isMinq1Current)
{
if(a==minq1.top) minq1.pop();
}
else
{
//mirror if(isMinq1Current) branch.
}
return a;
}

实际上可以使用 LinkedList 来维护队列。

LinkedList 中的每个元素都将是 Type

class LinkedListElement
{
LinkedListElement next;
int currentMin;
}

你可以有两个指针，一个指向开始，另一个指向结束。

如果向 Queue 的开始添加一个元素。检查 Start 指针和要插入的节点。如果节点要插入 currentmin 小于启动 currentmin 节点要插入 currentmin 的最小值。否则使用 start currentmin 更新 currentmin。

对 enque 重复同样的操作。

使用一个 deque (A)存储元素，另一个 deque (B)存储最小值。

当 x 排队时，将其推回到 A，并保持弹出支持 B，直到 B 的后面小于 x，然后将 x 推回到 B。

当排队时，pop _ front A 作为返回值，如果它等于 B 的前面，pop _ front B 也作为返回值。

当得到 A 的最小值时，使用 B 的前面作为返回值。

Dequeue 和 getmin 显然是 O (1)。对于队列操作，考虑 n 个元素的 push _ back。有 n 个推回到 A，n 个推回到 B，最多有 n 个弹回到 B，因为每个元素要么停留在 B 中，要么从 B 中弹出一次。总的来说，有 O (3n)操作，因此对于排队来说，摊销成本也是 O (1)。

最后，这个算法能够工作的原因是，当你把 x 放入 A 队列时，如果 B 中有大于 x 的元素，那么它们现在永远不会是最小值，因为 x 在队列 A 中停留的时间比 B 中的任何元素都长(队列是 FIFO)。因此，在将 x 放入 B 之前，我们需要在 B 中弹出大于 x 的元素(从后面)。

from collections import deque




class MinQueue(deque):
def __init__(self):
deque.__init__(self)
self.minq = deque()


def push_rear(self, x):
self.append(x)
while len(self.minq) > 0 and self.minq[-1] > x:
self.minq.pop()
self.minq.append(x)


def pop_front(self):
x = self.popleft()
if self.minq[0] == x:
self.minq.popleft()
return(x)


def get_min(self):
return(self.minq[0])

#include <iostream>
#include <queue>
#include <deque>
using namespace std;


queue<int> main_queue;
deque<int> min_queue;


void clearQueue(deque<int> &q)
{
while(q.empty() == false) q.pop_front();
}


void PushRear(int elem)
{
main_queue.push(elem);


if(min_queue.empty() == false && elem < min_queue.front())
{
clearQueue(min_queue);
}


while(min_queue.empty() == false && elem < min_queue.back())
{
min_queue.pop_back();
}


min_queue.push_back(elem);
}


void PopFront()
{
int elem = main_queue.front();
main_queue.pop();


if (elem == min_queue.front())
{
min_queue.pop_front();
}
}


int GetMin()
{
return min_queue.front();
}


int main()
{
PushRear(1);
PushRear(-1);
PushRear(2);


cout<<GetMin()<<endl;
PopFront();
PopFront();
cout<<GetMin()<<endl;


return 0;
}

此解决方案包含两个队列:
Main _ q-存储输入数字。
Min _ q-根据我们将要描述的特定规则(出现在函数 MainQ.enqueue (x)、 MainQ.dequeue ()、 MainQ.get _ min ()中)存储 min 数。

下面是 Python.Queue 中使用 List 实现的代码。
主要思想在于 MainQ.enqueue (x)、 MainQ.dequeue ()、 MainQ.get _ min ()函数。
一个关键的假设是清空队列需要 o (0)。
最后提供了一个测试。 < br/>

import numbers


class EmptyQueueException(Exception):
pass


class BaseQ():
def __init__(self):
self.l = list()


def enqueue(self, x):
assert isinstance(x, numbers.Number)
self.l.append(x)


def dequeue(self):
return self.l.pop(0)


def peek_first(self):
return self.l[0]


def peek_last(self):
return self.l[len(self.l)-1]


def empty(self):
return self.l==None or len(self.l)==0


def clear(self):
self.l=[]


class MainQ(BaseQ):
def __init__(self, min_q):
super().__init__()
self.min_q = min_q


def enqueue(self, x):
super().enqueue(x)
if self.min_q.empty():
self.min_q.enqueue(x)
elif x > self.min_q.peek_last():
self.min_q.enqueue(x)
else: # x <= self.min_q.peek_last():
self.min_q.clear()
self.min_q.enqueue(x)


def dequeue(self):
if self.empty():
raise EmptyQueueException("Queue is empty")
x = super().dequeue()
if x == self.min_q.peek_first():
self.min_q.dequeue()
return x


def get_min(self):
if self.empty():
raise EmptyQueueException("Queue is empty, NO minimum")
return self.min_q.peek_first()


INPUT_NUMS = (("+", 5), ("+", 10), ("+", 3), ("+", 6), ("+", 1), ("+", 2), ("+", 4), ("+", -4), ("+", 100), ("+", -40),
("-",None), ("-",None), ("-",None), ("+",-400), ("+",90), ("-",None),
("-",None), ("-",None), ("-",None), ("-",None), ("-",None), ("-",None), ("-",None), ("-",None))


if __name__ == '__main__':
min_q = BaseQ()
main_q = MainQ(min_q)


try:
for operator, i in INPUT_NUMS:
if operator=="+":
main_q.enqueue(i)
print("Added {} ; Min is: {}".format(i,main_q.get_min()))
print("main_q = {}".format(main_q.l))
print("min_q = {}".format(main_q.min_q.l))
print("==========")
else:
x = main_q.dequeue()
print("Removed {} ; Min is: {}".format(x,main_q.get_min()))
print("main_q = {}".format(main_q.l))
print("min_q = {}".format(main_q.min_q.l))
print("==========")
except Exception as e:
print("exception: {}".format(e))

上述测试的结果如下:

"C:\Program Files\Python35\python.exe" C:/dev/python/py3_pocs/proj1/priority_queue.py
Added 5 ; Min is: 5
main_q = [5]
min_q = [5]
==========
Added 10 ; Min is: 5
main_q = [5, 10]
min_q = [5, 10]
==========
Added 3 ; Min is: 3
main_q = [5, 10, 3]
min_q = [3]
==========
Added 6 ; Min is: 3
main_q = [5, 10, 3, 6]
min_q = [3, 6]
==========
Added 1 ; Min is: 1
main_q = [5, 10, 3, 6, 1]
min_q = [1]
==========
Added 2 ; Min is: 1
main_q = [5, 10, 3, 6, 1, 2]
min_q = [1, 2]
==========
Added 4 ; Min is: 1
main_q = [5, 10, 3, 6, 1, 2, 4]
min_q = [1, 2, 4]
==========
Added -4 ; Min is: -4
main_q = [5, 10, 3, 6, 1, 2, 4, -4]
min_q = [-4]
==========
Added 100 ; Min is: -4
main_q = [5, 10, 3, 6, 1, 2, 4, -4, 100]
min_q = [-4, 100]
==========
Added -40 ; Min is: -40
main_q = [5, 10, 3, 6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Removed 5 ; Min is: -40
main_q = [10, 3, 6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Removed 10 ; Min is: -40
main_q = [3, 6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Removed 3 ; Min is: -40
main_q = [6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Added -400 ; Min is: -400
main_q = [6, 1, 2, 4, -4, 100, -40, -400]
min_q = [-400]
==========
Added 90 ; Min is: -400
main_q = [6, 1, 2, 4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 6 ; Min is: -400
main_q = [1, 2, 4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 1 ; Min is: -400
main_q = [2, 4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 2 ; Min is: -400
main_q = [4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 4 ; Min is: -400
main_q = [-4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed -4 ; Min is: -400
main_q = [100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 100 ; Min is: -400
main_q = [-40, -400, 90]
min_q = [-400, 90]
==========
Removed -40 ; Min is: -400
main_q = [-400, 90]
min_q = [-400, 90]
==========
Removed -400 ; Min is: 90
main_q = [90]
min_q = [90]
==========
exception: Queue is empty, NO minimum


Process finished with exit code 0

Java 实现

import java.io.*;
import java.util.*;


public class queueMin {
static class stack {


private Node<Integer> head;


public void push(int data) {
Node<Integer> newNode = new Node<Integer>(data);
if(null == head) {
head = newNode;
} else {
Node<Integer> prev = head;
head = newNode;
head.setNext(prev);
}
}


public int pop() {
int data = -1;
if(null == head){
System.out.println("Error Nothing to pop");
} else {
data = head.getData();
head = head.getNext();
}


return data;
}


public int peek(){
if(null == head){
System.out.println("Error Nothing to pop");
return -1;
} else {
return head.getData();
}
}


public boolean isEmpty(){
return null == head;
}
}


static class stackMin extends stack {
private stack s2;


public stackMin(){
s2 = new stack();
}


public void push(int data){
if(data <= getMin()){
s2.push(data);
}


super.push(data);
}


public int pop(){
int value = super.pop();
if(value == getMin()) {
s2.pop();
}
return value;
}


public int getMin(){
if(s2.isEmpty()) {
return Integer.MAX_VALUE;
}
return s2.peek();
}
}


static class Queue {


private stackMin s1, s2;


public Queue(){
s1 = new stackMin();
s2 = new stackMin();
}


public  void enQueue(int data) {
s1.push(data);
}


public  int deQueue() {
if(s2.isEmpty()) {
while(!s1.isEmpty()) {
s2.push(s1.pop());
}
}


return s2.pop();
}


public int getMin(){
return Math.min(s1.isEmpty() ? Integer.MAX_VALUE : s1.getMin(), s2.isEmpty() ? Integer.MAX_VALUE : s2.getMin());
}


}






static class Node<T> {
private T data;
private T min;
private Node<T> next;


public Node(T data){
this.data = data;
this.next = null;
}




public void setNext(Node<T> next){
this.next = next;
}


public T getData(){
return this.data;
}


public Node<T> getNext(){
return this.next;
}


public void setMin(T min){
this.min = min;
}


public T getMin(){
return this.min;
}
}


public static void main(String args[]){
try {
FastScanner in = newInput();
PrintWriter out = newOutput();
// System.out.println(out);
Queue q = new Queue();
int t = in.nextInt();
while(t-- > 0) {
String[] inp = in.nextLine().split(" ");
switch (inp[0]) {
case "+":
q.enQueue(Integer.parseInt(inp[1]));
break;
case "-":
q.deQueue();
break;
case "?":
out.println(q.getMin());
default:
break;
}
}
out.flush();
out.close();


} catch(IOException e){
e.printStackTrace();
}
}


static class FastScanner {
static BufferedReader br;
static StringTokenizer st;


FastScanner(File f) {
try {
br = new BufferedReader(new FileReader(f));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
public FastScanner(InputStream f) {
br = new BufferedReader(new InputStreamReader(f));
}
String next() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}


String nextLine(){
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}


int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDoulbe() {
return Double.parseDouble(next());
}
}


static FastScanner newInput() throws IOException {
if (System.getProperty("JUDGE") != null) {
return new FastScanner(new File("input.txt"));
} else {
return new FastScanner(System.in);
}
}
static PrintWriter newOutput() throws IOException {
if (System.getProperty("JUDGE") != null) {
return new PrintWriter("output.txt");
} else {
return new PrintWriter(System.out);
}
}
}

JavaScript 实现

(这个想法要感谢 Adamax 的解决方案; 我 松散的就是基于它来实现的。跳到底部查看完整的注释代码或通读下面的一般步骤。注意，这里发现 最大值是 O (1)常量时间，而不是 最小值——很容易改变) :

一般的想法是在构造 MaxQueue时创建两个栈(我使用链表作为底层 Stack数据结构——代码中没有包含; 但是任何 Stack都可以，只要它是用 O (1)插入/删除实现的)。一个我们将主要从 pop(dqStack)和一个我们将主要从 push到(eqStack)。

对于 enqueue，如果 MaxQueue是空的，我们将 push的值与 Tuple中的当前最大值(相同的值，因为它是 MaxQueue中唯一的值)一起给 dqStack; 例如:

const m = new MaxQueue();


m.enqueue(6);


/*
the dqStack now looks like:
[6, 6] - [value, max]
*/

如果 MaxQueue不是空的，我们 push只是从 价值到 eqStack;

m.enqueue(7);
m.enqueue(8);


/*
dqStack:         eqStack: 8
[6, 6]           7 - just the value
*/

然后，更新元组中的最大值。

/*
dqStack:         eqStack: 8
[6, 8]           7
*/

对于 dequeue，我们将从 dqStack返回 pop并从元组返回值。

m.dequeue();
> 6


// equivalent to:
/*
const tuple = m.dqStack.pop() // [6, 8]
tuple[0];
> 6
*/

然后，如果 dqStack为空，则将 eqStack中的所有值移动到 dqStack，例如:

// if we build a MaxQueue
const maxQ = new MaxQueue(3, 5, 2, 4, 1);


/*
the stacks will look like:


dqStack:         eqStack: 1
4
2
[3, 5]           5
*/

当每个值被移动时，我们将检查它是否大于最大值 目前为止并将其存储在每个元组中:

maxQ.dequeue(); // pops from dqStack (now empty), so move all from eqStack to dqStack
> 3


// as dequeue moves one value over, it checks if it's greater than the ***previous max*** and stores the max at tuple[1], i.e., [data, max]:
/*
dqStack: [5, 5] => 5 > 4 - update                          eqStack:
[2, 4] => 2 < 4 - no update
[4, 4] => 4 > 1 - update
[1, 1] => 1st value moved over so max is itself            empty
*/

因为每个值都被移动到 dqStack 最多一次，所以我们可以说 dequeue具有 O (1)分摊时间复杂度。

然后，在任何时间点，我们可以调用 getMax来检索 O (1)常数时间内的当前最大值。只要 MaxQueue不是空的，最大值就很容易从 dqStack中的下一个元组中提取出来。

maxQ.getMax();
> 5


// equivalent to calling peek on the dqStack and pulling out the maximum value:
/*
const peekedTuple = maxQ.dqStack.peek(); // [5, 5]
peekedTuple[1];
> 5
*/

密码

class MaxQueue {
constructor(...data) {
// create a dequeue Stack from which we'll pop
this.dqStack = new Stack();
// create an enqueue Stack to which we'll push
this.eqStack = new Stack();
// if enqueueing data at construction, iterate through data and enqueue each
if (data.length) for (const datum of data) this.enqueue(datum);
}
enqueue(data) { // O(1) constant insertion time
// if the MaxQueue is empty,
if (!this.peek()) {
// push data to the dequeue Stack and indicate it's the max;
this.dqStack.push([data, data]); // e.g., enqueue(8) ==> [data: 8, max: 8]
} else {
// otherwise, the MaxQueue is not empty; push data to enqueue Stack
this.eqStack.push(data);
// save a reference to the tuple that's next in line to be dequeued
const next = this.dqStack.peek();
// if the enqueueing data is > the max in that tuple, update it
if (data > next[1]) next[1] = data;
}
}
moveAllFromEqToDq() { // O(1) amortized as each value will move at most once
// start max at -Infinity for comparison with the first value
let max = -Infinity;
// until enqueue Stack is empty,
while (this.eqStack.peek()) {
// pop from enqueue Stack and save its data
const data = this.eqStack.pop();
// if data is > max, set max to data
if (data > max) max = data;
// push to dequeue Stack and indicate the current max; e.g., [data: 7: max: 8]
this.dqStack.push([data, max]);
}
}
dequeue() { // O(1) amortized deletion due to calling moveAllFromEqToDq from time-to-time
// if the MaxQueue is empty, return undefined
if (!this.peek()) return;
// pop from the dequeue Stack and save it's data
const [data] = this.dqStack.pop();
// if there's no data left in dequeue Stack, move all data from enqueue Stack
if (!this.dqStack.peek()) this.moveAllFromEqToDq();
// return the data
return data;
}
peek() { // O(1) constant peek time
// if the MaxQueue is empty, return undefined
if (!this.dqStack.peek()) return;
// peek at dequeue Stack and return its data
return this.dqStack.peek()[0];
}
getMax() { // O(1) constant time to find maximum value
// if the MaxQueue is empty, return undefined
if (!this.peek()) return;
// peek at dequeue Stack and return the current max
return this.dqStack.peek()[1];
}
}