Stacks and queues (array-backed) · Pilas y colas (respaldadas por array)
Two ways to hold items
- A stack and a queue both hold a line of items, but they differ in which item comes out next.
- A stack is LIFO: Last In, First Out — like a pile of plates.
- A queue is FIFO: First In, First Out — like a line of people.
Dos formas de almacenar elementos
- Una pila y una cola almacenan ambas una secuencia de elementos, pero difieren en cuál elemento sale el siguiente.
- Una pila es LIFO: Último en entrar, primero en salir — como una pila de platos.
- Una cola es FIFO: Primero en entrar, primero en salir — como una fila de personas.
A stack is LIFO
- push adds an item on top. pop removes and returns the top item. peek looks at the top without removing it.
- The last item you pushed is the first one you pop.
- We store the items in an array
dataand an indextopthat counts how many are in.
Una pila es LIFO
- push añade un elemento en la parte superior. pop elimina y devuelve el elemento superior. peek mira el elemento superior sin eliminarlo.
- El último elemento que empujaste es el primero que extraes.
- Almacenamos los elementos en un array
datay un índicetopque cuenta cuántos hay dentro.
Array-backed stack
- With
topas the count, the top item is atdata[top - 1]. - push: write at
data[top], thentop++. pop:top--, then returndata[top]. - (For these tasks the array is big enough; you do not need to check for "full".)
Pila respaldada por array
- Con
topcomo contador, el elemento superior está endata[top - 1]. - push: escribe en
data[top], luegotop++. pop:top--, luego devuelvedata[top]. - (Para estas tareas el array es lo suficientemente grande; no necesitas verificar si está "lleno".)
A queue is FIFO
- enqueue adds an item at the back. dequeue removes and returns the item at the front.
- The first item you enqueue is the first one you dequeue.
- We keep two indexes:
front(next to leave) andback(next free slot).
Una cola es FIFO
- enqueue añade un elemento al final. dequeue elimina y devuelve el elemento en el inicio.
- El primer elemento que introduces es el primero que sacas.
- Mantenemos dos índices:
front(el próximo en salir) yback(la próxima ranura libre).
Array-backed queue
- enqueue: write at
data[back], thenback++. dequeue: readdata[front], thenfront++, and return it. frontchasesbackas items come and go.- (For these tasks the array is big enough; you do not need to wrap around or check for "empty".)
Cola respaldada por array
- enqueue: escribe en
data[back], luegoback++. dequeue: leedata[front], luegofront++, y lo devuelve. frontpersigue abackconforme entran y salen elementos.- (Para estas tareas el array es lo suficientemente grande; no necesitas hacer un bucle o verificar si está "vacía".)
Common mistakes
- A stack is last-in-first-out; a queue is first-in-first-out.
- Check the structure is not empty before you pop or dequeue.
Errores comunes
- Una pila es último-en-entrar-primer-salir; una cola es primero-en-entrar-primer-salir.
- Verifica que la estructura no esté vacía antes de hacer pop o dequeue.
Now you try
- The
StackandQueuestructs are given in the starter. Uses->top,q->front, andq->back. - Do not write a
main— the checker provides one.
Ahora practica
- Las estructuras
StackyQueuese proporcionan en el código inicial. Usas->top,q->frontyq->back. - No escribas un
main— el validador proporciona uno.
Stacks and queues · Pilas y colas
A stack is LIFO; a queue is FIFO. Step through the operations. · Una pila es LIFO; una cola es FIFO. Recorra las operaciones.
The · El Stack struct (with data and a count top) is given. Complete void push(Stack *s, int v) and · y int pop(Stack *s) so the stack is LIFO. Do not · no write a main. · Se da la estructura Stack (con data y un contador top). Complete void push(Stack *s, int v) e int pop(Stack *s) para que la pila sea LIFO. No escriba un main.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
The · El Stack struct is given. Complete int peek(const Stack *s) so it returns the top item without removing it. Assume the stack is not empty. Do not · no write a main. · Se da la estructura Stack. Complete int peek(const Stack *s) para que devuelva el elemento superior sin eliminarlo. Asumir que la pila no está vacía. No escriba un main.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
The · El Queue struct (with data, front, and back) is given. Complete void enqueue(Queue *q, int v) and · y int dequeue(Queue *q) so the queue is FIFO. Do not · no write a main. · Se da la estructura Queue (con data, front y back). Complete void enqueue(Queue *q, int v) e int dequeue(Queue *q) para que la cola sea FIFO. No escriba un main.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.