La pila no es más que la estructura de datos lineal donde la inserción y la eliminación tienen lugar solo en un extremo. La operación de inserción tiene un nombre especial conocido como PUSH y la operación de eliminación también tiene un nombre especial conocido como POP. El PUSH y POP son dos operaciones fundamentales que se podrían realizar solo en una pila en particular. Es un grupo de ubicaciones de memoria y las ubicaciones de memoria están relacionadas con la memoria de lectura o la memoria de escritura. Esto se utiliza para almacenar información binaria durante la ejecución del programa, cuando estamos ejecutando cualquier programa, el contenido de ese programa se almacenará en la pila. Sigue Último en entrar primero en salir (LIFO) y se utiliza solo para almacenar y recuperar los datos, pero no para almacenar los datos. La breve explicación del puntero de pila / pila se analiza a continuación.
¿Qué es Stack / Stack Pointer?
Definición: La pila es un dispositivo de almacenamiento que se utiliza para almacenar información o datos en forma de LIFO (último en entrar, primero en salir). Siempre que ingresamos los datos en forma LIFO, el elemento que debe eliminarse primero es el último elemento insertador, por lo que el último elemento insertado se saca primero. Es la unidad de memoria dentro de un registro de direcciones llamado puntero de pila (SP). El puntero de la pila siempre indica el elemento superior de la pila, lo que significa en qué ubicación se deben insertar los datos.
Tipos de pila
Hay dos tipos de pilas: pila de registros y pila de memoria.
Pila de registro
La pila de registros también es un dispositivo de memoria presente en la unidad de memoria, pero maneja solo una pequeña cantidad de datos. La profundidad de la pila siempre está limitada en la pila de registros porque el tamaño de la pila de registros es muy pequeño en comparación con la memoria.
Empujar la operación en la pila de registros
Paso 1: El puntero de la pila se incrementa en 1.
SP←SP+1
Paso 2: Ingrese los datos en la pila.
1000 [SP] ← CT
Donde DR es el registro de datos
Paso 3: Compruebe si la pila está llena o no
si (sp = 0) entonces (completo ← 1)
Paso 4: Marcar no vacío
empty←0
Operación emergente en la pila de registros
Paso 1: Leer datos de la pila.
DR ← M [SP]
Paso 2: Disminuir el punto de pila.
SP←SP-1
Paso 3: Compruebe si la pila está vacía o no
si sp = 0 entonces vacío ← 1
La organización de la pila de la pila de registros de 64 bits se muestra en la siguiente figura.
Registro de la organización de la pila
Pila de memoria
En la pila de memoria, la profundidad de la pila es flexible. Ocupa una gran cantidad de datos de memoria, mientras que en la pila de registros solo se almacenará un número finito de palabras de memoria.
Empuje la operación en la pila de memoria
Paso 1: SP←SP-1
Paso 2: 1000 [SP] ← CT
Operación emergente en Memory Stack
Paso 1: DR ← M [SP]
Paso 2: SP←SP-1
En comparación con la unidad de registro, la unidad de memoria almacena una gran cantidad de datos. La figura de la pila de memoria se muestra en la siguiente figura.
Pila de memoria
La unidad de memoria total se divide en tres partes, la primera unidad de memoria tiene el programa (nada más que instrucciones), la segunda parte son datos (operandos) y la tercera parte es pila. Las instrucciones del programa siempre se almacenan en el contador del programa (PC), los registros de datos son identificados por el registro de direcciones (AR). La dirección 3000 a 4001 utilizada para la pila y el primer artículo o elemento se almacena en 4001.
Apilado / puntero de apilado en microprocesador 8085
La vista del programador de 8085 microprocesador contiene registros de propósito general y registros de propósito especial . Los registros de propósito general son A, B, C, D, E, H, L, y los registros de propósito especial son SP (Stack Pointer) y PC (Program Counter). La vista del programador del microprocesador 8085 se muestra en la siguiente figura.
Vista del programador del 8085
El puntero de pila es un registro de 16 bits que contiene la dirección de memoria, suponga que el contenido del puntero de pila (SP) es FC78H, luego el microprocesador 8085 lo interpreta. Las ubicaciones de memoria tienen información útil de FC78H a FFFH y de FC77H a 0000H la ubicación de memoria no tiene información útil. La interpretación del puntero de pila se muestra en la siguiente figura.
Interpretación del puntero de pila
Operaciones básicas del puntero de pila / pila
Hay dos operaciones de la pila que son: operación PUSH y operación POP.
Operación PUSH
El PUSH significa empujar o insertar un elemento en la pila. La operación PUSH siempre incrementa el puntero de la pila y la operación POP siempre reduce el puntero de la pila. En el caso de una operación push, tenemos que comprobar si hay espacio libre disponible o no. Si hay espacio libre disponible, podemos ir a la operación de empuje, si el espacio libre no está disponible, aparece un mensaje de error de desbordamiento. El desbordamiento debe comprobarse en caso de operación de empuje respectivamente. La operación básica de push y pop se muestra en la siguiente figura.
Operación básica de PUSH y POP
La figura (a) es la pila. Si desea empujar el elemento que está insertando el elemento en la pila, debe empujar (s, a), donde 's' no es más que una pila. En la pila, colocamos el elemento 'a' y esta operación se muestra en la figura (b). Vea la figura (3), suponga que la pila contiene tres elementos a, b, c, y la pila está llena con un elemento.
Si desea insertar un cuarto elemento-'d' usando push (s, d), pero no hay espacio disponible para insertar el elemento, entonces indica que la pila está desbordada. La terminología de desbordamiento se utiliza cuando la pila está llena y el algoritmo de la operación de inserción se muestra a continuación.
empujar (pila [], superior, pila máxima, elemento)
si (top == maxstack-1)
{
imprimir 'desbordamiento'
}
demás
{
arriba = arriba + 1
pila [parte superior] = elemento
}
fin
Operación POP
El POP significa eliminar el elemento en la parte superior de la pila. En el caso de la operación pop, tenemos que comprobar si la pila está inicialmente vacía o no. Si la pila está inicialmente vacía, se produce una situación de desbordamiento. Suponga que la pila está vacía y aún desea colocar los elementos en la pila, pero no hay elementos en la pila, lo que provoca un desbordamiento de la pila.
El subdesbordamiento debe comprobarse en caso de operación emergente, respectivamente. En la operación emergente, cualquiera que sea el elemento superior que esté presente en la pila y que deba extraerse o eliminarse, no es necesario mencionar qué elemento aparecerá, de forma predeterminada se mostrará el elemento superior. El algoritmo de operación pop se muestra a continuación.
pop (pila [], superior, elemento)
si (arriba == - 1)
{
imprimir 'subdesbordamiento'
}
demás
{
item = stack [top]
top = top-1
}
Ejemplo
Los elementos se insertan en el orden A, B, C, D, E, representa la pila de cinco elementos. En la figura (a), queremos empujar el elemento 'A' en la pila, luego la parte superior se convierte en cero (parte superior = 0), de manera similar, la parte superior = 1 cuando se presiona el elemento 'B', la parte superior = 2 cuando el elemento 'C' se presiona, top = 3 cuando se presiona el elemento 'D', y top = 4 cuando se presiona el elemento 'E'.
Entonces, cualesquiera que sean los elementos que he tomado, se colocan en la pila, ahora la pila está llena. Si desea empujar otro elemento, no hay lugar en la pila, por lo que indica el desbordamiento. Ahora la pila está llena si desea hacer estallar el elemento 'E', el elemento debe eliminarse primero. La operación de empuje se muestra en la siguiente figura.
Operación de empuje
Tenemos que usar la operación pop para eliminar los elementos de la pila. Así que solo menciona pop (), no escribas argumentos en el pop porque, de forma predeterminada, elimina el elemento superior. El primer elemento 'E' se elimina junto al elemento 'D' ... .. 'A'. Cuando se eliminan los elementos superiores, el valor superior disminuye. Cuando top = -1, la pila indica subdesbordamiento. La operación pop se muestra en la siguiente figura.
Operación POP
Así que esta es la explicación de cómo se insertan y eliminan los elementos en la pila mediante la operación push y pop.
Aplicaciones
Las aplicaciones del puntero de pila / pila son
- Inversión de cuerdas
- Paréntesis equilibrado
- UNDO/DEDO
- Pila del sistema para registros de activación
- Infijo, prefijo, sufijo, expresión
Preguntas frecuentes
1). ¿Qué es el puntero de pila en el brazo?
El registro de puntero de pila (R13) utilizado como puntero a la pila activa en ARM.
2). ¿Por qué el puntero de pila es de 16 bits?
El puntero de pila (SP) y el contador de programa (PC) utilizados para almacenar la ubicación anterior y la dirección de la ubicación de memoria es de 16 bits, por lo que el puntero de pila (SP) también es de 16 bits.
3). ¿Cuál es la función del puntero de pila?
El papel del puntero de pila (SP) es indicar la parte superior del elemento en la pila.
4). ¿Qué pila se usa en 8085?
La pila utilizada en 8085 es Last In First Out (LIFO).
5). ¿El puntero de pila es un registro?
Sí, el puntero de pila (SP) es un registro de direcciones que siempre indica la parte superior del elemento en la pila.
