Qué es stack/stack pointer: tipos y sus aplicaciones

Stack no es más que la estructura de datos lineal donde la inserción y la eliminación solo tienen lugar en un extremo. La operación de inserción tiene un nombre especial llamado PUSH y la operación de eliminación también tiene un nombre especial llamado POP. PUSH y POP son dos operaciones fundamentales que solo se pueden realizar 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 usa para almacenar información binaria durante la ejecución del programa, cuando ejecutamos un programa, el contenido de este programa se almacenará en la pila. Sigue a Last In First Out (LIFO) y se usa solo para almacenar y recuperar datos, pero no para almacenar datos. La breve explicación de pila/puntero de pila se muestra a continuación.

¿Qué es el puntero de pila/pila?

Definición: Stack es un dispositivo de almacenamiento, que se utiliza para almacenar información o datos de manera LIFO (último en entrar, primero en salir). Cada vez que ingresamos los datos como LIFO, el elemento que debe eliminarse primero es el último elemento insertado, por lo que el último elemento insertado se elimina primero. Es la unidad de memoria en un registro de dirección llamado puntero de pila (SP). El puntero de la pila siempre indica el elemento superior de la pila, lo que significa dónde se deben insertar los datos.

Tipos de batería

Hay dos tipos de pilas: la pila de registro y la pila de memoria.

guardar pila

La pila de registros también es un dispositivo de memoria presente en la unidad de memoria, pero solo administra 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.

Empuje la operación en la pila de registro

Etapa 1: El puntero de la pila se incrementa en 1.

SP←SP+1

2do paso: Introduzca los datos en la pila.

METRO[SP]←RD

Donde DR es el registro de datos

Paso 3: Comprobar si la batería está llena o no

si (sp=0) entonces (completo←1)

Paso 4: Marcar no vacío

vacío←0

Operación pop en la pila de registros

Etapa 1: Leer datos de la pila.

DR←M[SP]

2do paso: Disminuye el punto de apilamiento.

SP←SP-1

Paso 3: Comprobar si la pila está vacía o no

si sp=0 entonces vacío←1

La organización de la pila de registros de 64 bits se muestra en la siguiente figura.

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.

Operación de inserción de pila de memoria

Etapa 1: SP←SP+1

2do paso: METRO[SP]←DR

Operación pop en la pila de memoria

Etapa 1: DR←M[SP]

2do paso: 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.

La unidad de memoria total se divide en tres partes, la primera unidad de memoria contiene el programa (solo instrucciones), la segunda parte contiene los datos (operandos) y la tercera parte es la pila. Las instrucciones del programa siempre se almacenan en el contador de programa (PC), los registros de datos se identifican mediante el registro de dirección (AR). La dirección 3000 a 4001 utilizada para la pila y el primer artículo o elemento se almacena en 4001.

Puntero de pila/pila en microprocesador 8085

La vista del programador del microprocesador 8085 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.

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, entonces 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.

Operaciones básicas de pila/puntero de pila

Hay dos operaciones de pila: la operación PUSH y la operación POP.

Operación PUSH

EMPUJAR 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 disminuye el puntero de la pila. En el caso de una operación push, es necesario comprobar si hay espacio libre disponible o no. Si hay espacio libre disponible, podemos proceder a la operación de inserción; si no hay espacio libre disponible, aparece un mensaje de error que indica desbordamiento. El desbordamiento debe verificarse en caso de operación de empuje respectivamente. La operación básica de empujar y abrir se muestra en la siguiente figura.

La figura (a) es la pila. Si desea empujar el elemento que empuja el elemento a 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 se llena con un elemento.

Si desea insertar un cuarto elemento-'d' usando push(s,d), pero no hay espacio disponible para insertar el elemento, esto indica que la pila se está desbordando. La terminología de desbordamiento se usa cuando la pila está llena y el algoritmo de la operación de inserción se muestra a continuación.

empujar (batería[]alto, pila máxima, artículo)

si (superior == maxstack-1)

{

imprimir "desbordamiento"

}

otro

{

arriba = arriba + 1

pila[top]= elemento

}

final

Operación POP

El POP significa eliminar el elemento en la parte superior de la pila. En el caso de una operación emergente, debemos verificar si la pila está inicialmente vacía o no. Si la pila está inicialmente vacía, se produce una situación de subdesbordamiento. Suponiendo que la pila está vacía, pero desea sacar los elementos de la pila pero no hay elementos en la pila, se produce un desbordamiento de la pila.

Undershoot debe verificarse en caso de operación pop respectivamente. En la operación de extracción, cualquiera que sea el elemento superior presente en la pila, debe extraerse o eliminarse, por lo que no es necesario mencionar qué elemento se extraerá; de forma predeterminada, se extraerá el elemento superior. El algoritmo de la operación pop se muestra a continuación.

estallar (apilar)[]arriba, artículo)

si (alto == -1)

{

imprimir "subdesbordamiento"

}

otro

{

elemento = pila[top]

superior=superior-1

}

Ejemplo

Los elementos se insertan en el orden A, B, C, D, E, esto representa la pila de cinco elementos. En la figura (a), queremos empujar el elemento 'A' a la pila, luego la parte superior se convierte en cero (parte superior = 0), de manera similar, la parte superior = 1 cuando se empuja el elemento 'B', la parte superior = 2 cuando se presiona el elemento 'C' , top=3 cuando se presiona el elemento 'D' y top=4 cuando se presiona el elemento 'E'.

Entonces, cualquier elemento que tomé se coloca en la pila, ahora la pila está llena. Si usted quiere empujando otro elemento, no hay espacio en la pila, por lo que indica desbordamiento. Ahora que la pila está llena, si desea hacer estallar, primero debe eliminar el elemento 'E'. La operación de empuje se muestra en la siguiente figura.

Necesitamos usar la operación pop para eliminar elementos de la pila. Así que solo mencione pop(), no escriba ningún argumento en el pop porque, de forma predeterminada, elimina el elemento superior. El primer elemento 'E' se elimina junto al elemento 'D'…..'A'. A medida que se eliminan los elementos superiores, el valor superior disminuye. Cuando top=-1, la pila indica un subdesbordamiento. La operación pop se muestra en la siguiente figura.

Así que aquí está la explicación de cómo los elementos se insertan y eliminan de la pila mediante la operación de empujar y sacar.

Aplicaciones

Las aplicaciones de puntero de pila/pila son

• inversión de cadena
• paréntesis equilibrado
• CANCELAR/CANCELAR
• Pila del sistema para la activación de grabaciones
• 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 la 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 ubicación de memoria son de 16 bits, por lo que el puntero de pila (SP) también es de 16 bits.

3). ¿Cuál es el papel del puntero de pila?

La función 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 dirección que siempre apunta a la parte superior del elemento de la pila.

En este artículo lo que es pila/puntero de pila (SP), operación push y operación pop con un ejemplo, pila de registro y pila de memoria con diagramas, puntero de pila y pila en 8085 y aplicaciones. Aquí hay una pregunta para usted: ¿cuál es el uso de stack/stack pointer?