Tema especial ｜Explicación detallada de pila y cola

Las pilas y las colas son dos estructuras de datos comunes, que se utilizan para resolver diferentes tipos de problemas. En programación, las pilas y colas son estructuras de datos muy importantes porque pueden ayudarnos a resolver muchos problemas prácticos.

Pila:

Primero, analicemos la pila. La pila es una estructura de datos de último en entrar, primero en salir (LIFO). Hay dos operaciones básicas de la pila: empujar y hacer estallar.

Empujar significa poner elementos en la parte superior de la pila, y hacer estallar significa sacar elementos de la parte superior de la pila. La esencia de una pila es un contenedor que puede almacenar cualquier tipo de datos, pero el tamaño de la pila es fijo porque sus elementos solo se pueden agregar o eliminar en la parte superior de la pila.

La pila tiene muchos escenarios de aplicación. Por ejemplo, cuando navegamos por la web, podemos utilizar la función "retorno" del navegador. Esta es una de las aplicaciones de la pila.

Cuando navegamos por la web, cada vez que hacemos clic en un enlace, se agregará una nueva página a la pila, y cuando hagamos clic en el botón "Volver", la página en la parte superior de la pila emergente, para que podamos volver. Llegó a la página anterior. Además, la pila también se puede utilizar para resolver problemas como la coincidencia de corchetes y la evaluación de expresiones.

Cola:

A continuación, introduzcamos la cola. Una cola es una estructura de datos de primero en entrar, primero en salir (FIFO), que es similar a una pila y también es una estructura de datos lineal y ordenada. Hay tres operaciones básicas de la cola, a saber, ingresar a la cola, sacarla de la cola y ver el primer elemento de la cola.

Poner en cola significa poner el elemento al final de la cola y sacar de la cola significa sacar el primer elemento de la cola. La esencia de una cola es también un contenedor, que puede almacenar cualquier tipo de datos, pero el tamaño de la cola también es fijo.

La cola también tiene muchos escenarios de aplicación, como la programación de procesos en el sistema operativo. Hay muchos procesos que deben ejecutarse en el sistema operativo y el sistema operativo gestiona estos procesos a través de colas.

Cuando es necesario ejecutar un proceso, se agrega al final de la cola. Cuando el sistema operativo asigna una CPU, el proceso al principio de la cola se saca y se ejecuta. cada proceso Todos tienen la oportunidad de ejecutarlo.

Además de los escenarios de aplicación anteriores, las pilas y colas tienen muchas otras aplicaciones. Por ejemplo, las pilas también se pueden usar para implementar algoritmos recursivos, las colas se usan para búsquedas en amplitud, etc. ¡Aprendamos más sobre pilas y colas a través de algunas preguntas clásicas!

Problema clásico (1)

Descripción del problema: verificar la secuencia de la pila

Dadas dos secuencias, empujadas y extraídas, los valores de cada secuencia no se repiten , devuelve verdadero solo si pueden ser el resultado de una secuencia de operaciones push y pop en una pila inicialmente vacía; de lo contrario, devuelve falso;

Ejemplo 1:

Entrada: push = , popped =

Salida: true

Explicación: Podemos ejecutar en el siguiente orden : empujar(1) , empujar(2) , empujar(3) , empujar(4) , pop() -> 4 , empujar(5) , pop() -> 5 , pop() -> 3, pop() - > 2 , pop() -> 1 .

Ejemplo 2:

Entrada:

empujado =, reventado =

Salida:

falso p>

Explicación:

1 no puede aparecer antes que 2.

Consejo:

1 <= push.length <= 1000 0 <= push[i] <= 1000 Todos los elementos de push son diferentes entre sí popped.length == push .length popped es una permutación de push.

Análisis:

Siempre que se simule el proceso de empujar y sacar un número, al insertar un número en la pila, verifique si el número es el siguiente número que se extraerá. la pila. Si es así, simplemente saque el número y continúe verificando los números en la pila.

Si se pueden escanear todos los números que se van a extraer, es una secuencia de pila legal.

Implementación de código Java: (use ArrayList para simular la pila)

solución de clase {

validación booleana públicaStackSequences(int[] empujada, int[] emergente) {

Lista S=new ArrayList<>();

int j=0;

for(int i=0;i

S.add(empujado[i]);

mientras(S.size()>0&&j

S.remove(S.size()-1);

j++;

}

}

return j==popped.length;

}

}

Implementación del código C++: (directamente pila STL usada)

clase Solución {

pública:

bool validarStackSequences(vector& push, vector& popped) {

pilaS;

int n=pusded.size();

int j=0;

for(int i = 0;i

S.push(empujado[i]);

mientras(S.size()>0&&j

S.pop();

j++;

}

}

return j==n;

}

};

Problema clásico (2)

Descripción del problema: apilar pagodas

El juego de construcción de pagodas permite a los niños construir pagodas en orden de mayor a menor según el diámetro de los círculos del arco iris que atrapan. Pero los círculos del arco iris no necesariamente se capturan en orden de diámetro. La estrategia adoptada por el bebé inteligente es la siguiente:

Primero prepare dos pilares, un pilar A para encordar la pagoda y un pilar B para apilar temporalmente. Utilice el primer trozo del círculo del arco iris como base de la primera pagoda y colóquelo en el pilar A. Compara la siguiente pieza del círculo del arco iris C que atrapaste con el círculo del arco iris en la parte superior de la pagoda del pilar A actual. Si es más pequeño que el superior, simplemente colócalo directamente;

De lo contrario, coloca C con. el superior en el pilar B Compare los círculos del arco iris: si el pilar B está vacío o C es grande, colóquelo en el pilar B; de lo contrario, retire la pagoda colgada en el pilar A y úsela como producto terminado; >

Luego coloque B Retire todos los círculos del arco iris más grandes que C en el pilar uno por uno y colóquelos en el pilar A, y finalmente coloque C también en el pilar A. Repita este paso hasta que se hayan capturado todos los círculos del arco iris. Finalmente, la pagoda restante del pilar A se utilizó como producto terminado, y los círculos del arco iris restantes del pilar B se quitaron uno por uno y se apilaron en otra pagoda.

Pregunta: ¿Cuántas pagodas puede construir el bebé de una sola vez? ¿Cuántos pisos tiene la pagoda más alta?

Repite este paso hasta que se hayan capturado todos los círculos del arcoíris. Finalmente, la pagoda restante del pilar A se utilizó como producto terminado, y los círculos del arco iris restantes del pilar B se quitaron uno por uno y se apilaron en otra pagoda.

Pregunta: ¿Cuántas pagodas puede construir el bebé de una sola vez? ¿Cuántos pisos tiene la pagoda más alta?

Formato de entrada:

La primera línea de entrada proporciona un número entero positivo N, que es el número de círculos del arco iris. La segunda línea da N números enteros positivos que no exceden 100 en el orden en que el bebé los agarra, correspondiente al diámetro de cada círculo del arco iris.

Formato de salida:

Muestre el número de pagodas acumuladas por el bebé y el número de pisos de la pagoda más alta en una línea. Los números deben estar separados por 1 espacio y no debe haber espacios adicionales al principio ni al final de la línea.

Muestra de entrada:

11

10 8 9 5 12 11 4 3 1 9 15

Muestra de salida:

p>

4 5

Explicación de muestra:

El orden de las pagodas apiladas por el bebé es:

10, 8, 5

12, 11, 4, 3, 1

9

15, 9

Análisis:

Según el significado de la pregunta, simplemente utilice dos pilas para las operaciones de simulación.

#include

usando el espacio de nombres std;

pilaa,b;

int n,x,maxx,sum;

int main(){

cin>>n;

for(int i=1;i<=n ;i++){

cin>>x;

if(a.empty()){

a.push(x);

continuar;

}

if(x

a.push(x);

}

else{

if(b.empty()||x>b.top()){

b.push(x) ;

}

else{

suma++;

if(a.size()>maxx)

maxx=a.size();

mientras(a.size()>0){

a.pop();

}

mientras(b.size()>0&&b.top()>x){

int h=b.top();

b.pop() ;

a.push(h);

}

a.push(x);

}

}

}if(!a.empty()){

suma++;

if(a.size()>maxx)

maxx=a.size();

}

if(!b.empty()){

suma++;

if(a.size()>maxx)

maxx=b.size();

}

cout<

}

Problema clásico (3)

Descripción del problema: simulación simple de cola de negocios bancaria

Supongamos que banco Hay dos ventanas comerciales, A y B, y la velocidad de procesamiento del negocio es diferente. La velocidad de procesamiento de la ventana A es el doble que la de la ventana B, es decir, cuando la ventana A termina de procesar 2 clientes, la ventana B termina de procesar 1 cliente. .

Dada la secuencia de clientes que llegan al banco, genere la secuencia de clientes en el orden en que se completa el negocio. Se supone que no se considera el intervalo de tiempo entre los clientes que llegan uno tras otro, y cuando dos clientes se procesan en diferentes ventanas al mismo tiempo, el cliente de la ventana A sale primero.

Formato de entrada:

La entrada es una línea de números enteros positivos, donde el primer número N (≤1000) es el número total de clientes, seguido del número de N clientes. Los clientes con números impares deben ir a la ventana A para gestionar el negocio, y los clientes con números pares deben ir a la ventana B. Los números están separados por espacios.

Formato de salida:

Muestre los números de cliente en el orden en que se completa el procesamiento comercial. Los números están separados por espacios, pero no debe haber espacios adicionales después del último número. .

Muestra de entrada:

8 2 1 3 9 4 11 13 15

Muestra de salida:

1 3 2 9 11 4 13 15

Análisis:

Según el significado de la pregunta, se utilizan dos colas para simular el negocio de procesamiento de ventanilla del banco. El orden de salida siempre es A primero y luego B, es decir, Primero se procesa una ventana, hasta 2 clientes, la ventana B puede procesar como máximo 1 cliente.

#include

#include

#include

usando el espacio de nombres std;

int primero=1;

void print(int x){

si(primero){

primero=0;

printf("%d",x);

}

else

printf(" %d",x);

}

int main(){

cola p1,p2;

int n,x,w;

scanf("%d",&n);

mientras(n--){

scanf("%d",&x);

if(x%2)

p1.push(x);

else

p2.push(x);

}

mientras(1){

if(p1.empty()||p2.empty())

romper;

if(!p1.empty()){

w=p1.front();

p1.pop();

print(w);

}

if(!p1.empty()){

w=p1.front();

p1.pop ();

imprimir(w);

}

if(!p2.empty()){

w=p2 .front();

p2.pop();

imprimir(w);

}

}

mientras(!p1.empty()){

w=p1.front();

p1.pop();

imprimir( w);

}

mientras(!p2.empty()){

w=p2.front();

p2.pop();

print(w);

}

}

También hay una cola especial llamada Doble- Las colas finalizadas se pueden colocar al principio o al final de la cola durante las operaciones de puesta en cola o retirada de la cola. A menudo se combinan con BFS para resolver algunos problemas de algoritmos comunes.

Problema clásico (4)

Descripción del problema: Tractor

Después de trabajar todo el día, el granjero John se olvidó por completo de que había dejado el tractor en medio del campo. . Su vaca era muy traviesa y decidió gastarle una broma a John.

Colocaron N fardos de heno en diferentes partes del campo para que John tuviera que retirar algunos de los fardos antes de poder alejarse con el tractor. Las posiciones del tractor y las posiciones de las N balas de heno son puntos de coordenadas enteros en un plano bidimensional.

No hay fardos de heno en la posición inicial del tractor. Cuando John conduce el tractor, solo puede moverlo en direcciones paralelas a los ejes de coordenadas (norte, sur, este y oeste), y el tractor debe moverse una distancia entera cada vez.

Ejemplo: Conducir un tractor primero se mueve 2 unidades hacia el norte y luego 3 unidades hacia el este.

El tractor no puede desplazarse a la posición que ocupa la bala de heno. Ayude a John a determinar la cantidad mínima de fardos de heno que necesita quitar para poder conducir el tractor hasta el origen del plano bidimensional.

Formato de entrada:

La primera línea contiene tres números enteros: N y la posición inicial del tractor (x, y). Siguen las siguientes N líneas, cada una de las cuales contiene las coordenadas de posición ( x , y ) de un fardo de heno.

Formato de salida:

Muestre el número mínimo de fardos de heno que John necesita eliminar.

Rango de datos:

1 ≤ N ≤ 50000

1 ≤ x, y ≤ 1000

Muestra de entrada:

7 6 3

6 2

5 2

4 3

2 1

7 3

5 4

6 4

Muestra de salida:

1

También hay una comparación. La cola especial se denomina cola de doble extremo. La posición durante la operación de entrada o salida de la cola puede ser la cabecera o la cola de la cola. A menudo se combina con BFS para resolver algunos problemas de algoritmos comunes.

#include

usando el espacio de nombres std;

bool vis[1010][1010];

int G[1010][1010];

int x,y,sx,sy,n;

int dir[4][2]={{1,0}, {0,1},{-1,0},{0,-1}};

int res,tx,ty;

int dist[1010][1010] ;

estructura nodo{

int x;

int y;

int dis;

};

dequeQ;

nodo t;

int main(){

scanf("%d%d% d",&n,&sx,&sy);

res=n;

mientras(n--){

scanf("%d%d" ,&x,&y);

G[x][y]=1;

}

nodo S;

S.x= sx,S.y=sy,S.dis=0;

Q.push_back(S);

vis[sx][sy]=1;

while(!Q.empty()){

nodo h=Q.front();

Q.pop_front();

if(h.x= =0&&h.y==0){

printf("%d",h.dis);

devuelve 0;

}

for(int i=0;i<4;i++){

tx=h.x+dir[i][0];

ty=h.y +dir [i][1];

if(tx<0||tx>=1005||ty<0||ty>=1005||vis[tx][ty])

continuar;

vis[tx][ty]=1;

t.x=tx,t.y=ty;

if(G[ tx] [ty]){

t.dis=h.dis+1;

Q.push_back(t);

}

else{

t.dis=h.dis;

Q.push_front(t);

}

}

}

}

Si el número de pilas/colas satisface una cierta monotonicidad, se denomina pila monótona/cola monótona. La monotonicidad también puede ser necesaria cuando se trata de ciertos problemas algorítmicos, como el problema de máximo/mínimo de ventana deslizante que se encuentra a menudo en las entrevistas. Cuando se utiliza una pila monótona/cola monótona, es necesario garantizar la monotonicidad de todos los números en ella en todo momento. Una vez que no se cumple la monotonicidad, se debe realizar una operación pop.

Ejemplo de pila monótona: pila monótona

Dada una secuencia entera de longitud N, genere el primer número a la izquierda de cada número que sea menor que él. sacarlo? 1.

Formato de entrada:

La primera línea contiene el número entero N, que indica la longitud de la secuencia. La segunda línea contiene N números enteros, que representan la secuencia de números enteros.

Formato de salida:

*** Una línea, que contiene N enteros, donde el i-ésimo número representa el primer número más pequeño a la izquierda del i-ésimo número. Si existe, genere ?1.

Rango de datos:

1 ≤ N ≤ 10^5

1 ≤ elementos en la secuencia ≤ 10^9

Muestra de entrada Ejemplo:

5

3 4 2 7 5

Muestra de salida:

-1 3 -1 2 2

Código de solución:

#include

usando el espacio de nombres std;

int a[100010],res[ 100010] ,n;

pilaS;

pilaid;

int main(){

scanf( "%d",&n);

for(int i=1;i<=n;i++){

scanf("%d",&a[i] );

}

memset(res,-1,sizeof(res));

for(int i=n;i>=1;i -- ){

mientras(!S.empty()&&a[i]

res[id.top()]=a[i ];

S.pop();

id.pop();

}

S.push(a[i ]) ;

id.push(i);

}

for(int i=1;i<=n;i++){

printf("%d ",res[i]);

}

}

Pregunta clásica (5)

Descripción del problema: ventana deslizante

Dada una matriz de tamaño n ≤ 10^6. Hay una ventana deslizante de tamaño k que se mueve desde el extremo izquierdo al extremo derecho de la matriz. Solo puedes ver k números en la ventana. Cada vez la ventana deslizante se mueve una posición hacia la derecha.

El siguiente es un ejemplo: la matriz es [1 3 -1 -3 5 3 6 7] y k es 3. Su tarea es determinar los valores máximo y mínimo en la ventana deslizante en cada ubicación.

Formato de entrada:

La entrada contiene dos líneas. La primera línea contiene dos números enteros n y k, que representan la longitud de la matriz y la longitud de la ventana deslizante respectivamente. La segunda línea contiene n números enteros, que representan los valores específicos de la matriz. Los datos de la misma fila están separados por espacios.

Formato de salida:

La salida contiene dos. La primera línea genera, de izquierda a derecha, el valor mínimo en la ventana deslizante en cada posición. La segunda línea genera, de izquierda a derecha, el valor máximo en la ventana deslizante en cada posición.

Muestra de entrada:

8 3

1 3 -1 -3 5 3 6 7

Muestra de salida:

p>

-1 -3 -3 -3 3 3

3 3 5 5 6 7

Código de solución:

#include

usando el espacio de nombres std;

int n,k,a[500010];

dequeq;

int main(){

scanf("%d%d",&n,&k);

for(int i=1;i<=n; i++)

scanf("%d",&a[i]);

for(int i=1;i<=n;i++){

if (!q.empty()&&i-q.front()>=k)

q.pop_front();

mientras(!q.empty()&&a[ i] <=a[q.back()])

q.pop_back();

q.push_back(i);

if(i >= k)

printf("%d ",a[q.front()]);

}

printf("\n") ;

mientras(!q.empty())

q.pop_back();

for(int i=1;i<=n;i++ ){

if(!q.empty()&&i-q.front()>=k)

q.pop_front();

mientras( !q .empty()&&a[i]>=a[q.back()])

q.pop_back();

q.push_back(i);

if(i>=k)

printf("%d ",a[q.front()]);

}

}

Las pilas monótonas/colas monótonas también se utilizan más ampliamente. Por ejemplo, algunos problemas de programación dinámica requieren el uso de colas monótonas para la optimización. Dichos problemas se presentarán en el tema de programación dinámica.

Resumen:

Si eres un estudiante universitario nuevo en el mundo de las computadoras o un programador que se prepara para una entrevista de trabajo, debes dominar los conceptos y aplicaciones de pilas y colas, y sus La mayoría de las estructuras de datos básicas. Una vez que comprenda el uso de estas estructuras de datos, podrá aplicarlas en varios problemas de programación.

En resumen, las pilas y las colas son estructuras de datos muy importantes y pueden ayudarnos a resolver muchos problemas prácticos. En programación, si puede utilizar pilas y colas con habilidad, será de gran ayuda para mejorar la eficiencia y legibilidad del programa. ¿Tiene este tema sobre pilas y colas?