Pila
Una pila es una estructura de datos lineal que sigue el principio de Último en entrar, primero en salir (LIFO). Esto significa que el último elemento insertado dentro de la pila se elimina primero.
Puede pensar en la estructura de datos de la pila como una pila de platos encima de otro.
Aquí puedes:
- Poner un plato nuevo encima
- Retire la placa superior
Y, si desea la placa en la parte inferior, primero debe quitar todas las placas en la parte superior. Así es exactamente como funciona la estructura de datos de la pila.
Principio de pila LIFO
En términos de programación, poner un elemento en la parte superior de la pila se llama empujar y la eliminación de un elemento se llama estallido.
En la imagen de arriba, aunque el artículo 3 se guardó en último lugar, se eliminó primero. Así es exactamente como el Principio LIFO (último en entrar, primero en salir) obras.
Podemos implementar una pila en cualquier lenguaje de programación como C, C++, Java, Python o C#, pero la especificación es prácticamente la misma.
Operaciones básicas de pila
Hay algunas operaciones básicas que nos permiten realizar diferentes acciones en una pila.
- Empujar: Añadir un elemento a la parte superior de una pila
- Estallido: Elimina un elemento de la parte superior de una pila
- Esta vacio: Comprobar si la pila está vacía
- Está lleno: Comprobar si la pila está llena
- Ojeada: Obtenga el valor del elemento superior sin eliminarlo
Funcionamiento de la estructura de datos de la pila
Las operaciones funcionan de la siguiente manera:
- Un puntero llamado PARTE SUPERIOR se utiliza para realizar un seguimiento del elemento superior de la pila.
- Al inicializar la pila, establecemos su valor en -1 para que podamos verificar si la pila está vacía comparando
TOP == -1. - Al empujar un elemento, aumentamos el valor de PARTE SUPERIOR y coloque el nuevo elemento en la posición señalada por PARTE SUPERIOR.
- Al abrir un elemento, devolvemos el elemento al que apunta PARTE SUPERIOR y reducir su valor.
- Antes de empujar, comprobamos si la pila ya está llena
- Antes de abrir, comprobamos si la pila ya está vacía
Implementaciones de pila en Python, Java, C y C++
La implementación de pila más común es usar arreglos, pero también se puede implementar usando listas.
Pitón
Java
C
C++
# Stack implementation in python
# Creating a stack
def create_stack():
stack = []
return stack
# Creating an empty stack
def check_empty(stack):
return len(stack) == 0
# Adding items into the stack
def push(stack, item):
stack.append(item)
print("pushed item: " + item)
# Removing an element from the stack
def pop(stack):
if (check_empty(stack)):
return "stack is empty"
return stack.pop()
stack = create_stack()
push(stack, str(1))
push(stack, str(2))
push(stack, str(3))
push(stack, str(4))
print("popped item: " + pop(stack))
print("stack after popping an element: " + str(stack))
// Stack implementation in Java
class Stack {
private int arr[];
private int top;
private int capacity;
// Creating a stack
Stack(int size) {
arr = new int[size];
capacity = size;
top = -1;
}
// Add elements into stack
public void push(int x) {
if (isFull()) {
System.out.println("OverFlow\nProgram Terminated\n");
System.exit(1);
}
System.out.println("Inserting " + x);
arr[++top] = x;
}
// Remove element from stack
public int pop() {
if (isEmpty()) {
System.out.println("STACK EMPTY");
System.exit(1);
}
return arr[top--];
}
// Utility function to return the size of the stack
public int size() {
return top + 1;
}
// Check if the stack is empty
public Boolean isEmpty() {
return top == -1;
}
// Check if the stack is full
public Boolean isFull() {
return top == capacity - 1;
}
public void printStack() {
for (int i = 0; i <= top; i++) {
System.out.println(arr[i]);
}
}
public static void main(String[] args) {
Stack stack = new Stack(5);
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.pop();
System.out.println("\nAfter popping out");
stack.printStack();
}
}
// Stack implementation in C
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
int count = 0;
// Creating a stack
struct stack {
int items[MAX];
int top;
};
typedef struct stack st;
void createEmptyStack(st *s) {
s->top = -1;
}
// Check if the stack is full
int isfull(st *s) {
if (s->top == MAX - 1)
return 1;
else
return 0;
}
// Check if the stack is empty
int isempty(st *s) {
if (s->top == -1)
return 1;
else
return 0;
}
// Add elements into stack
void push(st *s, int newitem) {
if (isfull(s)) {
printf("STACK FULL");
} else {
s->top++;
s->items[s->top] = newitem;
}
count++;
}
// Remove element from stack
void pop(st *s) {
if (isempty(s)) {
printf("\n STACK EMPTY \n");
} else {
printf("Item popped= %d", s->items[s->top]);
s->top--;
}
count--;
printf("\n");
}
// Print elements of stack
void printStack(st *s) {
printf("Stack: ");
for (int i = 0; i < count; i++) {
printf("%d ", s->items[i]);
}
printf("\n");
}
// Driver code
int main() {
int ch;
st *s = (st *)malloc(sizeof(st));
createEmptyStack(s);
push(s, 1);
push(s, 2);
push(s, 3);
push(s, 4);
printStack(s);
pop(s);
printf("\nAfter popping out\n");
printStack(s);
}
// Stack implementation in C++
#include <stdlib.h>
#include <iostream>
using namespace std;
#define MAX 10
int size = 0;
// Creating a stack
struct stack {
int items[MAX];
int top;
};
typedef struct stack st;
void createEmptyStack(st *s) {
s->top = -1;
}
// Check if the stack is full
int isfull(st *s) {
if (s->top == MAX - 1)
return 1;
else
return 0;
}
// Check if the stack is empty
int isempty(st *s) {
if (s->top == -1)
return 1;
else
return 0;
}
// Add elements into stack
void push(st *s, int newitem) {
if (isfull(s)) {
cout << "STACK FULL";
} else {
s->top++;
s->items[s->top] = newitem;
}
size++;
}
// Remove element from stack
void pop(st *s) {
if (isempty(s)) {
cout << "\n STACK EMPTY \n";
} else {
cout << "Item popped= " << s->items[s->top];
s->top--;
}
size--;
cout << endl;
}
// Print elements of stack
void printStack(st *s) {
printf("Stack: ");
for (int i = 0; i < size; i++) {
cout << s->items[i] << " ";
}
cout << endl;
}
// Driver code
int main() {
int ch;
st *s = (st *)malloc(sizeof(st));
createEmptyStack(s);
push(s, 1);
push(s, 2);
push(s, 3);
push(s, 4);
printStack(s);
pop(s);
cout << "\nAfter popping out\n";
printStack(s);
}Complejidad del tiempo de pila
Para la implementación basada en matrices de una pila, las operaciones de inserción y extracción toman un tiempo constante, es decir O(1).
Aplicaciones de la estructura de datos de pila
Aunque stack es una estructura de datos simple de implementar, es muy poderosa. Los usos más comunes de una pila son:
- Para invertir una palabra – Pon todas las letras en una pila y sácalas. Debido al orden de pila LIFO, obtendrá las letras en orden inverso.
- en compiladores – Los compiladores usan la pila para calcular el valor de expresiones como
2 + 4 / 5 * (7 - 9)convirtiendo la expresión en forma de prefijo o posfijo. - en navegadores – El botón Atrás en un navegador guarda todas las URL que ha visitado anteriormente en una pila. Cada vez que visita una nueva página, se agrega en la parte superior de la pila. Cuando presiona el botón Atrás, la URL actual se elimina de la pila y se accede a la URL anterior.
