Abstract Data Types — stack, queue, linked list · Tipos de Datos Abstractos — pila, cola, lista enlazada
| English | Español |
|---|---|
| queue/kjuː/ | cola |
| push/pʊʃ/ | empuje |
| abstract data type/ˈæbstrækt ˈdeɪtə taɪp/ | tipo de dato abstracto |
| stack/stæk/ | pila |
| linked list/lɪŋkt lɪst/ | lista enlazada |
| LIFO/ˈlaɪfəʊ/ | LIFO |
| pop/pɒp/ | pop |
| pointer/ˈpɔɪntə/ | puntero |
| FIFO/ˈfaɪfəʊ/ | FIFO |
| enqueue/enˈkjuː/ | enqueue |
| dequeue/diːˈkjuː/ | dequeue |
| node/nəʊd/ | nodo |
| traverse/trəˈvɜːs/ | recorrer |
The Back button and the printer queue
- Every page you visit is pushed onto a pile; the Back button takes the top one off. The page you left most recently is the first you return to.
- Down the corridor, a printer works through jobs in the order they arrived. The document sent first comes out first, however small the ones behind it.
- Two structures, opposite rules, and you use both before break. Neither says how it is stored; each says only what its operations do.
- That is an abstract data type 抽象数据类型. This lesson is the three the syllabus names, the operations on each, and how to justify one for a situation.
El botón Atrás y la cola de impresión
- Cada página que visitas se apila; el botón Atrás toma la superior. La página que dejaste más recientemente es la primera a la que vuelves.
- En el pasillo, una impresora procesa trabajos en el orden en que llegaron. El documento enviado primero sale primero, sin importar lo pequeños que sean los que están detrás.
- Dos estructuras, reglas opuestas, y usas ambas antes del recreo. Ninguna dice cómo está almacenada; cada una dice solo qué hacen sus operaciones.
- Eso es un tipo de dato abstracto (TDA). Esta lección cubre los tres que menciona el programa, las operaciones de cada uno y cómo justificar la elección de uno para una situación concreta.
What an ADT is
- An abstract data type (ADT) is a collection of data together with a set of operations on that data. That one sentence is the one-mark definition.
- It is defined by what the operations do, not by how the data is stored. The implementation is hidden, so it can change without affecting the code that uses it.
- A stack, a queue, a linked list, a binary tree and an array are all ADTs.
¿Qué es un TDA?
- Un tipo de dato abstracto (TDA) es una colección de datos junto con un conjunto de operaciones sobre esos datos. Esa única oración es la definición de una marca.
- Se define por qué hacen las operaciones, no por cómo se almacenan los datos. La implementación está oculta, por lo que puede cambiar sin afectar al código que la utiliza.
- Una pila, una cola, una lista enlazada, un árbol binario y un array son todos TDAs.
An Abstract Data Type (ADT) is defined by: · Un Tipo de Dato Abstracto (ADT) se define por:
An ADT specifies the operations (the interface); the implementation is hidden and can change freely. · Un ADT especifica las operaciones (la interfaz); la implementación está oculta y puede cambiar libremente.
The stack
- A stack 栈 is a list in which items are added to and removed from the same end, the top, so the last item added is the first removed: LIFO 后进先出.
- Operations: push 入栈 adds to the top, pop 出栈 removes from the top, peek looks at the top, and tests for empty and full.
- Uses: undo history, the Back button, the return addresses of function calls, checking brackets, backtracking.
Everything happens at the top
La pila
- Una pila es una lista en la que los elementos se añaden y se eliminan por el mismo extremo, el tope, de modo que el último elemento añadido es el primero en eliminarse: LIFO (Last In, First Out / Último en entrar, Primero en salir).
- Operaciones: push añade al tope, pop elimina del tope, peek mira el tope, y pruebas para ver si está vacía o llena.
- Usos: historial de deshacer, el botón Atrás, direcciones de retorno de llamadas a funciones, comprobación de paréntesis, retroceso (backtracking).
Todo sucede en el tope
A stack works in which order? · ¿En qué orden funciona una pila?
A stack is LIFO: the most recently pushed item is the first to be popped. · Una pila es LIFO: el elemento empujado más recientemente es el primero en ser extraído.
Worked example: trace the stack
- A stack holds, from the bottom,
'P' 'N' 'Z' 'X' 'Y' 'W'; the top pointer is at'W'. The operationsPOP,POP,PUSH 'A',PUSH 'B',POPare performed. What does the stack hold, and where is the pointer? - The two pops remove
'W'then'Y'. The pushes put'A'then'B'in their places. The last pop removes'B'. - The stack holds
'P' 'N' 'Z' 'X' 'A', with the pointer at'A'. The item on the stack longest is the bottom one,'P'; five more pops are possible, and a sixth would be an error, which is why pop tests for empty first.
Ejemplo resuelto: rastrear la pila
- Una pila contiene, desde abajo
'P' 'N' 'Z' 'X' 'Y' 'W'; el puntero superior está en'W'. Se realizan las operacionesPOP,POP,PUSH 'A',PUSH 'B',POP. ¿Qué contiene la pila y dónde está el puntero? - Los dos pops eliminan
'W'luego'Y'. Los pushes colocan'A'luego'B'en su lugar. El último pop elimina'B'. - La pila contiene
'P' 'N' 'Z' 'X' 'A', con el puntero en'A'. El elemento más antiguo en la pila es el inferior,'P'; son posibles cinco pops más, y un sexto sería un error, por eso el pop comprueba primero si está vacía.
A stack holds P N Z X Y W (top is W). After POP, POP, PUSH 'A', PUSH 'B', POP, which item is on top? · Una pila contiene P N Z X Y W (W está en la parte superior). Después de POP, POP, PUSH 'A', PUSH 'B', POP, ¿qué elemento queda en la parte superior?
W and Y are popped, A then B pushed, B popped. The top is A, above X. · Se extraen W e Y, se empujan A luego B, se extrae B. La parte superior es A, sobre X.
The queue
- A queue 队列 is a list in which items are added at the rear and removed from the front, so the first item added is the first removed: FIFO 先进先出.
- Operations: enqueue 入队 adds at the rear, dequeue 出队 removes from the front, and tests for empty and full.
- Uses: print spooling, keyboard buffers, scheduling, customers in a shop, breadth-first search.
Join at the back, leave from the front
La cola
- Una cola es una lista en la que los elementos se añaden en la parte trasera y se eliminan por el frente, de modo que el primer elemento añadido es el primero en eliminarse: FIFO (First In, First Out / Primero en entrar, Primero en salir).
- Operaciones: enqueue añade en la parte trasera, dequeue elimina del frente, y pruebas para ver si está vacía o llena.
- Usos: spooling de impresión, buffers de teclado, planificación, clientes en una tienda, búsqueda en anchura (breadth-first search).
Añade por atrás, sal por delante
Stacks, queues & linked lists · Pilas, colas y listas enlazadas
LIFO vs FIFO
A stack · pila is last-in-first-out; push and pop happen at the same end (the top). · Una pila es último-en-primer-salir; el push y el pop ocurren en el mismo extremo (la parte superior).
A queue is first-in-first-out: items are removed from the ______ and added at the rear. · Una cola es primero-en-entrar-primer-salir: los elementos se eliminan desde el ______ y se añaden en la parte trasera.
FIFO: dequeue from the front, enqueue at the rear — like a line of people. · FIFO: dequeue desde el frente, enqueue en la parte trasera — como una fila de personas.
Worked example: describe adding to and removing from a queue
- Adding: check that the queue is not full; store the item at the position given by the rear pointer; move the rear pointer on (and add one to the count).
- Removing: check that the queue is not empty; read the item at the front pointer; move the front pointer on (and subtract one from the count).
- State the convention you use: if the rear pointer marks the next free space, store first and then move; if it marks the last item, move first and then store. Either scores, if you are consistent.
Ejemplo resuelto: describir añadir y eliminar de una cola
- Añadir: verificar que la cola no esté llena; almacenar el elemento en la posición indicada por el puntero trasero; mover el puntero trasero (y sumar uno al contador).
- Eliminar: verificar que la cola no esté vacía; leer el elemento en el puntero frontal; mover el puntero frontal (y restar uno al contador).
- Establece la convención que uses: si el puntero trasero marca el siguiente espacio libre, almacena primero y luego mueve; si marca el último elemento, mueve primero y luego almacena. Ambas obtienen puntos si eres consistente.
Put the steps of adding an item to a queue in order (rear pointer marks the next free space). · Ordena los pasos para añadir un elemento a una cola (el puntero rear marca el próximo espacio libre).
The check comes first; then store, then move, under this convention. Say which convention you use. · La comprobación viene primero; luego almacenar, luego mover, bajo esta convención. Indica qué convención usas.
The linked list
- A linked list 链表 is a list in which each node 节点 holds a data item and a pointer 指针 to the next node, with a start pointer to the first node. The last node's pointer is a sentinel such as
NULL. - Operations: insert, delete, search, and traverse 遍历, following the pointers from the head to visit every node in order.
- Advantage over an array: inserting or deleting is cheap, just rewire pointers, and the list grows as needed. Disadvantage: no random access; reaching the tenth node means following nine pointers.
A value and an arrow, repeated
La lista enlazada
- Una lista enlazada es una lista en la que cada nodo contiene un elemento de datos y un puntero al siguiente nodo, con un puntero de inicio al primer nodo. El puntero del último nodo es un valor de sentinela como
NULL. - Operaciones: insertar, eliminar, buscar y recorrer, siguiendo los punteros desde la cabeza para visitar cada nodo en orden.
- Ventaja sobre un array: insertar o eliminar es barato, solo reconfigurar punteros, y la lista crece según sea necesario. Desventaja: no hay acceso aleatorio; llegar al décimo nodo significa seguir nueve punteros.
Un valor y una flecha, repetidos
A linked list: nodes joined by pointers · Una lista enlazada: nodos unidos por punteros
Each node stores a value and a pointer to the next node. Inserting or deleting just re-links pointers — no items shift along, unlike an array. · Cada nodo almacena un valor y un puntero al siguiente nodo. Insertar o eliminar solo re-conecta los punteros — ningún elemento se desplaza, a diferencia de un array.
Each node of a linked list holds: · Cada nodo de una lista enlazada contiene:
A node stores its value plus a pointer (reference) to the next node; the head marks the start, NULL the end. · Un nodo almacena su valor más un puntero (referencia) al siguiente nodo; el head marca el inicio, NULL el final.
A linked list makes inserting/deleting cheap (just rewire pointers) but random access slow (you must follow pointers from the head). · Una lista enlazada hace que insertar/eliminar sea barato (solo reconfigurar punteros) pero el acceso aleatorio sea lento (hay que seguir los punteros desde el head).
That is the array-vs-list trade-off: arrays give O(1) index access; lists give cheap insert/delete. · Esa es la compensación entre array y lista: los arrays dan acceso O(1) por índice; las listas dan inserción/eliminación barata.
Worked example: add a node in order
- Describe how a new value is inserted into a linked list that is kept in ascending order. [4]
- Traverse the list from the head, following the pointers, until the node before the position is found: the last node whose value is smaller than the new one.
- Take a free node and store the new value in it. Set the new node's pointer to the address the previous node currently points to.
- Then set the previous node's pointer to the new node. If the new value belongs at the front, it is the head pointer that changes instead.
Ejemplo resuelto: añadir un nodo en orden
- Describe cómo se inserta un nuevo valor en una lista enlazada mantenida en orden ascendente. [4]
- Recorre la lista desde la cabeza, siguiendo los punteros, hasta encontrar el nodo anterior a la posición deseada: el último nodo cuyo valor sea menor que el nuevo.
- Toma un nodo libre y almacena el nuevo valor en él. Establece el puntero del nuevo nodo a la dirección a la que actualmente apunta el nodo anterior.
- Luego establece el puntero del nodo anterior al nuevo nodo. Si el nuevo valor debe ir al principio, cambia el puntero de cabeza en su lugar.
Put the steps of inserting a value into an ordered linked list in order. · Ordena los pasos para insertar un valor en una lista enlazada ordenada.
Find, fill, point the new node forward, then rewire the previous node. Reversing the last two loses the rest of the list. · Encontrar, rellenar, apuntar el nuevo nodo hacia adelante, luego reconfigurar el nodo anterior. Invertir los últimos dos pierde el resto de la lista.
Justifying the choice
- Items must be handled in the order they arrived, print jobs, key presses, customers: a queue, because it is first in, first out.
- The most recent item must be handled first, undo, going back, nested calls: a stack, because it is last in, first out.
- Items are frequently inserted or deleted in the middle of an ordered collection, and the size is unknown: a linked list, because only pointers change and nothing is shifted.
- Name the structure, name its rule, tie the rule to the situation.
Justificar la elección
- Los elementos deben manejarse en el orden en que llegaron, trabajos de impresión, pulsaciones de tecla, clientes: una cola, porque es primero en entrar, primero en salir.
- El elemento más reciente debe manejarse primero, deshacer, retroceder, llamadas anidadas: una pila, porque es último en entrar, primero en salir.
- Los elementos se insertan o eliminan frecuentemente en el medio de una colección ordenada, y el tamaño es desconocido: una lista enlazada, porque solo cambian los punteros y nada se desplaza.
- Nombra la estructura, nombra su regla, vincula la regla a la situación.
Match each ADT to its rule and a typical use. · Empareja cada ADT con su regla y un uso típico.
Stack = last-in-first-out; queue = first-in-first-out; a linked list chains nodes with pointers. · Pila = último-en-entrar-primer-salir; cola = primero-en-entrar-primer-salir; una lista enlazada encadena nodos con punteros.
Print jobs must be printed in the order they were sent. Which ADT, and why? · Los trabajos de impresión deben imprimirse en el orden en que fueron enviados. ¿Qué ADT y por qué?
Order of arrival is the FIFO rule. A stack would print the most recent job first. · El orden de llegada sigue la regla FIFO. Una pila imprimiría el trabajo más reciente primero.
ADT versus implementation
- The ADT is the behaviour: push and pop, enqueue and dequeue, insert and traverse.
- The implementation is the storage: in this course, an array plus a few pointer variables (next lesson).
- A question about the ADT wants operations and rules; a question about implementation wants arrays, pointers and the checks.
TDA versus implementación
- El TDA es el comportamiento: push y pop, enqueue y dequeue, insertar y recorrer.
- La implementación es el almacenamiento: en este curso, un array más unas pocas variables de puntero (siguiente lección).
- Una pregunta sobre el TDA busca operaciones y reglas; una pregunta sobre la implementación busca arrays, punteros y las comprobaciones.
Marks that slip away
- Push and enqueue test for full first; pop and dequeue test for empty first. Write the check into the description.
- Inserting into a linked list: set the new node's pointer before changing the previous node's, or the rest of the list is lost.
- A stack changes at one end, a queue at both. "Remove from the top of the queue" is a stack answer.
- Expand the abbreviations once: LIFO, last in first out; FIFO, first in first out.
Marcas que se pierden
- Push y enqueue comprueban primero si está llena; pop y dequeue comprueban primero si está vacía. Escribe la comprobación en la descripción.
- Insertar en una lista enlazada: establece el puntero del nodo nuevo antes de cambiar el del nodo anterior, o se pierde el resto de la lista.
- Una pila cambia en un extremo, una cola en ambos. "Eliminar del tope de la cola" es una respuesta de pila.
- Desarrolla las abreviaturas una vez: LIFO, último en entrar primero en salir; FIFO, primero en entrar primero en salir.
You've got it
- an ADT is a collection of data together with a set of operations on it; behaviour, not storage
- stack: add and remove at the top, LIFO, push and pop · queue: add at the rear, remove at the front, FIFO, enqueue and dequeue
- linked list: nodes of value + pointer from a head pointer; cheap insert and delete, slow random access; traverse by following pointers
- justify by rule: order of arrival → queue; most recent first → stack; frequent insertion in the middle → linked list
Lo has logrado
- un TDA es una colección de datos junto con un conjunto de operaciones sobre ellos; comportamiento, no almacenamiento
- pila: añadir y eliminar en el tope, LIFO, push y pop · cola: añadir en la parte trasera, eliminar en el frente, FIFO, enqueue y dequeue
- lista enlazada: nodos de valor + puntero desde un puntero de cabeza; inserción y eliminación baratas, acceso aleatorio lento; recorrer siguiendo punteros
- justifica por regla: orden de llegada → cola; más reciente primero → pila; inserción frecuente en el medio → lista enlazada