Estructuras lineales

ESTRUCTURAS DE DATOS

UNIDAD 3 ESTRUCTURAS LINEALES ESTATICAS Y DINAMICAS
Una Estructura de datos, es una colección de datos almacenados, que se caracteriza por su
organización y las operaciones que la componen. Una estructura de datos esta compuesta por
tipos de datos simples o primitivos (entero, real, carácter, etc.).
Las estructuras de datos se organizan de forma Estática y Dinámica.
Las Estructuras de datos Estáticas, son aquellas en las que el tamaño ocupado en
memoria se define al tiempo de compilación, es decir, antes de la ejecución del
programa, y no podrá ser cambiado durante ella.



Las Estructuras de datos Dinámicas, no tienen limitaciones en la asignación de
memoria, ya que esta se define durante la ejecución del programa.

Las estructuras de datospueden ser Lineales y no Lineales, las primera se refieren a que los
elementos se encuentran posicionados lógicamente de manera secuencial uno tras otro, y las
no lineales son aquellas en que después de un elemento se encuentran posicionados más de
uno.
Entre las Estructuras Lineales se encuentran las Pilas, Colas y Listas.

PILAS
La Pila es una estructura de datos lineal que puede organizarsede manera estática o dinámica.
Se caracteriza por tener un mecanismo llamado LIFO (Last Input, First Output) que permite
realizar operaciones de inserción y eliminación de manera que el último en entrar, es el
primero en salir. Las entradas y salidas de datos se realizan por uno de sus extremos llamado
Tope.
La mayoría de lenguajes disponen de un tipo de dato Pila( Stack), sin embargo, esnecesario
conocer su manipulación ya sea mediante memoria estática o dinámica.
Mediante memoria estática la forma de representar una pila es mediante un vector. Para
representarla como estructura dinámica, se usan Listas Enlazadas o Ligadas.
Representación gráfica (Estática)
4 40
Pila
(Stack)

Tope

3 35
2 20
1 15

1

ESTRUCTURAS DE DATOS

Operaciones primitivas
1. INSERCIÓN.Consiste en agregar datos o elementos a una pila incrementando el tope
de esta, y la operación se conoce como push. Cuando se trata de una pila estática, la
operación se puede realizar siempre y cuando exista espacio en la pila.
2. ELIMINACIÓN. La supresión de un dato es conocida como operación pop, y una vez
eliminado el dato, el tope debe decrementarse. Para realizar esta operación la Piladebe tener al menos un elemento.
3. OBTENER ELEMENTO EN EL TOPE. Es la operación llamada stacktop, y permite
obtener el dato que se encuentra al tope, sin eliminarlo de la pila. Al igual que la
operación anterior, para realizarla, la Pila debe tener al menos un elemento.
4. PILA VACÍA. Permite saber si la Pila está vacía para poder realizar otras operaciones.
La operación retorna un valorverdadero si efectivamente la Pila se encuentra vacía, y
se conoce como empty.
Además de estas operaciones, cuando se trata de una Pila Estática, se debe definir la
operación para saber si la Pila está llena, ya que tendremos la limitación de memoria.

COLAS
Una cola es una estructura de datos lineal. El mecanismo que identifica a una cola es conocido
como FIFO (Fisrt Input First Output), esdecir el primer elemento que se inserta a una cola es
el primero en salir. Los extremos por donde se realizan las operaciones de entrada y salida,
son llamados fin y frente, consecutivamente.
Existen diversos tipos de colas:
1. La cola circular: Es aquella que representa a la estructura de datos como un círculo y
no como una línea recta. Esta representación soluciona el problema de espaciodesaprovechado que se presenta en una cola estática considerada como línea recta.
3
30
2

40

25

20

Fin
4
Frente

1
2. La bicola o cola doble: Es aquella en la que las inserciones y las eliminaciones se
pueden realizar por cualquiera de sus dos extremos. Existen dos tipos de bicolas:
a) Bicola de entrada restringida: Es aquella que acepta inserciones solo al final de
la cola y...