algorithm - sheet - stack data structure
Implemente una cola en la que push_rear(), pop_front() y get_min() son todas operaciones de tiempo constante (12)
Me encontré con esta pregunta: Implementar una cola en la que push_rear (), pop_front () y get_min () son todas operaciones de tiempo constante.
Inicialmente pensé en usar una estructura de datos min-heap que tiene una complejidad O (1) para un get_min (). Pero push_rear () y pop_front () sería O (log (n)).
¿Alguien sabe cuál sería la mejor manera de implementar tal cola que tiene O (1) push (), pop () y min ()?
Busqué en Google sobre esto, y quería señalar este hilo Algorithm Geeks . Pero parece que ninguna de las soluciones sigue una regla de tiempo constante para los 3 métodos: push (), pop () y min ().
Gracias por todas las sugerencias.
De acuerdo, creo que tengo una respuesta que te da todas estas operaciones en O (1) amortiguado, lo que significa que cualquier operación podría tomar hasta O (n), pero cualquier secuencia de n operaciones toma O (1) tiempo por operación .
La idea es almacenar sus datos como un árbol cartesiano . Este es un árbol binario que obedece a la propiedad min-heap (cada nodo no es más grande que sus hijos) y está ordenado de tal manera que un recorrido de los nodos en el orden le devuelve los nodos en el mismo orden en que fueron agregados. Por ejemplo, aquí hay un árbol cartesiano para la secuencia 2 1 4 3 5 :
1
/ /
2 3
/ /
4 5
Es posible insertar un elemento en un árbol cartesiano en O (1) tiempo amortizado usando el siguiente procedimiento. Mire la columna derecha del árbol (el camino desde la raíz hasta la hoja más a la derecha formada siempre caminando hacia la derecha). Comenzando por el nodo de la derecha, escanee hacia arriba a lo largo de esta ruta hasta que encuentre el primer nodo más pequeño que el nodo que está insertando.
Cambie ese nodo para que su hijo derecho sea este nuevo nodo, luego convierta el hijo anterior derecho del nodo en el hijo izquierdo del nodo que acaba de agregar. Por ejemplo, supongamos que queremos insertar otra copia de 2 en el árbol de arriba. Caminamos por la columna derecha pasando el 5 y el 3, pero paramos debajo del 1 porque 1 <2. Luego cambiamos el árbol para que se vea así:
1
/ /
2 2
/
3
/ /
4 5
Observe que un recorrido de inorder da 2 1 4 3 5 2, que es la secuencia en la que agregamos los valores.
Esto se ejecuta en O (1) amortizado porque podemos crear una función potencial igual a la cantidad de nodos en el lomo derecho del árbol. El tiempo real requerido para insertar un nodo es 1 más el número de nodos en el lomo que consideramos (llámalo k). Una vez que encontramos el lugar para insertar el nodo, el tamaño del lomo se reduce por la longitud k - 1, ya que cada uno de los k nodos que visitamos ya no se encuentran en el lomo derecho, y el nuevo nodo está en su lugar. Esto da un costo amortizado de 1 + k + (1 - k) = 2 = O (1), para el inserto O (1) amortizado. Como otra forma de pensar sobre esto, una vez que un nodo se ha movido fuera de la columna derecha, nunca vuelve a formar parte de la columna derecha, por lo que nunca más tendremos que volver a moverlo. Dado que cada uno de los n nodos se puede mover a lo sumo una vez, esto significa que n inserciones pueden hacer como máximo n movimientos, por lo que el tiempo de ejecución total es como máximo O (n) para un O amortizado (1) por elemento.
Para hacer un paso de dequeue, simplemente eliminamos el nodo más a la izquierda del árbol cartesiano. Si este nodo es una hoja, hemos terminado. De lo contrario, el nodo solo puede tener un hijo (el hijo correcto), por lo que reemplazamos el nodo con su hijo derecho. Siempre que realicemos un seguimiento de dónde está el nodo situado más a la izquierda, este paso toma O (1) vez. Sin embargo, después de eliminar el nodo más a la izquierda y reemplazarlo con su hijo derecho, es posible que no sepamos dónde está el nuevo nodo situado más a la izquierda. Para solucionar esto, simplemente caminamos por la columna izquierda del árbol comenzando en el nuevo nodo que acabamos de mover al niño más a la izquierda. Yo afirmo que esto todavía se ejecuta en O (1) tiempo amortizado. Para ver esto, afirmo que un nodo se visita como máximo una vez durante cualquiera de estos pasos para encontrar el nodo más a la izquierda. Para ver esto, tenga en cuenta que una vez que un nodo ha sido visitado de esta manera, la única forma en que podríamos necesitar mirarlo de nuevo sería si se moviera desde un elemento secundario del nodo más a la izquierda al nodo más a la izquierda. Pero todos los nodos visitados son los padres del nodo más a la izquierda, por lo que esto no puede suceder. En consecuencia, cada nodo se visita como máximo una vez durante este proceso, y el pop se ejecuta en O (1).
Podemos hacer find-min en O (1) porque el árbol cartesiano nos da acceso al elemento más pequeño del árbol de forma gratuita; es la raíz del árbol.
Finalmente, para ver que los nodos vuelven en el mismo orden en el que se insertaron, tenga en cuenta que un árbol cartesiano siempre almacena sus elementos para que un recorrido inorden los visite en orden ordenado. Como siempre eliminamos el nodo situado más a la izquierda en cada paso, y este es el primer elemento del recorrido intermedio, siempre recuperamos los nodos en el orden en que se insertaron.
En resumen, obtenemos O (1) pulsado y pop amortiguado, y O (1) el peor caso de find-min.
Si puedo llegar a una implementación O (1) del peor de los casos, definitivamente lo publicaré. Este fue un gran problema; gracias por publicarlo!
De hecho, puede usar una LinkedList para mantener la cola.
Cada elemento en LinkedList será de Tipo
class LinkedListElement
{
LinkedListElement next;
int currentMin;
}
Puede tener dos punteros, uno para el inicio y el otro para el final.
Si agrega un elemento al inicio de la cola. Examine el puntero de Inicio y el nodo para insertar. Si el nodo para insertar currentmin es menor que start currentmin node para insertar currentmin es el mínimo. De lo contrario, actualice el currentmin con start currentmin.
Repita lo mismo para enque.
Esta solución contiene 2 colas:
1. main_q - almacena los números de entrada.
2. min_q - almacena los números mínimos por ciertas reglas que describiremos (aparecen en las funciones MainQ.enqueue (x), MainQ.dequeue (), MainQ.get_min ()).
Aquí está el código en Python. Cola se implementa utilizando una lista.
La idea principal se encuentra en las funciones MainQ.enqueue (x), MainQ.dequeue (), MainQ.get_min ().
Una suposición clave es que vaciar una cola toma o (0).
Se proporciona una prueba al final.
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))
El resultado de la prueba anterior es:
"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
Implementación de 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);
}
}
}
Las soluciones a esta pregunta, incluido el código, se pueden encontrar aquí: http://discuss.joelonsoftware.com/default.asp?interview.11.742223.32
Ok, aquí hay una solución.
Primero necesitamos algunas cosas que proporcionan push_back (), push_front (), pop_back () y pop_front () en 0 (1). Es fácil de implementar con array y 2 iteradores. El primer iterador señalará al frente, el segundo a la parte posterior. Vamos a llamar tales cosas deque.
Aquí está el pseudo-código:
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();
}
}
Explicación:
Ejemplo, empujemos números [12,5,10,7,11,19] y a nuestro MyQueue
1) empujando 12
D [12]
Min[12]
2) empujando 5
D[12,5]
Min[5] //5>12 so 12 removed
3) presionando 10
D[12,5,10]
Min[5,10]
4) empujando 7
D[12,5,10,7]
Min[5,7]
6) empujando 11
D[12,5,10,7,11]
Min[5,7,11]
7) empujando 19
D[12,5,10,7,11,19]
Min[5,7,11,19]
Ahora llamemos pop_front ()
tenemos
D[5,10,7,11,19]
Min[5,7,11,19]
El mínimo es 5
Llamemos a pop_front () nuevamente
Explicación: pop_front eliminará 5 de D, pero también resaltará el elemento frontal de Min, porque equivale al elemento frontal de D''s (5).
D[10,7,11,19]
Min[7,11,19]
Y el mínimo es 7. :)
Sabemos que push y pop son operaciones de tiempo constante [O (1) para ser precisos].
Pero cuando pensamos en get_min () [es decir, para encontrar el número mínimo actual en la cola] en general, lo primero que nos viene a la mente es buscar toda la cola cada vez que se realiza la solicitud del elemento mínimo. Pero esto nunca dará la operación de tiempo constante, que es el objetivo principal del problema.
Esto generalmente se pregunta con frecuencia en las entrevistas, por lo que debe conocer el truco
Para hacer esto tenemos que usar dos colas más que mantendrán la pista del elemento mínimo y tenemos que seguir modificando estas 2 colas a medida que hacemos operaciones de empuje y pop en la cola para que el elemento mínimo se obtenga en el tiempo O (1) .
Aquí está el código de sudo autodescriptivo basado en el enfoque mencionado anteriormente.
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;
}
Si no te importa almacenar un poco de datos adicionales, sería trivial almacenar el valor mínimo. Push y pop pueden actualizar el valor si el elemento nuevo o eliminado es el mínimo, y devolver el valor mínimo es tan simple como obtener el valor de la variable.
Esto supone que get_min () no cambia los datos; si prefieres algo como pop_min () (es decir, eliminar el elemento mínimo), puedes simplemente almacenar un puntero al elemento real y al elemento que lo precede (si lo hay) y actualizarlos según push_rear () y pop_front () también.
Editar después de los comentarios:
Obviamente, esto conduce a O (n) push y pop en el caso de que los cambios mínimos en esas operaciones, y por lo tanto no cumple estrictamente los requisitos.
Use un deque (A) para almacenar los elementos y otro deque (B) para almacenar los mínimos.
Cuando x está en cola, retroceda a A y mantenga pop_backing B hasta que la parte posterior de B sea más pequeña que x, luego push_back x a B.
al eliminar A, pop_front A como valor de retorno, y si es igual al frente de B, pop_front B también.
cuando obtenga el mínimo de A, use el frente de B como valor de retorno.
dequeue y getmin son obviamente O (1). Para la operación en cola, considere la push_back de n elementos. Hay n push_back a A, n push_back a B y a lo sumo n pop_back de B porque cada elemento permanecerá en B o saldrá una vez de B. En total, hay O (3n) operaciones y, por lo tanto, el costo amortizado es O (1) también para enqueue.
Por último, la razón por la que funciona este algoritmo es que cuando encaste x en A, si hay elementos en B que son mayores que x, nunca serán mínimos ahora porque x permanecerá en la cola A más tiempo que cualquier elemento en B (una cola es FIFO). Por lo tanto, necesitamos extraer los elementos en B (desde la parte posterior) que son más grandes que x antes de insertar x en 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])
Implementación de JavaScript
(Crédito a la solución de adamax para la idea: basé una implementación en él. Pase al final para ver el código completamente comentado o lea los pasos generales a continuación. Tenga en cuenta que esto encuentra el valor máximo en O (1) tiempo constante en lugar de el valor mínimo - fácil de cambiar):
Inserción: O (1) peor casoLa idea general es crear dos Stacks en la construcción de
MaxQueue(utilicé una lista vinculada como la estructura de datosStacksubyacente, no incluida en el código, pero cualquierStackmientras se implemente con O (1) inserción / supresión). Uno de ellos saldrá principalmente de (dqStack) y el otro lopushprincipalmente (eqStack).
Para en
enqueue, si elMaxQueueestá vacío,pushel valor adqStackjunto con el valor máximo actual en una tupla (el mismo valor ya que es el único valor en elMaxQueue); p.ej:
const m = new MaxQueue();
m.enqueue(6);
/*
the dqStack now looks like:
[6, 6] - [value, max]
*/
Si el
MaxQueueno está vacío, solopushel valor paraeqStack;
m.enqueue(7);
m.enqueue(8);
/*
dqStack: eqStack: 8
[6, 6] 7 - just the value
*/
luego, actualice el valor máximo en la tupla.
/*
dqStack: eqStack: 8
[6, 8] 7
*/
Eliminación: O (1) amortizado
Para
dequeueharemospopdesdedqStacky devolveremos el valor de la tupla.
m.dequeue();
> 6
// equivalent to:
/*
const tuple = m.dqStack.pop() // [6, 8]
tuple[0];
> 6
*/
Entonces, si
dqStackestá vacío, mueva todos los valores eneqStackadqStack, por ejemplo:
// 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
*/
A medida que se mueve cada valor, comprobaremos si es mayor que el máximo hasta el momento y lo almacenaremos en cada tupla:
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
*/
Encontrar el valor máximo: O (1) peor casoDebido a que cada valor se mueve a
dqStacka lo sumo una vez , podemos decir quedequeuetiene O (1) complejidad de tiempo amortizado.
Luego, en cualquier punto del tiempo, podemos llamar a
getMaxpara recuperar el valor máximo actual en O (1) tiempo constante. Siempre que elMaxQueueno esté vacío, el valor máximo se saca fácilmente de la siguiente tupla endqStack.
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
*/
Código
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];
}
}
Puede implementar una pila con O (1) pop (), push () y get_min (): simplemente almacene el mínimo actual junto con cada elemento. Entonces, por ejemplo, la pila [4,2,5,1] (1 en la parte superior) se convierte en [(4,4), (2,2), (5,2), (1,1)] .
Luego puede usar dos pilas para implementar la cola . Empuja a una pila, pop de otra; si la segunda pila está vacía durante el pop, mueva todos los elementos de la primera pila a la segunda.
Por ejemplo, para una solicitud pop , moviendo todos los elementos de la primera pila [(4,4), (2,2), (5,2), (1,1)] , la segunda pila sería [(1,1), (5,1), (2,1), (4,1)] . y ahora devuelve el elemento superior de la segunda pila.
Para encontrar el elemento mínimo de la cola, observe los dos elementos más pequeños de los min-stacks individuales, luego tome el mínimo de esos dos valores. (Por supuesto, hay una lógica extra aquí es el caso de que una de las pilas esté vacía, pero eso no es demasiado difícil de solucionar).
Tendrá O (1) get_min() y push() y amortizará O (1) pop() .
#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;
}