Quiero comenzar diciendo que esta NO es una pregunta de tarea. Estoy leyendo Introducción a los algoritmos, el famoso texto CLRS para ser un mejor programador. Estoy tratando de resolver los problemas y ejercicios dados en el libro por mí mismo.
Estoy tratando de resolver el Ejercicio 10.1-2 del Capítulo 10 Estructuras de datos elementales de la segunda edición de CLRS. Esto es lo que dice:
Explicar cómo implementar dos pilas en una matriz A [1..n] de tal manera que ninguna pila se desborde a menos que el número total de elementos en ambas pilas juntas sea n . Las operaciones PUSH y POP deben ejecutarse en tiempo O (1) .
La solución que se me ocurrió hasta ahora es:
Deje la matriz A [1..n] implemente dos pilas: S1 [1..i] y S2 [i..n] .
Para las operaciones PUSH-S1 y PUSH-S2 , si la pila está 'llena', entonces comience a insertar elementos en la otra pila (por ejemplo, si la pila S1 está llena cuando un nuevo elemento está tratando de ser empujado, luego empuje ese elemento hacia adentro pila S2 y viceversa).
El problema con este enfoque es que no podré POP-S1 o POP-S2 de manera confiable ya que no hay forma de 'recordar' qué elemento pertenece a qué pila. Si los elementos de la pila son pares (clave, valor) , siendo la clave el número de la pila, entonces para hacer estallar un elemento tendría que buscar, en el peor de los casos, i o (ni) veces, que será O (n ) (siéntase libre de corregirme si me equivoco aquí), que no sería O (1) .
He estado golpeando mi cabeza con la pregunta desde hace bastante tiempo. ¿Estoy en el camino correcto? ¿Alguien puede dar mis posibles consejos para resolver este problema?
En general, ¿cómo debo 'pensar' sobre estos problemas? ¿O solo las personas realmente inteligentes pueden resolver este tipo de problemas? ¿Abordar / resolver problemas como estos (es decir, adquirir experiencia) me ayudará a mejorar en esto?
Espero la iluminación.
fuente
Respuestas:
Otra pista además de lo que dijo Yuval: ayuda a colocar las pilas de una manera específica en las matrices y a fijar su dirección de crecimiento en consecuencia. No tienen que crecer en la misma dirección.
fuente
Aquí hay algunos consejos:
fuente
La primera pila comienza en 1 y crece hacia n, mientras que la segunda comienza desde n y baja hacia 1. El desbordamiento de pila ocurre cuando se empuja un elemento cuando los dos punteros de pila son adyacentes.
fuente
Este método utiliza eficientemente el espacio disponible. No causa un desbordamiento si hay espacio disponible en arr []. La idea es comenzar dos pilas desde dos esquinas extremas de arr []. stack1 comienza desde el elemento más a la izquierda, el primer elemento en stack1 se empuja en el índice 0. La stack2 comienza desde la esquina más a la derecha, el primer elemento en stack2 se empuja en el índice (n-1). Ambas pilas crecen (o se reducen) en la dirección opuesta. Para verificar el desbordamiento, todo lo que necesitamos verificar es el espacio entre los elementos superiores de ambas pilas.
fuente
Pensé en otra solución. Si dividimos la matriz a la mitad (o lo más cerca posible si la matriz tiene una longitud impar) y hacemos que el primer elemento entre en la primera pila y el segundo elemento entre en la segunda pila. Mientras aparecíamos podríamos volver sobre estos pasos. Sin embargo, si se implementa de esta manera, ¿violaría algún principio de pila?
fuente
Algunas pistas
Hacer una matriz
Los elementos de matriz con índice impar son para stack1
Los elementos de matriz con índice par son para stack2
Ahora puedes hacer crecer ambas pilas de izquierda a derecha
Simplemente mantenga variables que mantengan la posición superior de ambas pilas. No tendrá que buscar en la matriz.
y si stack1 se llena mientras stack2 está vacío, puede realizar un seguimiento de elementos adicionales de stack1 en stack2 manteniendo algunas variables
fuente