Mejor respuesta
En informática , un tipo de datos abstracto ( ADT ) es un modelo matemático para tipos de datos donde un tipo de datos se define por su comportamiento ( semántica ) desde el punto de vista de un usuario de los datos, específicamente en términos de posibles valores, posibles operaciones sobre datos de este tipo y el comportamiento de estas operaciones. Esto contrasta con las estructuras de datos , que son representaciones concretas de datos y son el punto de vista de un implementador, no de un usuario.
De Estructura de datos :
En informática , una estructura de datos es una forma particular de organizar datos en una computadora para que se puedan usar eficientemente .
Las estructuras de datos pueden implementar uno o más tipos de datos abstractos particulares (ADT), que son los medios para especificar el contrato de operaciones y su complejidad
Una estructura de datos es una implementación concreta del contrato proporcionada por un ADT
Lo que eso significa es:
1. ADT es una representación abstracta , desde el punto de vista del usuario
2. DS es una representación concreta, no desde el punto de vista del usuario
En términos simples:
1. Stack es ADT , solo especifica que debe haber un push, pop, etc. para que lo use el usuario.
2. Stack (como otros ADT como Queue) se implementa con DS como matriz o lista (lista vinculada, etc.)
Resumen:
La pila no es DS, es ADT y se implementa mediante otros DS.
Espero haberlo ayudado.
Mucha suerte
Respuesta
Pilas
Una pila es un contenedor de objetos que se insertan y eliminan de acuerdo con el principio de último en entrar, primero en salir (LIFO). En las pilas de pushdown solo se permiten dos operaciones: empujar el elemento en la pila y pop el artículo fuera de la pila. Una pila es una estructura de datos de acceso limitado: los elementos se pueden agregar y quitar de la pila solo en la parte superior. push agrega un elemento a la parte superior de la pila, pop elimina el elemento de la parte superior . Una analogía útil es pensar en una pila de libros; puede eliminar solo el libro superior, también puede agregar un libro nuevo en la parte superior.
Una pila es una estructura de datos recursiva . A continuación, se muestra una definición estructural de una pila:
Aplicaciones
- La aplicación más simple de una pila es invertir una palabra. Usted empuja una palabra determinada para que se apile, letra por letra, y luego saca letras de la pila.
- Otra aplicación es un mecanismo de «deshacer» en los editores de texto; esta operación se logra manteniendo todos los cambios de texto en una pila. Retroceso . Este es un proceso en el que necesita acceder al elemento de datos más reciente en una serie de elementos. Piense en un laberinto o laberinto: ¿cómo encuentra el camino de una entrada a una salida? Una vez que llega a un callejón sin salida, debe retroceder. ¿Pero retroceder hacia dónde? al punto de elección anterior. Por lo tanto, en cada punto de elección almacena en una pila todas las opciones posibles. Luego, retroceder simplemente significa sacar una siguiente opción de la pila.
- Procesamiento del lenguaje: el espacio para los parámetros y las variables locales se crea internamente usando una pila. La verificación de sintaxis del compilador para las llaves coincidentes se implementa mediante stack.support para recursividad
Implementación
En la biblioteca estándar de clases, la pila de tipos de datos es una adapter clase, lo que significa que una pila se construye sobre otras estructuras de datos. La estructura subyacente de una pila podría ser una matriz, un vector, una ArrayList, una lista enlazada, o cualquier otra colección Independientemente del tipo de estructura de datos subyacente, una pila debe implementar la misma funcionalidad.Esto se logra proporcionando una interfaz única:
public interface StackInterface
{
public void push(AnyType e);
public AnyType pop();
public AnyType peek();
public boolean isEmpty();
}
El La siguiente imagen demuestra la idea de implementación por composición .
Otro requisito de implementación (además de la interfaz anterior) es que todas las operaciones de la pila deben ejecutarse en
tiempo constante O (1)
. El tiempo constante significa que hay una constante k tal que una operación toma k nanosegundos de tiempo computacional independientemente del tamaño de la pila.
Implementación basada en matrices
En una implementación basada en arreglos, mantenemos los siguientes campos: un arreglo A de un tamaño predeterminado (≥ 1 ), la variable top que se refiere al elemento superior de la pila y la capacidad que se refiere al tamaño de la matriz. La variable top cambia de -1 a capacity - 1. Decimos que una pila está vacía cuando top = -1, y que la pila está llena cuando top = capacity-1.
En un -tamaño de la pila de abstracción, la capacidad permanece sin cambios, por lo tanto, cuando top alcanza la capacidad , la pila el objeto lanza una excepción.
En una abstracción de pila dinámica cuando top alcanza la capacidad , duplicamos el tamaño de la pila.
Implementación basada en listas enlazadas
Basadas en listas enlazadas La implementación proporciona la mejor implementación de pila dinámica (desde el punto de vista de la eficiencia).
Fuente – Pilas y colas