Implementing ADTs using arrays · Implementación de ADT usando arrays
| English | Español |
|---|---|
| overflow/ˌəʊvəˈfləʊ/ | desbordamiento |
| underflow/ˌʌndəˈfləʊ/ | subdesbordamiento |
| circular array/ˈsɜːkjʊlə əˈreɪ/ | arreglo circular |
| free list/friː lɪst/ | lista libre |
There is no such thing as a stack in memory
- Open a computer and look for the stack. You will not find one. Memory is one enormous array of numbered cells, and that is all there is.
- Every stack, every queue, every linked list is that array plus two or three integer variables that remember where things are. Push is "add one to a number and store"; dequeue is "read a cell and add one to a different number".
- The whole of this lesson is bookkeeping: which pointers, which checks, and what happens at the edges.
- The exam asks you to describe the declarations, walk the pointers through a few operations, and say why the checks are there.
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.
A stack in an array
- Hold the items in
Stack[1:MaxSize]with an integerTop, 0 when the stack is empty. - Push(x): if
Top = MaxSizethe stack is full, an overflow 溢出; otherwiseTop ← Top + 1andStack[Top] ← x. - Pop(): if
Top = 0the stack is empty, an underflow 下溢; otherwise returnStack[Top]andTop ← Top − 1.
The array never moves; only Top does
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, se produce un overflow (desbordamiento); de lo contrarioTop ← Top + 1yStack[Top] ← x. - Pop(): si
Top = 0la pila está vacía, se produce un underflow (subdesbordamiento); de lo contrario devuelvaStack[Top]yTop ← Top − 1.
El array nunca se mueve; solo Top lo hace
Pushing an item onto a stack that is already full causes a stack ______. · Empujar un elemento a una pila que ya está llena causa un desbordamiento de pila ______.
Overflow = push when Top = MaxSize; popping from an empty stack (Top = 0) is underflow. · Overflow = push cuando Top = MaxSize; pop en una pila vacía (Top = 0) es underflow.
Match each array-stack condition to what it means. · Asocia cada condición de la pila basada en array con su significado.
Top counts the items: 0 = empty, MaxSize = full; the two error cases are underflow and overflow. · Top cuenta los elementos: 0 = vacío, MaxSize = lleno; los dos casos de error son underflow y overflow.
Worked example: declare and initialise the stack
- Describe the declarations and initialisation needed to implement a stack of up to 50 integers using an array. [5]
- An array of 50 elements of type
INTEGER,DECLARE Stack : ARRAY[1:50] OF INTEGER, to hold the items. - A constant or variable
MaxSizeset to 50, so that push can test for full. - An
INTEGERtop-of-stack pointer,Top, initialised to 0 to show the stack is empty; pop tests it for underflow, and push compares it withMaxSizefor 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.
Which belong in the declaration and initialisation of an array-based stack? Select all · todos that apply. · ¿Qué elementos pertenecen a la declaración e inicialización de una pila basada en array? Selecciona todos los que correspondan.
A stack needs one pointer, Top. A front pointer belongs to a queue. · Una pila necesita un solo puntero, Top. Un puntero front pertenece a una cola.
A queue in a plain array
- Two pointers:
Frontfor the next item to leave,Rearfor the next free space. Enqueue stores atRearand moves it on; dequeue reads atFrontand moves it on. - Both pointers only ever move forward, so after a few operations they march off the end of the array while the cells at the start sit empty and unusable.
- The fix is to let the pointers wrap around.
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.
The circular array
- A circular array 循环数组 wraps a pointer back to the first cell when it passes the last: with 1-based indices,
Rear ← (Rear MOD MaxSize) + 1. - Enqueue(x): check not full;
Rear ← (Rear MOD MaxSize) + 1;Queue[Rear] ← x. Dequeue(): check not empty; returnQueue[Front];Front ← (Front MOD MaxSize) + 1. - Keep a separate count: when the queue is completely full and when it is completely empty the two pointers are in the same relative position, so the pointers alone cannot tell the two apart.
After the last cell comes the first cell
El array circular
- Un array circular 循环数组 devuelve un punter a la primera celda cuando pasa 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
Implementing ADTs with arrays · Implementación de ADT con arrays
FIFO
A queue · cola is first-in-first-out — enqueue at the back, dequeue from the front. · Una cola es primero en entrar, primero en salir: se inserta al final y se extrae desde el frente.
Why use a circular array for a queue? · ¿Por qué usar un array circular para una cola?
A linear queue wastes the cells at the start as Front advances; wrapping with MOD reuses them. · Una cola lineal desperdicia las celdas al inicio mientras Front avanza; dar la vuelta con MOD las reutiliza.
A circular queue uses MOD so the front/rear pointers wrap around and reuse the cells freed at the start of the array. · Una cola circular usa MOD para que los punteros front/rear den la vuelta y reutilicen las celdas liberadas al inicio del array.
(pointer MOD MaxSize) + 1 wraps the index back to the first cell, so a linear queue no longer wastes the cells Front has passed. · (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.
Worked example: walk the pointers
- With
MaxSize = 6: ifRear = 5, then(5 MOD 6) + 1 = 6, so the next item goes in cell 6. IfRear = 6, then(6 MOD 6) + 1 = 1: the pointer wraps to cell 1. - A circular queue is held in an array of size 5, indices 0 to 4, with
Front = 3,Rear = 3and one item stored. Two items are added, then two removed. With 0-based indices each move is(pointer + 1) MOD 5. - Adding twice moves
Rear: 3 → 4, then 4 → 0, because (4 + 1) MOD 5 = 0. Removing twice movesFront: 3 → 4 → 0. One item remains, at index 0, and the queue reused the cells freed at the start of the array.
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.
A circular queue uses cells 1 to 6 and Rear = 6. After Rear ← (Rear MOD 6) + 1, where does the next item go? · 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?
6 MOD 6 = 0, plus 1 gives 1. The pointer wraps to the start of the array. · 6 MOD 6 = 0, más 1 da 1. El puntero da la vuelta al inicio del array.
Worked example: the enqueue algorithm in words
- Describe the algorithm for adding an item to a circular queue. [4]
- If the count equals the size, report that the queue is full and stop.
- Otherwise add one to the rear pointer; if it is now past the last index, set it to the first index.
- Store the item at the rear pointer and add one to the count.
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.
Put the steps of adding to a circular queue in order. · Ordena los pasos para agregar a una cola circular.
Check, move, wrap, store, count. The wrap is what makes the array circular. · Verificar, mover, dar la vuelta, almacenar, contar. La vuelta es lo que hace al array circular.
A linked list in an array
- Use an array of node records, each with a
Nextindex;-1marks the end. AHeadindex marks the first node,-1if the list is empty. - The unused slots are chained into a free list 空闲列表 from
FreeListHead, exactly as the data list chains its used ones.
- Insert: take the slot at
FreeListHead, set itsValueandNext, then rewire the previous node'sNextorHead. Delete: unlink the node and return its slot to the front of the free list.
Two lists share one array: the data list and the free list
Una lista enlazada en un array
- Utilice un array de registros de nodos, cada uno con un
Nextíndice;-1marca el final. UnHeadíndice marca el primer nodo,-1si la lista está vacía. - Las ranuras no utilizadas se encadenan en una lista libre 空闲列表 desde
FreeListHead, exactamente como la lista de datos encadena los utilizados.
TYPE TNode
DECLARE Value : INTEGER
DECLARE Next : 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 suValueyNext, luego reconecte elNextdel 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
In an array-based linked list, the free list: · En una lista enlazada basada en array, la free list:
The free list links the spare slots, so an insert can grab one and a delete can return one — like a second linked list of empties. · 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.
Worked example: insert into the array-held list
DataandPointerarrays hold the list 1 → 3 → 4, withStart = 1; index 1 holdsD40, index 3 holdsD32, index 4 holdsD11with a null pointer. The free list starts at index 2 and continues 2 → 5. InsertD6betweenD32andD11.- Take the first free node, index 2, and set
FreeStartto its pointer, 5. StoreD6inData[2]. - Set
Pointer[2]to the valuePointer[3]held, which is 4. Then setPointer[3]to 2. - The list now reads 1 → 3 → 2 → 4 and the free list is 5 → null. The implementation, if asked: an array for the data, a parallel array (or record field) for the pointers, a start pointer, and a free-list pointer.
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.
In the worked example, after D6 is inserted the free list starts at index ____. · En el ejemplo resuelto, después de insertar D6, la free list comienza en el índice ____.
Index 2 was taken from the free list, so FreeStart moves to what index 2 pointed to, which was 5. · 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.
When inserting into the list, the previous node's pointer should be changed before the new node's pointer is set. · Al insertar en la lista, el puntero del nodo anterior debe cambiarse antes de que se establezca el puntero del nuevo nodo.
Set the new node's pointer to the old next node first. Rewiring the previous node first loses the address of the rest of the list. · Establece primero el puntero del nuevo nodo al antiguo siguiente. Recablear el nodo anterior primero pierde la dirección del resto de la lista.
Marks that slip away
- The checks come first: full before push or enqueue, empty before pop or dequeue. Describe them; they are marks.
- The wrap formula depends on the indices:
(Rear MOD MaxSize) + 1for 1-based,(Rear + 1) MOD Sizefor 0-based. Match the question's bounds. - The count is what tells a full circular queue from an empty one. Pointers alone cannot.
- Set the new node's
Nextbefore rewiring the previous node, and return a deleted node's slot to the free list, or the array slowly fills with unreachable cells.
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
Nextdel 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.
You've got it
- stack in an array:
Stack[1:MaxSize]and aToppointer starting at 0;Top = MaxSizeis overflow,Top = 0is underflow - circular queue:
FrontandRearwrap withMOD; a separate count distinguishes full from empty - linked list in an array: node records with a
Nextindex, aHead, and a free list chaining the spare slots - every operation is check, then pointer arithmetic, then store or read; the ADT's behaviour is unchanged by how it is stored
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 ⟨
Next⟩, 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