Pilas y tipos de datos abstractos en Informática

Tipos de datos abstractos (ADT)

Un tipo de datos abstracto (ADT) es una abstracción de una estructura de datos

Un ADT especifica:

• Datos almacenados
• Operaciones sobre los datos
• Condiciones de error asociadas con las operaciones

Ejemplo de ADT: Coche

AUTO:

• Comenzar()
• Detener()
• Gire a la izquierda()
• Gire a la derecha()

NOTA: La implementación puede ser diferente para diferentes automóviles, por ejemplo, transmisión automática.

AUTO:

Comenzar(){ Seleccione la primera marcha Soltar el freno de estacionamiento Llevar el embrague hasta el punto de fricción. Pisar el pedal del acelerador Soltar embrague }

Componentes y Especificaciones de un ADT

Un ADT se compone de

• Una colección de datos
• Un conjunto de operaciones sobre esos datos

Las especificaciones de un TAD indican Qué hacen las operaciones del TAD, no cómo implementarlas a ellos

Implementación de un ADT Incluye la elección de una estructura de datos particular

Estructuras de datos lineales

Las estructuras lineales son colecciones de datos cuyos elementos se ordenan dependiendo de cómo se agregan o eliminan de la estructura.

Una vez que se agrega un elemento, permanece en esa posición en relación con otros elementos que vinieron antes y después de él.

Se puede pensar que las estructuras lineales tienen dos extremos, superior e inferior (o delantero y extremo o delantero y trasero).

Lo que distingue una estructura lineal de otra es la forma en que se agregan y eliminan elementos, en particular la ubicación donde ocurren estas adiciones y eliminaciones, por ejemplo, agregar solo a un extremo, agregar a ambos, etc.

El ADT de Pila

Una pila es una colección ordenada de elementos donde La adición de nuevos elementos y la eliminación de elementos existentes siempre se lleva a cabo en el mismo extremo, denominado parte superior de la pila.

es decir, agregar en la parte superior, eliminar desde la parte superior

Propiedad de último en entrar, primero en salir (LIFO) El último elemento colocado en la pila será el primer elemento eliminado

Ejemplo: Una pila de platos en una cafetería.

Operaciones Principales de la Pila

Operaciones de la pila principal:

• push(object): inserta un elemento object
• pop(): elimina y devuelve el último elemento insertado

Agrega solo en la parte superior de una pila Elimina solo de la parte superior de la pila

empujar estallido estallido

Agregar un nuevo elemento Quitar el elemento superior Quitar el elemento superior

103 12 57 34

12 57 34

12 57 34

57 34

Funciones de Pila

Stack() crea una nueva pila que está vacía. No necesita parámetros y devuelve una pila vacía.

push(item) agrega un nuevo elemento a la parte superior de la pila. Necesita el elemento y no devuelve nada. Se modifica la pila.

pop() elimina el elemento superior de la pila. No necesita parámetros y devuelve el elemento. La pila es modificado.

peek() devuelve el elemento superior de la pila, pero no lo elimina. No necesita parámetros. La pila no se modifica.

isEempty() comprueba si la pila está vacía. No necesita parámetros y devuelve un valor booleano.

size() devuelve la cantidad de elementos en la pila. No necesita parámetros y devuelve un entero.

Ejemplo de Operaciones de Pila

s=Stack() print(s.isEmpty()) s. push (4) s. push ( 'dog' ) print(s.peek()) s. push (True) print(s.size()) print(s.isEmpty()) s.push(8.4) print(s.pop()) print(s.pop()) print(s.size())

arriba Perro arriba perro arriba 4 4 verdadero 4 8,4 mejores Perro arriba Perro verdadero 4 arriba perro 4 verdadero 4

Ejemplo de Operaciones de Pila y Estado

Operaciones de pila, estado de la pila, valores devueltos

s.isEempty() [] Verdadero

s.push(4) [4]

s.push('perro') [4,'perro']

s.peek() [4,'perro'] 'perro

s.push(Verdadero) [4,'perro', Verdadero]

s.size() [4,'perro', Verdadero] 3

s.isEempty() [4,'perro', Verdadero] FALSO

s.push(8.4) [4,'perro', Verdadero,8.4]

s.pop() [4,'perro', Verdadero] 8.4

s.pop() [4,'perro'] Verdadero

s.size() [4,'perro'] 2

Clase Stack en Python

Usamos una estructura de datos de lista de Python para implementar la pila. Recuerde: la adición de nuevos elementos y la eliminación de Los elementos existentes siempre se colocan en el mismo extremo, denominado parte superior de la pila.

¿Pero cuál "final" es mejor?

class Stack: def __ init __ (self) : self.items = [ ]

def isEmpty(self) : return self. items == [ ]

def push(self, item) : self. items. append(item)

def pop(self) : return self. items . pop()

def peek (self) : return self. items [len(self.items) -1]

def size(self) : return len(self.items)

? items . . 1 Pitón Lista . . . . . . . .

Stack en Python - Versión 2

Esta implementación supone que el El comienzo de la lista contendrá el elemento superior de la pila.

class Stack: def __ init __ (self) : self.items = [ ]

def isEmpty(self) : return self. items == [ ]

def push(self, item) : self.items.append(0,item)

def pop(self) : return self.items.pop(0)

¿Qué es Big-O de push()/pop()?

En) empujar( ... ) estallido()

items . . 1 . . . . . . . .

Stack en Python - Versión 1

Esta implementación supone que el final de la lista contendrá el elemento superior de la pila.

A medida que la pila crece, se agregarán nuevos elementos al FINAL de la lista. Las operaciones de extracción manipularan el mismo

class Stack: def __ init __ (self) : self.items = [ ]

def isEmpty(self) : return self.items == [ ]

def push(self, item) : self.items. append(item)

def pop(self) : return self.items. pop()

items . . 1 . . empujar( ... ) estallido() . . . ¿Qué es Big-O de push()/pop()? . . O(1)

Orden de los Elementos en la Pila

La base de la pila contiene el elemento más antiguo , el que ha estado allí durante más tiempo.

En una pila, el orden en el que se eliminan los elementos es exactamente el inverso del orden en el que se colocaron .

8.4 1st 4th True 2nd 3rd "dog" 3rd 2nd 1 4th - 1st 4

8.4 True "dog" 4

4 "dog" True 8.4

Original Order Reversed Order

Aplicaciones de las Pilas

• Comprobación de llaves equilibradas
• Coincidencia de corchetes
• Cálculo de sufijos

Comprobación del Equilibrio de los Tirantes

Utilizar una pila para verificar si los tirantes están equilibrados

Un ejemplo de llaves equilibradas Un ejemplo de llaves no equilibradas

OHO

Requisitos para llaves equilibradas

• Cada vez que encuentre un "}", coincide con un se encontró con "{"
• Cuando llegue al final de la cadena, habrá coincidido con cada “{”

Algoritmo para Tirantes Equilibrados

Inicializar la pila para vaciarla

Por cada char leído

• Si es un corchete abierto, entonces empujelo a la pila
• Si es un corchete cerrado,
• Si la pila está vacía, devuelva ERROR
• De lo contrario, extraiga un elemento de la pila

Si es un caracter que no esta entre corchetes, omitalo.

Si la pila NO ESTÁ VACÍA, ERROR

Ejemplo de Brackets Equilibrados

Cape ort derentrada Stackoder algorithmeexetaletalgoritmo

1. push " {" {a {b}c} 2. push " {" { { { 3. pop { 4. pop Stack empty balanced

{ a {bc } 1. push " {" { 2. push " {" { { { 3. pop Stack not empty not balanced

{ab} c} 1. push " {" { 2. pop Stack empty when last " } " encountered not balanced

Correspondencia de Corchetes

Asegúrese de que los pares de soportes coincidan correctamente: p.ej {a,(b+f[4])*3,d+f[5]}

109

Otros ejemplos:

• ( .. ) .. ) // demasiados corchetes de cierre
• ( .. .. ) // demasiados corchetes abiertos
• [ .. ( .. ] .. ) // corchetes no coincidentes

.

Reglas Generales para Paréntesis

Cada o "" debe ir acompañado , de un ")", 0 " correspondiente.

correcto: ()(()){{[( )])}

incorrecto . {([( )])} t: )

incorrecto (( )){{[( )])}

incorrectot: ({[ ])}

incorrectot: ({{[])}})

Algoritmo de Coincidencia de Paréntesis

Inicializar la pila para vaciarla

Por cada char leído

• si es un corchete abierto, entonces empújelo a la pila
• si es un corchete cerrado, entonces
• si la pila está vacía, devuelva ERROR
• sacar de la pila
• si no coinciden entonces devuelve ERROR

. Si no es un corchete, omite el carácter.

Si la pila NO ESTÁ VACÍA, ERROR

Ejemplo de Correspondencia de Paréntesis

Ejemplo 1: {a,(b+f[4])*3,d+f[5]}

arriba arriba arriba arriba [ arriba { { arriba { arriba {

Ejemplo 2 de Correspondencia de Paréntesis

Ejemplo 2: ]

estallido: pop: ] () y {

arriba arriba arriba ¡¡¡ No coincide !! arriba [ arriba [

Evaluación de Expresiones Aritméticas

14-3 * 2 +7 =(14-(3 * 2) ) + 7

La precedencia del operador * tiene precedencia sobre +/-

Operadores de asociatividad del mismo grupo de precedencia evaluados de izquierda a derecha

Ejemplo: x - y + Z (x -y) + z en lugar de x - (y + z)

Calculadora de Sufijos

El cálculo de expresiones aritméticas se puede Se lleva a cabo de manera eficiente en notación Postfix con la ayuda de la pila.

Infijo - arg1 en arg2 Prefijo - en arg1 arg2 Postfijo - arg1 arg2 en

infijo sufijo Resultado

infijo (2*3)+4 2*3+4 2*(3+4)

sufijo 2 3 * 4 + 234 +* 234 +*

Resultado 10 10 14

Funcionamiento de la Calculadora de Sufijos

Requiere que ingrese expresiones sufijas

Ejemplo: 234+*

Cuando se ingresa un operando, la calculadora lo coloca en una pila

Cuando se introduce un operador, la calculadora lo aplica a los dos operandos superiores de la pila Extrae los dos operandos superiores de la pila. . Introduce el resultado de la operación en la pila.

Evaluando la expresión: 2 3 4 + *

clave ingresada Acción de la calculadora arriba

2 s.push (2) 2

3 s.push (3) 3 2

4 s.empujar (4) Los 4 mejores 3 2

+ arg2 = s.pop() arg1 = s.pop() s.push(arg1 + arg2) 7 2

* arg2 = s.pop() arg1 = s.pop() s.push(arg1 * arg2) Los 14 mejores 2