Share
Hasta ahora hemos examinado colecciones que proporcionan almacenamiento de datos muy básico, esencialmente abstracciones en una matriz. En esta sección, veremos qué sucede cuando agregamos algunos comportamientos muy básicos que cambian por completo la utilidad de las colecciones..
Una pila es una colección que devuelve objetos a la persona que llama en un patrón de último en entrar, primero en salir (LIFO). Lo que esto significa es que el último objeto agregado a la colección será el primer objeto devuelto.
Las pilas se diferencian de las colecciones de listas y de tipo matriz. No se pueden indexar directamente, los objetos se agregan y eliminan mediante diferentes métodos, y sus contenidos son más opacos que las listas y matrices. Lo que quiero decir con esto es que mientras una colección basada en listas proporciona un método Contains, una pila no lo hace. Además, una pila no es enumerable. Para entender por qué es esto, veamos qué es una pila y cómo el uso de una pila impulsa estas diferencias.
Una de las analogías más comunes para una pila es la pila de platos de restaurante. Este es un dispositivo simple cargado por resorte sobre el cual se apilan las placas limpias. El resorte asegura que, independientemente de cuántas placas haya en la pila, se puede acceder fácilmente a la placa superior. Las placas limpias se agregan a la parte superior de la pila, y cuando un cliente retira una placa, él o ella está retirando la placa superior (la placa que se agregó más recientemente).
Comenzamos con un plato vacío..
Una pila de platos vacíos (el resorte no sostiene platos) Y luego agregamos una placa roja, azul y verde al estante en ese orden.
El punto clave a comprender aquí es que a medida que se agregan nuevas placas, éstas se agregan a la parte superior de la pila. Si un cliente recupera una placa, él o ella obtendrá la placa más recientemente agregada (la placa verde). El siguiente cliente obtendría la placa azul y, finalmente, la placa roja se eliminaría..
Ahora que entendemos cómo funciona una pila, definamos algunos términos nuevos. Cuando se agrega un elemento a la pila, se "empuja" al usar el empujar método. Cuando un elemento se elimina de la pila, se "quita" usando el Popular método. El elemento superior de la pila, el más recientemente agregado, se puede "echar un vistazo" al usar el Ojeada método. Peeking le permite ver el elemento sin quitarlo de la pila (al igual que el cliente en el estante de la placa podría ver el color de la placa superior). Con estos términos en mente, veamos la implementación de un Apilar clase.
los Apilar clase define empujar, Popular, y Ojeada métodos, un Contar propiedad, y utiliza el Lista enlazada Clase para almacenar los valores contenidos en la pila..
pila de clase pública LinkedList _items = new LinkedList (); public void Push (valor de T) lanzar una nueva NotImplementedException (); public T Pop () lanza la nueva NotImplementedException (); public T Peek () lanza la nueva NotImplementedException (); public int Count get;
| Comportamiento | Agrega un elemento a la parte superior de la pila. |
| Actuación | O (1) |
Ya que estamos usando una lista vinculada como nuestra tienda de respaldo, todo lo que tenemos que hacer es agregar el nuevo elemento al final de la lista..
public void Push (valor de T) _items.AddLast (valor);
| Comportamiento | Elimina y devuelve el último elemento agregado a la pila. Si la pila está vacía, un InvalidOperationException es aventado. |
| Actuación | O (1) |
empujar agrega elementos a la parte posterior de la lista, por lo que los "saltamos" desde la parte posterior. Si la lista está vacía, se lanza una excepción..
Accentsconagua
public T Pop () if (_items.Count == 0) lanza una nueva excepción InvalidOperationException ("La pila está vacía"); T result = _items.Tail.Value; _items.RemoveLast (); resultado de retorno | Comportamiento | Devuelve el último elemento agregado a la pila, pero deja el elemento en la pila. Si la pila está vacía, un InvalidOperationException es aventado. |
| Actuación | O (1) |
público T Peek () if (_items.Count == 0) lanza una nueva excepción InvalidOperationException ("La pila está vacía"); return _items.Tail.Value; | Comportamiento | Devuelve el número de elementos en la pila.. |
| Actuación | O (1) |
Dado que se supone que la pila es una estructura de datos opaca, ¿por qué tenemos una Contar ¿propiedad? Sabiendo si una pila está vacía (Cuenta == 0) es muy útil, sobre todo porque Popular lanza una excepción cuando la pila está vacía.
public int Count get return _items.Count;
El ejemplo clásico de pila es la calculadora de notación polaca inversa (RPN).
La sintaxis de RPN es bastante simple. Usa:
En lugar de lo tradicional:
En otras palabras, en lugar de decir "4 + 2", diríamos "4 2 +". Si desea comprender el significado histórico de la sintaxis de RPN, lo aliento a que visite la Wikipedia o su motor de búsqueda favorito..
La forma en que se evalúa el RPN y la razón por la cual una pila es tan útil cuando se implementa una calculadora RPN se puede ver en el siguiente algoritmo:
para cada valor de entrada, si el valor es un entero, presione el valor en la pila de operandos, si el valor es un operador, haga clic en los valores de izquierda y derecha de la pila y evalúe al operador presionando el resultado en la respuesta de pila de la pila.
Entonces, dada la cadena de entrada "4 2 +", las operaciones serían:
push (4) push (2) push (pop () + pop ())
Ahora la pila contiene un solo valor: seis (la respuesta).
La siguiente es una implementación completa de una calculadora simple que lee una ecuación (por ejemplo, "4 2 +") de la entrada de la consola, divide la entrada en cada espacio (["4", "2" y "+"]) , y realiza el algoritmo RPN en la entrada. El bucle continúa hasta que la entrada es la palabra "salir".
void RpnLoop () while (true) Console.Write (">"); entrada de cadena = Console.ReadLine (); if (input.Trim (). ToLower () == "quit") break; // La pila de enteros aún no operados. Valores de pila = pila nueva (); foreach (token de cadena en input.Split (new char [] ")) // Si el valor es un entero ... int value; if (int.TryParse (token, out value)) // ... push to la pila. values.Push (value); else // De lo contrario, evalúe la expresión ... int rhs = values.Pop (); int lhs = values.Pop (); // ... y devuelva el resultado a la pila. switch (token) caso "+": valores.Push (lhs + rhs); break; caso "-": valores.Push (lhs - rhs); break; caso "*": valores.Push (lhs * rhs) ; break; case "/": values.Push (lhs / rhs); break; case "%": values.Push (lhs% rhs); break; default: throw new ArgumentException (string.Format ("Token no reconocido: 0 ", ficha)); // El último elemento en la pila es el resultado. Console.WriteLine (values.Pop ()); Las colas son muy similares a las pilas: proporcionan una colección opaca a partir de la cual se pueden agregar (poner en cola) o eliminar (sacar en cola) los objetos de una manera que agrega valor a una colección basada en listas.
Las colas son una colección de primero en entrar, primero en salir (FIFO). Esto significa que los elementos se eliminan de la cola en el mismo orden en que se agregaron. Puede pensar en una cola como en una fila en un mostrador de caja. La gente ingresa a la línea y recibe el servicio en el orden en que llega..
Las colas se usan comúnmente en las aplicaciones para proporcionar un búfer para agregar elementos para el procesamiento futuro o para proporcionar acceso ordenado a un recurso compartido. Por ejemplo, si una base de datos es capaz de manejar solo una conexión, se puede usar una cola para permitir que los hilos esperen su turno (en orden) para acceder a la base de datos.
los Cola, como el Apilar, está respaldado por un Lista enlazada. Adicionalmente, proporciona los métodos. Encolar (para agregar artículos), Dequeue (para eliminar elementos), Ojeada, y Contar. Me gusta Apilar, no se tratará como una recopilación de propósito general, lo que significa que no se implementará ICollection.
cola de clase pública LinkedList _items = new LinkedList (); Public void Enqueue (valor T) lanzar una nueva NotImplementedException (); public T Dequeue () lanza la nueva NotImplementedException (); public T Peek () lanza la nueva NotImplementedException (); public int Count get;
| Comportamiento | Agrega un elemento al final de la cola. |
| Actuación | O (1) |
Esta implementación agrega el elemento al inicio de la lista enlazada. El elemento podría agregarse fácilmente al final de la lista. Todo lo que realmente importa es que los elementos se pongan en cola en un extremo de la lista y se eliminen de la cola (FIFO). Observe que esto es lo opuesto a la clase de Pila, donde los elementos se agregan y eliminan del mismo extremo (LIFO).
Public void Enqueue (valor T) _items.AddFirst (value);
| Comportamiento | Elimina y devuelve el elemento más antiguo de la cola. Un InvalidOperationException se arroja si la cola está vacía. |
| Actuación | O (1) |
Ya que Encolar añadido el elemento al inicio de la lista, Dequeue Debe eliminar el elemento al final de la lista. Si la cola no contiene elementos, se lanza una excepción.
pública T Dequeue () if (_items.Count == 0) lanza una nueva excepción InvalidOperationException ("La cola está vacía"); T last = _items.Tail.Value; _items.RemoveLast (); regreso último | Comportamiento | Devuelve el siguiente elemento que se devolvería si se llamara a Dequeue. La cola se deja sin cambios. Se lanza una InvalidOperationException si la cola está vacía. |
| Actuación | O (1) |
público T Peek () if (_items.Count == 0) lanza la nueva excepción InvalidOperationException ("La cola está vacía"); return _items.Tail.Value; | Comportamiento | Devuelve el número de elementos actualmente en la cola. Devuelve 0 si la cola está vacía. |
| Actuación | O (1) |
public int Count get return _items.Count;
Una cola doble, o deque, extiende el comportamiento de la cola al permitir que los elementos se agreguen o eliminen de ambos lados de la cola. Este nuevo comportamiento es útil en varios dominios problemáticos, específicamente la programación de tareas y subprocesos. También es generalmente útil para implementar otras estructuras de datos. Veremos un ejemplo de cómo usar un deque para implementar otra estructura de datos más adelante..
los Deque La clase está respaldada por una lista doblemente enlazada. Esto nos permite agregar y eliminar elementos de la parte frontal o posterior de la lista y acceder a la primero y Último propiedades Los principales cambios entre la clase Queue y la clase Deque son que Encolar, Dequeue, y Ojeada los métodos se han duplicado en primero y Último variantes.
clase pública Deque LinkedList _items = new LinkedList (); public void EnqueueFirst (valor T) lanzar una nueva NotImplementedException (); public void EnqueueLast (valor de T) lanzar una nueva NotImplementedException (); public T DequeueFirst () lanza la nueva NotImplementedException (); public T DequeueLast () lanza la nueva NotImplementedException (); public T PeekFirst () lanza la nueva NotImplementedException (); public T PeekLast () lanza la nueva NotImplementedException (); public int Count get;
| Comportamiento | Agrega el valor proporcionado a la cabecera de la cola. Este será el próximo elemento en cola de DequeueFirst. |
| Actuación | O (1) |
public void EnqueueFirst (valor de T) _items.AddFirst (valor);
| Comportamiento | Agrega el valor proporcionado a la cola de la cola. Este será el siguiente elemento eliminado por DequeueLast. |
| Actuación | O (1) |
public void EnqueueLast (valor T) _items.AddLast (valor);
| Comportamiento | Elimina y devuelve el primer elemento en el deque. Se lanza una InvalidOperationException si el deque está vacío. |
| Actuación | O (1) |
public T DequeueFirst () if (_items.Count == 0) lanza la nueva excepción InvalidOperationException ("DequeueFirst se llama cuando deque está vacío"); T temp = _items.Head.Value; _items.RemoveFirst (); temperatura de retorno | Comportamiento | Elimina y devuelve el último elemento en el deque. Se lanza una InvalidOperationException si el deque está vacío. |
| Actuación | O (1) |
public T DequeueLast () if (_items.Count == 0) lanza la nueva excepción InvalidOperationException ("DequeueLast se llama cuando deque está vacío"); T temp = _items.Tail.Value; _items.RemoveLast (); temperatura de retorno | Comportamiento | Devuelve el primer elemento en el deque pero deja la colección sin cambios. Se lanza una InvalidOperationException si el deque está vacío. |
| Actuación | O (1) |
public T PeekFirst () if (_items.Count == 0) lanza la nueva excepción InvalidOperationException ("PeekFirst se llama cuando deque está vacío"); return _items.Head.Value; | Comportamiento | Devuelve el último elemento en el deque pero deja la colección sin cambios. Se lanza una InvalidOperationException si el deque está vacío. |
| Actuación | O (1) |
public T PeekLast () if (_items.Count == 0) lanza la nueva excepción InvalidOperationException ("PeekLast se llama cuando el deque está vacío"); return _items.Tail.Value; | Comportamiento | Devuelve el número de elementos actualmente en el deque, o 0 si el deque está vacío. |
| Actuación | O (1) |
public int Count get return _items.Count;
Los deques se utilizan a menudo para implementar otras estructuras de datos..
Hemos visto una pila implementada usando un Lista enlazada, Así que ahora vamos a ver uno implementado utilizando una Deque.
Usted podría preguntarse por qué elegiría implementar un Apilar usando un Deque preferible a Lista enlazada. El motivo es uno de rendimiento y reutilización de código. Una lista vinculada tiene el costo de la sobrecarga por nodo y la reducida localidad de datos: los elementos se asignan en el montón y es posible que las ubicaciones de la memoria no estén cerca unas de otras, lo que provoca un mayor número de fallas de caché y fallos de página en la CPU y el hardware de memoria niveles Una implementación de una cola con mejor rendimiento podría utilizar una matriz como almacén de respaldo en lugar de una lista. Esto permitiría una menor sobrecarga por nodo y podría mejorar el rendimiento al abordar algunos problemas de localidad.
Implementando un Apilar o Cola Sin embargo, como una matriz es una implementación más compleja. Al implementar el Deque De esta manera más compleja y al utilizarla como base para otras estructuras de datos, podemos obtener los beneficios de rendimiento para todas las estructuras y solo tenemos que escribir el código una vez. Esto acelera el tiempo de desarrollo y reduce los costos de mantenimiento..
Veremos un ejemplo de una Deque como una matriz más adelante en esta sección, pero primero veamos un ejemplo de una Apilar implementado usando un Deque.
Pila de clase pública Deque _items = new Deque (); public void Push (valor de T) _items.EnqueueFirst (valor); public T Pop () return _items.DequeueFirst (); public T Peek () return _items.PeekFirst (); public int Count get return _items.Count;
Tenga en cuenta que todas las comprobaciones de errores ahora están aplazadas a Deque y cualquier optimización o corrección de errores hecha a la Deque se aplicará automáticamente a la Apilar clase. Implementando un Cola Es tan fácil y, como tal, se deja como un ejercicio para el lector..
Como se mencionó anteriormente, hay ventajas de usar una matriz en lugar de una lista vinculada como almacén de respaldo para el Deque (un deque de enteros). Conceptualmente, esto parece simple, pero en realidad hay varias cuestiones que deben abordarse para que esto funcione..
Veamos algunos de estos problemas gráficamente y luego veamos cómo podemos resolverlos. En el camino, tenga en cuenta los problemas de política de crecimiento que se discutieron en la sección ArrayList y que esos mismos problemas se aplican aquí.
Cuando se crea la colección, es una matriz de 0 longitud. Veamos cómo algunas acciones afectan la matriz interna. A medida que pasamos por esto, observe que la "h" verde y la "t" roja en las figuras se refieren a "cabeza" y "cola", respectivamente. La cabecera y la cola son los índices de matriz que indican los primeros y últimos elementos de la cola. A medida que agreguemos y eliminemos elementos, la interacción entre la cabeza y la cola será más clara..
Deque deq = nuevo Deque (); deq.EnqueueFirst (1);
Añadiendo un valor al frente del deque. deq.EnqueueLast (2);
Añadiendo un valor al final del deque. deq.EnqueueFirst (0);
Añadiendo otro valor al frente del deque; el índice de la cabeza se envuelve alrededor Note lo que ha sucedido en este punto. El índice de cabeza se ha envuelto alrededor del final de la matriz. Ahora el primer artículo en el deque, lo que sería devuelto por DequeueFirst, es el valor en el índice de matriz tres (cero).
deq.EnqueueLast (3);
Añadiendo un valor al final del deque. En este punto, la matriz está llena. Cuando se agrega otro elemento, ocurrirá lo siguiente:
EnqueueFirst - El elemento se agrega en el índice cero (la operación de copia deja este abierto).EnqueueLast - El elemento se agrega al final de la matriz. deq.EnqueueLast (4);
Agregando un valor al final del deque expandido Ahora veamos qué sucede cuando los elementos se eliminan de Deque..
deq.DequeueFirst ();
Eliminando el primer elemento del deque expandido deq.DequeueLast ();
Eliminando el último elemento del deque expandido El punto crítico a tener en cuenta es que, independientemente de la capacidad de la matriz interna, los contenidos lógicos de Deque son los elementos del índice de cabecera al índice de cola, teniendo en cuenta la necesidad de envolver al final de la matriz. Una matriz que proporciona el comportamiento de envolver alrededor de la cabeza a la cola a menudo se conoce como un búfer circular.
Con esta comprensión de cómo funciona la lógica de matriz, sumergámonos directamente en el código.
Los métodos y las propiedades de Deque basados en matrices son los mismos que los basados en listas, por lo que no se repetirán aquí. Sin embargo, la lista se ha reemplazado con una matriz y ahora hay tres propiedades para contener la información de tamaño, cabecera y cola.
clase pública Deque T [] _items = new T [0]; // El número de elementos en la cola. int _size = 0; // El índice del primer elemento (el más antiguo) en la cola. int _head = 0; // El índice del último elemento (el más nuevo) en la cola. int _tail = -1;…
Cuando la matriz interna necesita crecer, el algoritmo para aumentar el tamaño de la matriz, copiar el contenido de la matriz y actualizar los valores del índice interno debe ejecutarse. los Encolar método realiza esa operación y es llamado por ambos EnqueueFirst y EnqueueLast. los StartingIndex Este parámetro se utiliza para determinar si se debe dejar abierta la ranura de matriz en el índice cero (en el caso de EnqueueFirst).
Preste especial atención a cómo se desenvuelven los datos en los casos en que la caminata de la cabeza a la cola requiere volver al final de la matriz a cero.
private void allocateNewArray (int startingIndex) int newLength = (_size == 0)? 4: _size * 2; T [] newArray = new T [newLength]; if (_size> 0) int targetIndex = startingIndex; // Copie el contenido ... // Si la matriz no tiene envoltura, simplemente copie el rango válido. // Si no, copie desde la cabeza hasta el final de la matriz y luego desde 0 hasta la cola. // Si la cola es menor que la cabeza, hemos envuelto. si < _head) // Copy the _items[head]… _items[end] -> newArray [0]… newArray [N]. para (int index = _head; index < _items.Length; index++) newArray[targetIndex] = _items[index]; targetIndex++; // Copy _items[0]… _items[tail] -> newArray [N + 1]… para (índice int = 0; índice <= _tail; index++) newArray[targetIndex] = _items[index]; targetIndex++; else // Copy the _items[head]… _items[tail] -> newArray [0]… newArray [N] para (int index = _head; index <= _tail; index++) newArray[targetIndex] = _items[index]; targetIndex++; _head = startingIndex; _tail = targetIndex - 1; // Compensate for the extra bump. else // Nothing in the array. _head = 0; _tail = -1; _items = newArray;
| Comportamiento | Agrega el valor proporcionado a la cabecera de la cola. Este será el próximo elemento en cola de DequeueFirst. |
| Actuación | O (1) en la mayoría de los casos; O (n) cuando el crecimiento es necesario. |
public void EnqueueFirst (elemento T) // Si la matriz necesita crecer. if (_items.Length == _size) allocateNewArray (1); // Como sabemos que la matriz no está llena y _head es mayor que 0, // sabemos que la ranura en frente de la cabeza está abierta. if (_head> 0) _head--; else // De lo contrario, tenemos que envolver al final de la matriz. _head = _items.Length - 1; _items [_head] = item; _size ++;
| Comportamiento | Agrega el valor proporcionado a la cola de la cola. Este será el siguiente elemento eliminado por DequeueLast. |
| Actuación | O (1) en la mayoría de los casos; O (n) cuando el crecimiento es necesario. |
public void EnqueueLast (elemento T) // Si la matriz necesita crecer. if (_items.Length == _size) allocateNewArray (0); // Ahora tenemos una matriz de tamaño adecuado y podemos centrarnos en resolver problemas. // Si _tail está al final de la matriz, tenemos que envolverlo. if (_tail == _items.Length - 1) _tail = 0; else _tail ++; _items [_tail] = item; _size ++;
| Comportamiento | Elimina y devuelve el primer elemento en el deque. Se lanza una InvalidOperationException si el deque está vacío. |
| Actuación | O (1) |
public T DequeueFirst () if (_size == 0) lanza la nueva excepción InvalidOperationException ("El deque está vacío"); Valor de T = _items [_head]; if (_head == _items.Length - 1) // Si la cabeza está en el último índice de la matriz, envuélvala. _head = 0; else // Mover a la siguiente ranura. _head ++; _tamaño--; valor de retorno; | Comportamiento | Elimina y devuelve el último elemento en el deque. Se lanza una InvalidOperationException si el deque está vacío. |
| Actuación | O (1) |
public T DequeueLast () if (_size == 0) lanza la nueva excepción InvalidOperationException ("El deque está vacío"); Valor de T = _items [_tail]; if (_tail == 0) // Si la cola está en el primer índice de la matriz, envuélvala. _tail = _items.Length - 1; else // Mueve a la ranura anterior. _cola--; _tamaño--; valor de retorno; | Comportamiento | Devuelve el primer elemento en el deque pero deja la colección sin cambios. Un InvalidOperationException Se lanza si el deque está vacío.. |
| Actuación | O (1) |
public T PeekFirst () if (_size == 0) lanza la nueva excepción InvalidOperationException ("El deque está vacío"); return _items [_head]; | Comportamiento | Devuelve el último elemento en el deque pero deja la colección sin cambios. Un InvalidOperationException Se lanza si el deque está vacío.. |
| Actuación | O (1) |
public T PeekLast () if (_size == 0) lanza la nueva excepción InvalidOperationException ("El deque está vacío"); return _items [_tail]; | Comportamiento | Devuelve el número de elementos actualmente en el deque o 0 si el deque está vacío. |
| Actuación | O (1) |
public int Count get return _size;
