Implementación de ADT usando arrays
Introducido| English | Significado |
|---|---|
| overflow/ˌəʊvəˈfləʊ/ | desbordamiento |
| underflow/ˌʌndəˈfləʊ/ | desbordamiento inferior |
| circular array/ˈsɜːkjʊlə əˈreɪ/ | array circular |
| free list/friː lɪst/ | lista libre |
No existe tal cosa como una pila en la memoria
- Abra un ordenador y busque la pila. No la encontrará. La memoria es un enorme array de celdas numeradas, y eso es todo lo que hay.
- Cada pila, cada cola y cada lista enlazada son ese array más dos o tres variables enteras que recuerdan dónde están las cosas. Un push (empujar) es "sumar uno a un número y almacenar"; un dequeue (sacar) es "leer una celda y sumar uno a un número diferente".
- Toda esta lección trata de llevar la contabilidad: qué punteros, qué comprobaciones y qué sucede en los bordes.
- El examen le pide describir las declaraciones, recorrer los punteros con algunas operaciones y explicar por qué existen las comprobaciones.
Una pila en un array
- Mantenga los elementos en
Stack[1:MaxSize]usando un enteroTop, 0 cuando la pila está vacía. - Push(x): si
Top = MaxSizela pila está llena, hay un desbordamiento; de lo contrario,Top ← Top + 1yStack[Top] ← x. - Pop(): si
Top = 0la pila está vacía, hay un subdesbordamiento; de lo contrario, retornaStack[Top]yTop ← Top − 1.

El array nunca se mueve; solo Top lo hace
Empujar un elemento a una pila que ya está llena causa un desbordamiento de pila ______.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Overflow = push cuando Top = MaxSize; pop en una pila vacía (Top = 0) es underflow.
Asocia cada condición de la pila basada en array con su significado.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Top cuenta los elementos: 0 = vacío, MaxSize = lleno; los dos casos de error son underflow y overflow.
Ejemplo resuelto: declarar e inicializar la pila
- Describa las declaraciones e inicialización necesarias para implementar una pila de hasta 50 enteros usando un array. [5]
- Un array de 50 elementos del tipo
INTEGER,DECLARE Stack : ARRAY[1:50] OF INTEGER, para guardar los elementos. - Una constante o variable
MaxSizeestablecida en 50, para que el push pueda comprobar si está llena. - Un
INTEGERpunter de tope de pila,Top, inicializado a 0 para indicar que la pila está vacía; el pop lo comprueba para detectar subdesbordamientos, y el push lo compara conMaxSizepara detectar desbordamientos.
¿Qué elementos pertenecen a la declaración e inicialización de una pila basada en array? Selecciona todos los que correspondan.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Una pila necesita un solo puntero, Top. Un puntero front pertenece a una cola.
Una cola en un array simple
- Dos punteros:
Frontpara el próximo elemento en salir,Rearpara el próximo espacio libre. El enqueue almacena enReary lo avanza; el dequeue lee enFronty lo avanza. - Ambos punteros solo se mueven hacia adelante, por lo que tras unas pocas operaciones marchan fuera del final del array mientras las celdas al principio quedan vacías e inutilizables.
- La solución es permitir que los puntores den vueltas.
El array circular
- Un arreglo circular devuelve un puntero a la primera celda cuando supera la última: con índices basados en 1,
Rear ← (Rear MOD MaxSize) + 1. - Enqueue(x): compruebe que no esté llena;
Rear ← (Rear MOD MaxSize) + 1;Queue[Rear] ← x. Dequeue(): compruebe que no esté vacía; devuelvaQueue[Front];Front ← (Front MOD MaxSize) + 1. - Mantenga un count (recuento) separado: cuando la cola está completamente llena y cuando está completamente vacía, los dos punteros ocupan la misma posición relativa, por lo que los punteros solos no pueden distinguir entre ambos casos.

Después de la última celda viene la primera celda
Implementación de ADT con arrays
FIFO
Una cola es primero en entrar, primero en salir: se inserta al final y se extrae desde el frente.
¿Por qué usar un array circular para una cola?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Una cola lineal desperdicia las celdas al inicio mientras Front avanza; dar la vuelta con MOD las reutiliza.
Una cola circular usa MOD para que los punteros front/rear den la vuelta y reutilicen las celdas liberadas al inicio del array.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
(pointer MOD MaxSize) + 1 devuelve el índice a la primera celda, por lo que una cola lineal ya no desperdicia las celdas que Front ha pasado.
Ejemplo resuelto: recorrer los punteros
- Con
MaxSize = 6: siRear = 5, entonces(5 MOD 6) + 1 = 6, por lo que el próximo elemento va en la celda 6. SiRear = 6, entonces(6 MOD 6) + 1 = 1: el puntero vuelve a la celda 1. - Una cola circular se almacena en un array de tamaño 5, índices del 0 al 4, con
Front = 3,Rear = 3y un elemento almacenado. Se añaden dos elementos, luego se eliminan dos. Con índices basados en 0, cada movimiento es(pointer + 1) MOD 5. - Añadir dos veces mueve
Rear: 3 → 4, luego 4 → 0, porque (4 + 1) MOD 5 = 0. Eliminar dos veces mueveFront: 3 → 4 → 0. Queda un elemento, en el índice 0, y la cola reutilizó las celdas liberadas al inicio del array.
Una cola circular usa celdas de 1 a 6 y Rear = 6. Después de Rear ← (Rear MOD 6) + 1, ¿dónde va el próximo elemento?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
6 MOD 6 = 0, más 1 da 1. El puntero da la vuelta al inicio del array.
Ejemplo resuelto: el algoritmo de enqueue en palabras
- Describa el algoritmo para añadir un elemento a una cola circular. [4]
- Si el conteo es igual al tamaño, informe que la cola está llena y deténgase.
- De lo contrario, sume uno al puntero trasero; si ahora supera el último índice, establézcalo en el primer índice.
- Almacene el elemento en el puntero trasero y sume uno al conteo.
Ordena los pasos para agregar a una cola circular.
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
Verificar, mover, dar la vuelta, almacenar, contar. La vuelta es lo que hace al array circular.
Una lista enlazada en un array
- Utilice un array de registros de nodos, cada uno con un
NextIndexíndice;-1marca el final. UnHeadíndice marca el primer nodo,-1si la lista está vacía. - Los espacios no utilizados se encadenan en una lista de espacio libre desde
FreeListHead, exactamente como la lista de datos encadena los utilizados.
TYPE TNode
DECLARE Value : INTEGER
DECLARE NextIndex : INTEGER // index of the next node, or -1
ENDTYPE
DECLARE Nodes : ARRAY[1:MaxSize] OF TNode
DECLARE Head : INTEGER // -1 when empty
DECLARE FreeListHead : INTEGER // first unused slot
- Insertar: tome la ranura en
FreeListHead, establezca suValueyNextIndex, luego reconecte elNextIndexdel nodo anterior oHead. Eliminar: desconecte el nodo y devuelva su ranura al frente de la lista libre.

Dos listas comparten un solo array: la lista de datos y la lista libre
En una lista enlazada basada en array, la free list:
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
La free list conecta los slots sobrantes, así que una inserción puede tomar uno y una eliminación devolver uno — como una segunda lista enlazada de espacios vacíos.
Ejemplo resuelto: insertar en la lista mantenida en el array
- Los arrays
DatayPointercontienen la lista 1 → 3 → 4, conStart = 1; el índice 1 contieneD40, el índice 3 contieneD32, el índice 4 contieneD11con un puntero nulo. La lista de espacios libres comienza en el índice 2 y continúa 2 → 5. InsertaD6entreD32yD11. - Toma el primer nodo libre, índice 2, y establece
FreeStarta su puntero, 5. AlmacenaD6enData[2]. - Establece
Pointer[2]al valorPointer[3]que se almacena, que es 4. Luego establecePointer[3]a 2. - La lista ahora lee 1 → 3 → 2 → 4 y la lista de espacios libres es 5 → nulo. La implementación, si se pregunta: un array para los datos, un array paralelo (o campo de registro) para los punteros, un puntero de inicio y un puntero de lista de espacios libres.
En el ejemplo resuelto, después de insertar D6, la free list comienza en el índice ____.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
El índice 2 fue tomado de la free list, por lo que FreeStart se mueve a lo que el índice 2 apuntaba, que era 5.
Al insertar en la lista, el puntero del nodo anterior debe cambiarse antes de que se establezca el puntero del nuevo nodo.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Establece primero el puntero del nuevo nodo al antiguo siguiente. Recablear el nodo anterior primero pierde la dirección del resto de la lista.
Puntos que se pierden fácilmente
- Las comprobaciones vienen primero: lleno antes de hacer push o enqueue, vacío antes de hacer pop o dequeue. Descríbelas; son marcas.
- La fórmula de retorno depende de los índices:
(Rear MOD MaxSize) + 1para bases 1,(Rear + 1) MOD Sizepara bases 0. Ajusta los límites según la pregunta. - El conteo es lo que distingue una cola circular llena de una vacía. Los punteros solos no pueden hacerlo.
- Establece el
NextIndexdel nuevo nodo antes de reconfigurar el nodo anterior, y devuelve la ranura de un nodo eliminado a la lista de espacios libres, de lo contrario el array se llenará lentamente de celdas inaccesibles.
Lo has entendido
- pila en un array:
Stack[1:MaxSize]y un punteroTopcomenzando en 0;Top = MaxSizees desbordamiento,Top = 0es subdesbordamiento - cola circular:
FrontyRearretornan conMOD; un conteo separado distingue lleno de vacío - lista encadenada en un array: registros de nodos con un índice de ⟨
NextIndex⟩, un ⟨Head⟩, y una lista de espacios libres encadenando las ranuras sobrantes - cada operación es comprobación, luego aritmética de punteros, luego almacenamiento o lectura; el comportamiento del ADT no cambia por cómo se almacena