Las estructuras de datos son una colección de valores de datos, las relaciones entre ellos y las funciones u operaciones que se pueden aplicar a los datos. Ahora hay muchas estructuras de datos disponibles. Pero hoy nuestro enfoque estará en las estructuras de datos de pila. Hablaré de los siguientes temas:
- ¿Por qué estructuras de datos?
- Tipos de estructuras de datos
- ¿Qué es la estructura de datos de pila?
- Crear estructura de datos de pila
- Empuje los elementos en la pila
- Elementos pop de la pila
- Aplicaciones de la estructura de datos de pila
¿Por qué estructuras de datos?
Para responder a esto tendrás que pensar en un gran nivel. Piense en cómo los mapas de Google le muestran la mejor ruta en solo una fracción de segundos, cómo devuelve el resultado de su búsqueda en microsegundos. No se ocupa solo de 100 sitios web, se ocupa de más de mil millones de sitios y aún muestra los resultados con mucha rapidez.
Bueno, aunque el algoritmo utilizado juega un papel crucial, la estructura de datos o el contenedor utilizado es la base de ese algoritmo. En cualquier aplicación, organizar y almacenar datos de una manera o en una estructura que se adapte mejor a su uso es clave para un acceso y procesamiento de datos eficientes.
Tipos de estructuras de datos
Hay algunas estructuras de datos estándar que se pueden usar para trabajar de manera eficiente con datos. Incluso podemos personalizarlos o crear otros completamente nuevos que se adapten a nuestra aplicación.
¿Qué es la estructura de datos de pila?
Considere algunos ejemplos de la vida real:
- Envío en carga
- Platos en bandeja
- Pila de monedas
- Pila de cajones
- Desvío de trenes en una estación de ferrocarril
Todos estos ejemplos siguen un Último en entrar primero en salir estrategia. Considere los platos en una bandeja. Cuando desee elegir un plato, se verá obligado a elegir un plato de la parte superior, mientras que cuando los platos se mantuvieron en la bandeja, deben estar en orden inverso. Los ejemplos anteriores que siguen a Último en entrar, primero en salir (LIFO) principio se conocen como Apilar .
Aparte de las operaciones complementarias, puedo decir que las principales Operaciones posibles en la pila son:
que es un espacio de nombres en c ++
- Empuje o inserte un elemento en la parte superior de la pila
- Pop o eliminar un elemento de la parte superior de la pila
Crear estructura de datos de pila
class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1
- tamaño máximo es el número máximo de elementos que se esperan en la pila.
- Los elementos de la pila se almacenan en la lista de Python.
- Top indica el índice más alto de la pila que inicialmente se toma -1 para marcar la pila vacía.
El estado inicial de la pila se puede ver en la Figura donde max_size = 5
Empuje el elemento en la pila
Ahora, si desea ingresar o empujar un elemento a la pila, debe recordar que
- La parte superior señalará el índice en el que se insertará el elemento.
- Y que no se insertará ningún elemento cuando la pila esté llena, es decir, cuando max_size = top.
Entonces, ¿cuál debería ser el algoritmo?
# devuelve el tamaño máximo de la pila def get_max_size (self): return self .__ max_size # devuelve el valor bool si la pila está llena o no, True si está llena y False de lo contrario def is_full (self): return self.get_max_size () - 1 == self .__ top #pulsa el elemento en la parte superior de la pila def push (self, data): if (self.is_full ()): print ('la pila ya está llena') else: self .__ top = self .__ top + int (1 ) self .__ elements [self .__ top] = data # Puede usar el siguiente __str __ () para imprimir los elementos del objeto DS mientras se depura def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = '' .join (msg) msg = 'Apilar datos (de arriba a abajo):' + msg return msgAhora, cuando ejecutas lo siguiente:
stack1 = Stack (4)
#Presione todos los elementos requeridos.
stack1.push ('A')
stack1.push ('B')
stack1.push ('C')
stack1.push ('E')
imprimir (stack1.is_full ())
imprimir (pila1)
Salida:
la pila ya está llena
Cierto
Datos de pila (de arriba a abajo): D C B A
Elementos pop de la pila
Ahora, como ha insertado los elementos en la pila, desea hacer estallarlos, por lo que debe ocuparse de lo siguiente:
- La pila no está vacía, es decir, ¡arriba! = -1
- Cuando elimina los datos, la parte superior debe apuntar a la parte superior anterior de la pila.
Entonces, ¿cuál será el algoritmo?
#returns bool value ya sea que la pila esté vacía o no, True si está vacía y False en caso contrario def is_empty (self): return self .__ top == - 1 #returns popped value def pop (self): if (self.is_empty ()): print ('nada para mostrar, ya está vacío') else: a = self .__ elements [self .__ top] self .__ top = self .__ top-1 devuelve un #display todos los elementos de la pila de arriba a abajo def display (self): para i en rango (self .__ top, -1, -1): print (self .__ elementos [i], end = '') print ()Ahora, considerando la pila creada anteriormente, intente hacer estallar elementos
cómo convertir double en int java
imprimir (stack1.pop ())
imprimir (stack1.pop ())
imprimir (pila1)
imprimir (stack1.pop ())
imprimir (stack1.pop ())
imprimir (stack1.pop ())
Salida:
re
C
Datos de pila (de arriba a abajo): B A
B
A
nada para hacer estallar, ya vacío
Aplicaciones de la estructura de datos de pila
- Ejemplo 1:
Una pila se utiliza para implementar el algoritmo de coincidencia de corchetes para la evaluación de expresiones aritméticas y también en la implementación de llamadas a métodos.
Respuesta a la cual es 5.
- Ejemplo 2:
Portapapeles en Windows usa dos pilas para implementar operaciones de deshacer-rehacer (ctrl + z, ctrl + y). Habría trabajado en editores de palabras de Windows como MS-Word, Bloc de notas, etc. Aquí hay un texto escrito en MS-Word. Observe cómo cambió el texto al hacer clic en Ctrl-Z y Ctrl-Y.
Aquí hay un código que simula la operación deshacer-rehacer. Repase el código y observe cómo se usa la pila en esta implementación.
#creating class stack class Pila: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1 def is_full (self): if (self .__ top == self .__ max_size-1): return True return False def is_empty (self): if (self .__ top == - 1): return True return False def push (self, data): if (self.is_full ()): print ('La pila está llena !!') else: self .__ top + = 1 self .__ elements [self .__ top] = data def pop (self): if (self.is_empty ()): print ('¡La pila está vacía! ! ') else: data = self .__ elementos [self .__ top] self .__ top- = 1 return data def display (self): if (self.is_empty ()): print (' La pila está vacía ') else: index = self .__ top while (index> = 0): print (self .__ elements [index]) index- = 1 def get_max_size (self): return self .__ max_size # Puede usar el siguiente __str __ () para imprimir los elementos del Objeto DS mientras se depura def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = ' '.join (msg) msg =' Apilar datos (de arriba a abajo): '+ msg return ms g # función para implementar la operación de quitar o retroceder def remove (): portapapeles global, undo_stack data = portapapeles [len (portapapeles) -1] portapapeles.remove (datos) undo_stack.push (datos) imprimir ('Eliminar:', portapapeles) # función para implementar la operación deshacer def undo (): portapapeles global, undo_stack, redo_stack if (undo_stack.is_empty ()): print ('No hay datos para deshacer') else: data = undo_stack.pop () clipboard.append ( data) redo_stack.push (data) print ('Deshacer:', portapapeles) # función para implementar la operación de rehacer def redo (): portapapeles global, undo_stack, redo_stack if (redo_stack.is_empty ()): print ('No hay datos para rehacer ') else: data = redo_stack.pop () if (datos no en el portapapeles): print (' No hay datos para rehacer ') redo_stack.push (data) else: clipboard.remove (data) undo_stack.push ( data) print ('Rehacer:', portapapeles) portapapeles = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Stack (len (portapapeles)) redo_stack = Stack (len (portapapeles)) eliminar () deshacer () rehacer ()Salida:
Quitar: ['A', 'B', 'C', 'D', 'E']
Deshacer: ['A', 'B', 'C', 'D', 'E', 'F']
Rehacer: ['A', 'B', 'C', 'D', 'E']
Con esto, llegamos al final de este artículo de Estructura de datos de pila en Python. Si entendió y ejecutó correctamente los códigos por sí mismo, ya no es un novato en Stacks Data Structure.
cómo clonar un objeto en java
Tienes una pregunta para nosotros? Menciónelo en la sección de comentarios de este artículo y nos comunicaremos con usted lo antes posible.
Para obtener un conocimiento profundo de Python junto con sus diversas aplicaciones, puede inscribirse en Live con soporte 24/7 y acceso de por vida.