实现push_rear（），pop_front（）和get_min（）都是常量操作的队列
我碰到过这个问题： 实现一个push_rear（），pop_front（）和get_min（）都是常量操作的队列。
我最初想到使用get_min（）具有O（1）复杂度的min-heap数据结构。 但push_rear（）和pop_front（）将是O（log（n））。
有没有人知道什么是最好的方式来实现这样一个队列，其中有O（1）push（），pop（）和min（）？
我search了这个，并想指出这个algorithm极客线程 。 但似乎没有任何解决scheme遵循所有3种方法的常量时间规则：push（），pop（）和min（）。
感谢所有的build议。
你可以使用O（1）pop（），push（）和get_min（）来实现一个堆栈：只要将当前最小值与每个元素一起存储即可。 因此，例如，堆栈[4,2,5,1] （顶部1）变成[(4,4), (2,2), (5,2), (1,1)] 。
那么你可以使用两个堆栈来实现队列 。 推到一个堆栈，从另一个堆栈popup; 如果popup过程中第二个堆栈是空的，请将第一个堆栈中的所有元素移至第二个堆栈。
例如，对于pop请求，将第一个堆栈[(4,4), (2,2), (5,2), (1,1)]所有元素移动，第二个堆栈将是[(1,1), (5,1), (2,1), (4,1)] 。 现在从第二个堆栈返回顶部的元素。
要查找队列的最小元素，请查看各个最小堆栈中最小的两个元素，然后取这两个值中的最小值。 （当然，这里还有一些额外的逻辑，如果其中一个堆栈是空的，但这不是很难解决）。
它将有O（1） get_min()和push()并分期O（1） pop() 。
好的 – 我认为我有一个答案，可以给你所有这些操作的分期 O（1），这意味着任何一个操作可以占用O（n），但是任何n个操作序列每个操作需要O（1）次。
这个想法是将你的数据存储为笛卡尔树 。 这是一个遵循min-heap属性的二叉树（每个节点都不比它的子节点大），并且按照这样的方式sorting：节点的inorder遍历以与添加节点相同的顺序返回节点。 例如，这里是序列2 1 4 3 5的笛卡尔树：
1 / \ 2 3 / \ 4 5
可以使用以下过程在O（1）摊销时间中将元素插入到笛卡尔树中。 看看树的正确脊柱（从根到最右边的叶子的path总是走向右边）。 从最右边的节点开始，沿着这条path向上扫描，直到find第一个节点小于所插入的节点。
更改该节点，使其右侧的子节点为新节点，然后使该节点的前一个右侧子节点为刚刚添加的节点的左侧子节点。 例如，假设我们想在上面的树中插入另一个2的副本。 我们走过5号和3号的右脊柱，而是在1号以下停下来，因为1 <2。然后我们把树改成这样：
1 / \ 2 2 / 3 / \ 4 5
请注意，一个inorder遍历给出了2 1 4 3 5 2，这是我们添加值的顺序。
由于我们可以创build一个潜在的函数，这个函数等于树右边的节点的数量，所以这个函数运行在O（1）。 插入节点所需的实际时间是1加上我们考虑的脊椎节点的数量（称为k）。 一旦我们find插入节点的地方，由于我们所访问的k个节点中的每一个不再位于右侧脊柱上，并且新节点位于其中，所以脊柱的大小缩小了长度k-1。 这为摊销O（1）插入提供了1 + k +（1 – k）= 2 = O（1）的摊销成本。 作为另一种思考的方式，一旦一个节点被移出正确的脊柱，它就再也不会是右脊柱的一部分了，所以我们再也不用移动它了。 由于每个n节点最多可以移动一次，这意味着n次插入最多可以执行n次移动，因此总运行时间对于每个元素的分摊O（1）至多为O（n）。
要执行一个出队步骤，我们只需从笛卡尔树中移除最左边的节点。 如果这个节点是叶子，我们就完成了。 否则，节点只能有一个孩子（正确的孩子），所以我们用正确的孩子replace节点。 假设我们跟踪最左边的节点在哪里，这个步骤需要O（1）次。 但是，删除最左侧的节点并将其replace为其右侧的子节点后，我们可能不知道新的最左侧节点在哪里。 为了解决这个问题，我们只需从刚刚移动到最左边的子节点的新节点开始，走到树的左侧脊柱。 我声称这仍然运行在O（1）摊销时间。 为了看到这一点，我声称一个节点最多访问一次在任何一个这些过程中find最左边的节点。 要看到这一点，请注意，一旦以这种方式访问了一个节点，我们再次需要查看的唯一方法就是将其从最左端的节点的子节点移动到最左节点。 但是所有访问的节点都是最左端节点的父节点，所以这是不可能发生的。 因此，在这个过程中最多访问一次每个节点一次，popup在O（1）中运行。
我们可以在O（1）中findmin，因为笛卡尔树允许我们访问树的最小元素， 它是树的根。
最后，为了看到节点以与插入顺序相同的顺序返回，请注意，笛卡尔树总是存储其元素，以便顺序遍历以sorting顺序访问它们。 由于我们总是在每一步移除最左边的节点，而这是中序遍历的第一个元素，所以我们总是按照它们插入的顺序返回节点。
简而言之，我们得到O（1）分期付出的推动和stream行，以及O（1）最坏情况的find-min。
如果我能想出一个最糟糕的O（1）实现，我一定会发布它。 这是一个很大的问题。 感谢张贴它！
好的，这是一个解决scheme。
首先，我们需要一些在0（1）中提供push_back（），push_front（），pop_back（）和pop_front（）的东西。 使用数组和2个迭代器很容易实现。 第一个迭代器将指向前面，第二个后面。 我们把这种东西叫做deque。
这里是伪代码：
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，但是它也会popupMin的前一个元素，因为它等于D的前面元素（5）。
D[10,7,11,19] Min[7,11,19]
最小值是7。
使用一个deque（A）存储元素，另一个deque（B）存储最小值。
当x入队时，push_back到A并保持pop_backing B，直到B的后面小于x，然后push_back x到B.
当出列A时，pop_front A作为返回值，如果它等于B的前面，pop_front B也是如此。
当得到A的最小值时，用B的前面作为返回值。
出列和getmin显然是O（1）。 对于排队操作，考虑n个元素的push_back。 有n push_back到A，n push_back到B，最多n pop_back B，因为每个元素将停留在B中或从B中popup一次。总共有O（3n）个操作，因此摊余成本为O （1）以及入队。
最后，这个algorithm的工作原理是，当你将x排入A时，如果B中的元素大于x，那么它们将永远不会是最小值，因为x将保留在队列A中比B中的任何元素长是FIFO）。 因此，在将x推入B之前，我们需要popup大于x的B（从后面）的元素。
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])
如果你不介意存储一些额外的数据，存储最小值应该是微不足道的。 如果新元素或删除的元素是最小值，则推送和popup可以更新值，返回最小值与获取variables的值一样简单。
这是假设get_min（）不会更改数据; 如果你喜欢pop_min（）（也就是删除最小元素），你可以简单地存储一个指向实际元素的指针和它前面的元素（如果有的话），并用push_rear（）和pop_front（）以及。
评论后编辑：
很显然，在这些操作发生最小变化的情况下，会导致O（n）推送和popup，因此不能严格满足要求。
解决这个问题，包括代码，可以在这里find： http : //discuss.joelonsoftware.com/default.asp?interview.11.742223.32
你实际上可以使用LinkedList来维护队列。
LinkedList中的每个元素都是Type
class LinkedListElement { LinkedListElement next; int currentMin; }
你可以有两个指针，一个指向Start，另一个指向End。
如果您添加一个元素到队列的开始。 检查开始指针和要插入的节点。 如果节点插入currentmin小于启动currentmin节点插入currentmin是最小的。 否则，以currentmin开始更新currentmin。
对enque重复同样的操作。
#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; }
该解决scheme包含2个队列：
1. main_q – 存储input的数字。
2. min_q – 按照我们将要描述的某些规则存储最小数字（出现在函数MainQ.enqueue（x），MainQ.dequeue（），MainQ.get_min（））中。
这里是Python中的代码。 队列使用List实现。
主要思想在于MainQ.enqueue（x），MainQ.dequeue（），MainQ.get_min（）函数。
一个关键的假设是清空一个队列需要o（0）。
最后提供了一个testing。
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))
上述testing的输出是：
"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); } } }
我们知道，推动和stream行是恒定的时间操作[O（1）准确地说]。
但是，当我们想到get_min（）[即查找队列中当前的最小数量]时，通常首先想到的是每当请求最小元素时search整个队列。 但是这永远不会给时间的持续运作，这是问题的主要目的。
这在采访中经常被问到，所以你必须知道这个窍门
要做到这一点，我们必须使用两个队列来保持最小元素的轨迹，并且我们必须继续修改这两个队列，因为我们在队列上进行推送和popup操作，以便在O（1）时间内获得最小元素。
这里是基于上述方法的自描述sudo代码。
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; }
