Estructura de datos: utilice una lista enlazada circular con encabezado para representar el problema de la cola

Descripción del problema:

Representa una cola como una lista enlazada de anillo principal (se supone que tiene la longitud de la cola es N)

Si solo se establece el puntero principal, ¿cuál es la complejidad temporal de quitar y poner en cola?

Si solo se establece el puntero de cola, ¿cuál es la complejidad temporal de quitar y poner en cola?

Mi respuesta:

Si solo se establece el puntero principal, entonces la cola de salida es O(1); la cola de entrada es O(N)

Si solo se establece el puntero de cola, entonces la cola de salida es O(1); la cola de entrada es O(1)

¿Verdad?

Respuesta:

Requisito previo: los nodos de la cola se insertan desde el final de la cola y se eliminan desde el principio de la cola; los nodos de la cola apuntan desde el principio de la cola; la cola al final de la cola porque es una lista circular enlazada, entonces el nodo al lado del nodo final es el encabezado de la cola.

Si solo está el puntero principal, es fácil salir de la cola, simplemente mueva el puntero principal hacia atrás uno en uno, si desea ingresar a la cola, debe atravesar toda la cola, determine; al final de la cola, y luego inserte, por lo que el tiempo para salir de la cola es O (1) y el tiempo para ingresar a la cola es O (n)

Si solo existe la cola puntero, ingrese a la cola directamente y solo necesita mover un nodo hacia atrás para salir de la cola. Encontrar el encabezado de la cola lleva el mismo tiempo, que es O (1).

En términos generales, una cola circular no necesita un puntero principal, solo un puntero al nodo final de la cola. Es muy fácil determinar el principio y el final de la cola.