¿Cuáles son las diferencias y conexiones entre pilas?
La diferencia entre montón y pila:
1. Diferencias en la asignación del espacio de la pila:
1. Pila (sistema operativo): asignada, liberada y almacenada automáticamente. por el sistema operativo Valores de parámetros de función, valores de variables locales, etc. Su método de operación es similar a la pila en la estructura de datos;
2. Montón (sistema operativo): generalmente lo asigna y libera el programador. Si el programador no lo libera, puede reciclarlo. por el sistema operativo cuando finaliza el programa. El método de asignación es similar a una lista vinculada.
2. Diferencias en los métodos de almacenamiento en caché de la pila:
1. La pila utiliza un caché de primer nivel. Generalmente están en el espacio de almacenamiento cuando se llaman y se liberan inmediatamente. la llamada se completa;
p>
2. El montón se almacena en el caché de segundo nivel y su ciclo de vida está determinado por el algoritmo de recolección de basura de la máquina virtual (no es que pueda ser así). reciclado una vez que se convierte en un objeto huérfano). Por lo tanto, la velocidad de llamada de estos objetos es relativamente baja.
3. Diferencias entre las estructuras de datos de la pila:
Montón (estructura de datos): el montón se puede considerar como un árbol, como por ejemplo: clasificación del montón;
Pila (estructura de datos): una estructura de datos de primero en entrar y último en salir.
Información ampliada:
El montón admite los siguientes conceptos básicos:
1.build: crea un montón vacío;
2.insert: Insertar un nuevo elemento en el montón;
3.update: promociona el nuevo elemento para que se ajuste a las propiedades del montón;
4.get: obtiene el valor del elemento superior actual del montón;
5.delete: elimina el elemento superior del montón
6.heapify: convierte el montón donde se elimina el elemento superior del montón; un montón de nuevo.
Algunas implementaciones del montón también admiten otras operaciones. Por ejemplo, el montón de Fibonacci admite comprobar si un elemento existe en un montón.
Algoritmo básico de pila
1. Algoritmo PUSH
①Si TOP≥n, se proporcionará información de desbordamiento y se realizará el manejo de errores (antes de insertar en la pila, primero verifique si la pila está llena; si está llena, se desbordará; si no, haga ②);
②Establezca TOP=TOP+1 (el puntero de la pila aumenta en 1, apuntando a la dirección de inserción
③S(TOP)=X, end (); X es el elemento recién insertado en la pila);
2. Algoritmo de extracción de la pila (POP)
①Si TOP≤0, se proporcionará información de subdesbordamiento y se realizará el manejo de errores (antes de extraer la pila, verifique si la pila está vacía, si está vacía, se desbordará; si no está vacío, haga ②);
②X=S(TOP), (el elemento después de salir de la pila se asigna a la parte superior).
Referencia: Enciclopedia Baidu: Pila
Enciclopedia Baidu: Pila