La pila: todo pasa por el tope
Una pila es una lista con un solo extremo abierto: el tope. push apila en el tope y pop saca del tope. Al empezar, tope es null.
Una pila es una lista con un solo extremo abierto: el tope.
push apila en el tope y pop saca del tope. Al empezar, tope es null.
Una pila es una lista con un solo extremo abierto: el tope. push apila en el tope y pop saca del tope. Al empezar, tope es null.
push("A") crea un nodo y lo deja en el tope.
Cada nodo nuevo apunta al tope anterior y pasa a ser el nuevo tope.
No hay bucles: apilar cuesta O(1), haya los nodos que haya.
push("A") crea un nodo y lo deja en el tope. Cada nodo nuevo apunta al tope anterior y pasa a ser el nuevo tope. No hay bucles: apilar cuesta O(1), haya los nodos que haya.
pop() devuelve el dato del tope y baja el tope al siguiente. Sale "C".
Después sale "B": el último en entrar es el primero en salir. Eso es LIFO.
pop() devuelve el dato del tope y baja el tope al siguiente. Sale "C". Después sale "B": el último en entrar es el primero en salir. Eso es LIFO.
Sale "A" y el tope vuelve a null: la pila vacía.
Otro pop() se detiene en la guardia y lanza NoSuchElementException.
Sale "A" y el tope vuelve a null: la pila vacía. Otro pop() se detiene en la guardia y lanza NoSuchElementException.
Una cola abre los dos extremos: se entra por el fondo y se sale por el frente.
Con un solo nodo, frente y fondo apuntan al mismo. enqueue cuesta O(1).
Cada llegada se engancha al fondo, y el fondo avanza hasta ella.
Una cola abre los dos extremos: se entra por el fondo y se sale por el frente. Con un solo nodo, frente y fondo apuntan al mismo. enqueue cuesta O(1). Cada llegada se engancha al fondo, y el fondo avanza hasta ella.
dequeue() saca por el frente: primero "A", después "B". Es el orden de llegada.
Los nodos no se corren: solo avanza el frente. FIFO, también en O(1).
dequeue() saca por el frente: primero "A", después "B". Es el orden de llegada. Los nodos no se corren: solo avanza el frente. FIFO, también en O(1).
Sale "C" y el frente queda en null.
Pero el fondo sigue apuntando a un nodo que ya no pertenece a la cola.
Por eso, si el frente queda en null, también fondo = null.
Sale "C" y el frente queda en null. Pero el fondo sigue apuntando a un nodo que ya no pertenece a la cola. Por eso, si el frente queda en null, también fondo = null.
La pila invierte el orden: sirve para deshacer o para la pila de llamadas.
La cola respeta el orden de llegada: la cola de impresión, los turnos.
Solo tocan sus extremos, así que todas sus operaciones cuestan O(1).
La pila invierte el orden: sirve para deshacer o para la pila de llamadas. La cola respeta el orden de llegada: la cola de impresión, los turnos. Solo tocan sus extremos, así que todas sus operaciones cuestan O(1).