Tipos Abstractos de Datos: Listas, Pilas y Colas

Clase 13 de 42 • Curso Práctico de Estructuras de Datos y Algoritmos

En esta lectura de referencia encontrarás la definición de los 3 Abstract Data Types más utilizados: listas ADT, Stack o Pila ADT y Queue o Cola ADT.

La forma general de conocer cada una de estas 3 ADT es a través de sus definiciones y las definiciones sólo mencionan qué operaciones serán implementadas, sin embargo no especifican cómo se organizarán los datos en memoria o cuál algoritmo se utilizará para implementar las operaciones. Estas tres definiciones hacen parte de lo que conocemos como tipos de datos abstractos, porque dan una vista independiente de la implementación. Debido a esto es importante que conozcas los métodos o funcionalidades que podrás encontrar en un ADT.

List ADT

Una lista es un tipo de datos abstracto utilizado para representar un número contable de valores ordenados. El mismo valor puede existir más de una vez, esta es la implementación computacional del concepto matemático de secuencia finita, la lista.

A continuación te comparto las operaciones disponibles en este ADT:

get() – Retorna un elemento de la lista en cualquier posición especificada. insert() – Inserta un elemento en cualquier posición de la lista. remove() – Remueve la primera aparición de cualquier elemento en una lista no-vacía. removeAt() – Remueve el elemento que se encuentre en la posición especificada en una lista que no esté vacía. replace() – Reemplaza un elemento en cualquier posición por otro elemento. size() – Retorna el número de elementos contenidos en la lista. isEmpty() – Retorna true si la lista está vacía, si no, regresa false. isFull() – Retorna true si la lista está llena, si no, regresa false.

Stack ADT

Un Stack es un tipo de datos abstracto que sirve como una colección de elementos con dos operaciones principales: Push: agrega un elemento a la colección Pop remueve el elemento que se añadió más recientemente y que no ha sido removido, el orden en el que esto funciona como hemos visto en clases sigue la lógica LIFO (last in, first out) que en español sería “último o más reciente en entrar, primero en salir”

A continuación te comparto las operaciones disponibles en este ADT:

push() – Inserta un elemento en un extremo de la pila denominado “cima”. pop() – Remueve y retorna el elemento en la cima de la pila, si el stack no está vació. peek() – Retorna el elemento en la cima del stack sin removerlo, si el stack no está vacío. size() – Retorna el número de elementos en el stack. isEmpty() – Retorna true si el stack está vacío, si no, retorna false. isFull() – Retorna true si la lista está llena, si no, regresa false.

Queue ADT

Una cola es un ADT que sirve para almacenar datos en el orden en el que los datos van llegando, sigue una lógica del tipo FIFO o “primero en llegar, primero en salir” como es en la mayoría de supermercados.

A continuación te comparto las operaciones disponibles en este ADT:

enqueue() – Inserta un nuevo elemento al final de la cola. dequeue() – Remueve y retorna el primer elemento de la cola si la cola no está vacía. peek() – Retorna el primer elemento de la cola sin removerlo. size() – Retorna el número de elementos almacenados en la cola. isEmpty() – Retorna true si la cola está vacía, si no, retorna false. isFull() – Retorna true si la cola está vacía, si no, retorna false.

Leisy Karina Algarra Fernandez

student•

Fernanda Vieira Jófili

student•

🤩 Que super aporte!!! Gracias por compartirlo, Karina! Nos ayudará muuucho, es muy visual y simple.

Daniel Ramírez Castaño

student•

Excelente!

Israel Castro

student•

Al final, exactamente en la última línea, parece ser que hay un error:

Queue ADT isFull() – Retorna true si la cola está vacía, si no, retorna false. // Debe decir que retorna true si la cola está llena…

Aaron Joel Limachi Quispe

student•

Es verdad isFull() - Retorna true si la cola está llena, sino retorna false

David Barreto

student•

Exacto bien dicho!

Jose Antonio Rojas Ollarves

student•

ADT Vs. Estructura de datos: Los ADT son estructura de datos creadas por el mismo programador, lo que quiere decir que se basan ya sea en una lista, un diccionario o un stack, pero estaran definidas de otra forma para tener un mejor control y flujo del codigo. En un caso mas claro imaginen tener un proyecto grande donde se trabaja con muchas variables y datos necesitamos crear estructuras de datos para tener un mejor orden y si trabajamos con las formas primitivas seria algo muy confuso de esta forma es en la que salen las ADT. Entonces las ADT realmente son definiciones de las mismas estructuras de datos pero declaradas por los programadores

Willy Florencio Samaniego Chinchay

student•

Pues tu comentario, le da más sentido a todo esto. Muchas gracias!

Alejandro Giraldo Londoño

student•

Estos son algunos que encontré adicionales, habrá que explorar más de este asunto:

Container
List
Set
Multiset
Map
Multimap
Graph
Tree
Stack
Queue
Priority queue
Double-ended queue
Double-ended priority queue

David Barreto

student•

Excelente aporte!

Manuel Alejandro Aguilar Téllez Girón

student•

Entonces se podría entender a la cola (Queue) como la fila de un banco o de un restaurante o cualquier otro, porque los clientes se van formando y atienden al primero que llegó.

La pila (Stack) es como cuando guardabas discos en unas cosas que tenían como un cilindro en medio, sacabas el último que habías metido, si querías sacar uno del medio tenías que sacar un montón y se hacía un desorden.

La lista entiendo que sacas el que quieras de la posición que quieras. Es como cuando checas tus calificaciones en la universidad, buscas tu nombre y revisas, o buscas el de tu amigo y ya, no tienes que estar revisando uno por uno a mucho detalle.

Luis Alfredo Villalta López

student•

Excelente definición,

Luis Alfredo Villalta López

student•

Excelente definición,

José David Garzón

student•

Amigos, para ahondar en la implementación de estas estructuras de datos en javascript.

https://www.youtube.com/watch?v=1AJ4ldcH2t4

Alfredo Martínez García

student•

muchas gracias voy a verlo!

Cristian Blandon

student•

Vale aclarar que, como se mencionó en la clase anterior, Stacks & Queues serían Abstract Data Types, y no estructuras de datos.

Carlos Martin Castillo Jimenez

student•

Hola a todos, me parece que hay un error en el Queue ADT, al ingresar isFull() - debería retornar true si la cola está llena. Ya que como aparece en el resumen, isEmpty y isFull están retornando la misma información.

Josue Granados

student•

Asi es, error de dedo supongo.

Jorge Luis Veliz Berzosa

student•

Quisiera saber mas la utilidad en el dia a dia de estos conceptos

Usuario anónimo

user•

Hola, aqui me vienen a la mente algunos:

Insertar usuarios en una tabla de memoria, para un sitio web donde esta observando el potencial cliente, no insertas en tabla su registro, pues solo es potencial cliente, y usas memoria para tratarlo en la sesión en la que esta operando.
Lo mismo para productos en una tienda online, los agregas al carrito de compras, y antes de efectuar algun CUD(Create, Update, Delete) en la BDD, lo almacenas en memoria; ya cuando el cliente ha efectuado la compra, ahora si haces uso de CUD.

Ricardo Andres Rojas Alonso

student•

Me queda la duda de si en las operaciones disponibles isEmpty () y isFull del ADT de Queue realmente tienen la misma funcionalidad, ya que en el artículo ambas dicen lo siguiente:

isEmpty() – Retorna true si la cola está vacía, si no, retorna false. isFull() – Retorna true si la cola está vacía, si no, retorna false.

Por ende no veo la diferencia, me gustaría saber si "isFull()" lo que realmente hace es (Retornar true si la cola está llena, si no, retorna false)

Agradezco sus comentarios... Saludos!

Juan José Peláez Hernández

student•

Es un error humano. Tu deducción es correcta ! isFull() – Retorna true si la cola está llena, si no, retorna false.

Ricardo Andres Rojas Alonso

student•

Muchas gracias compañero

Henry Gutierrez Mora

student•

Espero ver los ejercicios prácticos, pues la lectura estuvo clara.. hay algunos vacíos .. al momento frente a las anteriores clases esta no me a gustado la dinámica del docente

Cristian Vargas

student•

Si uno se pone a analizar todos estos conceptos se usan a diario en las herramientas que usamos para desarrolar (Arreglos, Git , Objetos)

Karen Paola Diaz Duarte

student•

genial, ahora a la practica. :)

Joshua Raúl Váley Porras

student•

Pequeña observación. En Queue ADT las funciones isEmpty() e isFull() dicen lo mismo. Es así o es un pequeño error?? Saludos :D

Sebastian Alejandro Veliz Ysla

student•

Deberían ser contrárias XD

Edwin Meixueiro Torres

student•

isFull() esta alreves

Joel Vicente Nieto Gómez

student•

Ahora me interesa saber como implementar y entender su esencia de cada ADT.

Daniel Esteban Santos Mendez

student•

Estoy entiendo poco a poco los conceptos pero algo que no entiendo es que lenguaje tiene estos ADT? O nosotros como programadores somos los que tenemos que crearlos y estos son estandares de los métodos para llevar al momento de crear un ADT, si?

Array es un ADT? Según lo que he entendido de todo si por lo métodos que tiene, pero también es una Estructura de Datos? Esto se esta poniendo bien ambigüo jeje.

Y ya como comentario, deberían aclarar que estos no son cosas nativas de los lenguajes, porque Celis habla como si lo fuera y me ha estado confundiendo mucho.

Miguel Torres

student•

Hola, @ElDani.

Dependiendo del lenguaje de programación se incluyen o NO de forma nativa estas ADT. Un gran ejemplo es Python con sus listas y diccionarios. En JS también se incluyen varios de los que Celis menciona aquí. 🤓

Erick Alejandro Carrillo López

student•

Por si tiene duda sobre si python cuenta con un mecanismo de estructuras de datos aquí lo explica muy bien https://recursospython.com/guias-y-manuales/estructuras/

Ivan Ezequiel Mazzalay

student•

Genial! Muchas gracias!!

Enzo Díaz

student•

Más adelante les comparto la implementación de Queue que hice en Javascript^^

Demian Martinez

student•

En el isFull() del Queue ADT no debería ser Retorna True si la cola está llena, sino, retorna false? Gracias

Raul Armas

student•

Con referente al glosario, ¿La sintaxis y los métodos no dependen del lenguaje?

Fernanda Vieira Jófili

student•

Los métodos existen en cualquier lenguaje de programación porque son parte del acceso a los datos y la lógica de almacenamiento. Esto significa que lo que diferenciará es cómo se implementarán los métodos en cada lenguaje de programación.

Marco Ezequiel Morales

student•

Gracias por este excelente Resumen

Tipos Abstractos de Datos: Listas, Pilas y Colas

Bienvenido al Curso

Algoritmos y Estructuras de Datos: Curso Básico

Introducción a los algoritmos

Cómo Funcionan las Computadoras y el Sistema Binario

Introducción a Lenguajes de Programación: Bajo y Alto Nivel

Estructuras de Datos para Rutas Más Cortas en Mapas

Algoritmo de Dijkstra para encontrar la ruta más corta

Metodología para Resolver Algoritmos Paso a Paso

Variables y Tipos de Datos en Programación

Creación de Tipos de Datos Personalizados en C

Configuración de Ubuntu en Windows 10 para C/C++

Implementación de User Defined Data Type en C: Estructuras paso a paso

Tipos de Datos Abstractos y Estructuras de Datos en Programación

Tipos Abstractos de Datos: Lista, Pila, Cola y Diccionario

Tipos Abstractos de Datos: Listas, Pilas y Colas

Clases y objetos

Colas y estructuras de datos: gestión de pedidos en restaurante

Implementación de Queues con Arrays en Visual Studio Code

Implementación de Abstract Data Type en C: Función enqueue

Implementación de la función dequeue en estructuras de datos en C

Implementación de Colas en C: Declaración y Uso de Funciones Básicas

Algoritmos de ordenamiento

Algoritmos de Ordenamiento: Conceptos y Aplicaciones Básicas

Funcionamiento del Algoritmo de Ordenamiento Burbuja

Implementación de Bubble Sort en C paso a paso

Implementación de Bubble Sort en C y función de impresión

Ordenamiento por Inserción en C: Algoritmo y Ejemplo Práctico

Algoritmos de Ordenamiento Descendente: Implementación Práctica

Recursividad

Recursividad en Programación: Entendiendo el Factorial

Factorial Recursivo en C: Implementación y Ejemplo

Inversión de cadenas con recursividad en Java

Recursividad en Python: Arte con Turtle y Funciones Recursivas

Divide and conquer y programación dinámica

Diseño y análisis de algoritmos: Divide y vencerás

Introducción a Programación Dinámica y Quicksort

Ordenamiento de Arrays con MergeSort en C

Algoritmos de Ordenamiento de Datos de Mayor a Menor

Algoritmo Quicksort en Python: Implementación y Funcionamiento

Ordenamiento Quick Sort en Python paso a paso

Algoritmos 'Greedy'

Algoritmos Voraces: Principios y Aplicaciones Prácticas

Implementación de Algoritmo Greedy para Cambio de Monedas

Cambio de Monedas en C++: Implementación y Ejecución

Grafos y árboles

Introducción a Árboles y Grafos: Estructuras de Datos Básicas

Estructura de Datos: Árboles y sus Componentes Básicos

¿Cómo comparar Algoritmos?

Comparación de Algoritmos: Complejidad y Ritmo de Crecimiento

¿Qué sigue?

Resolución de Problemas Básicos con Algoritmos y Estructuras de Datos