data-structures
Apilar

Introducción a la pila

La pila es una estructura de datos LIFO (último en entrar, primero en salir), es decir, el elemento más reciente (o "último en") agregado a la pila será el primer elemento eliminado ("primero en salir").

Consideremos el ejemplo de los libros en una caja. Solo se puede agregar o quitar un libro de la caja a la vez, y solo se puede agregar y quitar desde la parte superior.

Ahora, la caja con los dos primeros libros se ve así:

  |--------|
  | book 2 | ◀──── top of box
  |--------|
  | book 1 | ◀──── bottom of box
  |--------|

Si añadimos el libro 3, estará en la parte superior. El resto de los libros, que se agregaron antes del libro 3, permanecerán debajo:

  |--------|
  | book 3 | ◀──── top of box
  |--------|
  | book 2 |
  |--------|
  | book 1 | ◀──── bottom of box
  |--------|

La caja es como una pila y los libros son elementos de datos. Agregar un libro al cuadro es la operación de empuje, mientras que quitar / obtener un libro de la parte superior del cuadro es la operación emergente. Si realizamos la operación pop, obtendremos el libro 3, y la caja volverá a ser como era antes de que presionáramos el libro 3. Esto significa que el último elemento (o el más reciente) que pusimos fue el primer elemento que salió (LIFO). Para obtener el libro 1, tenemos que realizar dos pops más: uno para eliminar el libro 2 y el segundo para obtener el libro 1.

Implementación de la pila utilizando una matriz. Para esto, necesitamos un índice que apunte a la ubicación superior (tos). Cada vez que se inserta un elemento en la pila, los incrementos de tos en uno y cada vez que se realiza una operación de apertura, el índice que apunta a la parte superior de la pila (tos) se reduce en uno.

EMPUJAR:

Antes de la operación PUSH

                                  tos
                                   |
                                   |
        |-----|-----|-----|-----|-----|
        | i1  | i2  | i3  |  i4 |     |
        |-----|-----|-----|-----|-----|

void push(dataElment item){
    stack[top]=item; //item = i4
    top++;
    
}

Después de la operación PUSH La pila tiene un puntero a la parte superior de la pila. Cada vez que se llama a la operación de inserción, coloca el valor en la parte superior y lo actualiza.

        tos -- Top of the stack
                            tos
                             |
                             |
        |-----|-----|-----|-----|
        | i1  | i2  | i3  |     |
        |-----|-----|-----|-----|

POP: la operación emergente elimina el contenido de la parte superior de la pila y actualiza el valor de tos disminuyendo en 1

Antes de la operación pop:

                                  tos
                                   |
                                   |
        |-----|-----|-----|-----|-----|
        | i1  | i2  | i3  |  i4 |     |
        |-----|-----|-----|-----|-----|

dataElment pop(){
    dataElment value = stack[tos--];
    return value;
}

Después de la operación pop:

                            tos
                             |
                             |
        |-----|-----|-----|-----|
        | i1  | i2  | i3  |  i4 |
        |-----|-----|-----|-----|
        When a push operation is performed it overwrites i4.
    

Usando pilas para encontrar palíndromos.

Un palíndromo es una palabra que puede leerse en ambos sentidos, como 'kayak'.

Este ejemplo mostrará cómo encontrar si una palabra dada es un palíndromo utilizando Python3.

Primero, debemos convertir una cadena en una pila (usaremos matrices como pilas).

str = "string"
stk = [c for c in str] #this makes an array: ["s", "t", "r", "i", "n", "g"]
stk.append("s") #adds a letter to the array
stk.pop() #pops the last element

Ahora, tenemos que invertir la palabra.

def invert(str):
    stk = [c for c in str]
    stk2 = []
    while len(stk) > 0:
        stk2.append(stk.pop())
    #now, let's turn stk2 into a string
    str2 = ""
    for c in stk2:
        str2 += c
    return str2

Ahora podemos comparar la palabra y la forma invertida.

def palindrome(str):
    return str == invert(str)

Implementación de la pila utilizando una matriz y una lista enlazada

Implementación de Array

#include<stdio.h>

#define MAX 100000                    //Global variables
int top = -1;
int a[MAX];

void push(int x){
    
    if(top == MAX-1){                         // Check whether stack is full
        printf("Stack Overflow\n");
        return;
    }
    
    a[++top] = x;                            // Otherwise increment top and insert x
}

void pop(){
    if(top == -1){                                     // if top = -1, empty stack
        printf("Empty stack\n");
        return;
    }
    top--;        
}

void print(){                         //printing stack values
    
    for(int i=0;i <= top;i++){
        printf("%d ",a[i]);        
    }        
    printf("\n");        
}

void topValue(){                        // Method can print the top value of a stack
    printf("%d",a[top]);
}
int main(){
        
    push(5);
    push(20);
    push(15);
    print();
    pop();
    print();
    push(35);
    print();
    topValue();    
    
}

Implementación de listas enlazadas

#include<stdio.h>
#include<malloc.h>

 struct node{
    int data;
    node* link;
};
node* top = NULL;

void push(int data){
    
    node* temp = (struct node*)malloc(sizeof(struct node*));
    temp->data = data;
    temp->link = top;
    top = temp;
}

void pop(){
    
    if(top == NULL) return;
    node* temp = top;
    top = top->link;
    free(temp);
}
void print(){
    
    node* t = top;
    while(t != NULL){
        printf("%d ",t->data);
        t=t->link;
    }
    printf("\n");
}

void topValue(){
    printf("%d ",top->data);
}
int main(){
        
    push(5);
    push(20);
    push(15);
    print();
    pop();
    print();
    push(35);
    print();            
    topValue();    
}

Comprobación de paréntesis equilibrados

Se considera que un corchete es uno de los siguientes caracteres: ( , ) , { , } , [ o ] .

Se considera que dos corchetes son un par emparejado si el paréntesis de apertura (es decir, ( , [ , o { ) aparece a la izquierda de un corchete de cierre (es decir, ) , ] o } ) del mismo tipo. Hay tres tipos de pares coincidentes de paréntesis: [] , {} y () .

Un par de paréntesis coincidentes no se equilibra si el conjunto de paréntesis que encierra no se empareja. Por ejemplo, {[(])} no está equilibrado porque los contenidos entre { y } no están equilibrados. El par de corchetes encierra un corchete de apertura único, desequilibrado, ( , y el par de paréntesis encierra un corchete de cierre simple, desequilibrado, ] .

Por esta lógica, decimos que una secuencia de corchetes se considera equilibrada si se cumplen las siguientes condiciones:

No contiene paréntesis inigualables.

El subconjunto de corchetes encerrados dentro de los límites de un par de corchetes coincidentes también es un par de corchetes coincidentes.

Algoritmo:

1. Declara una pila (por ejemplo, stack ).
2. Ahora atraviesa la cadena de entrada.

• a) Si el carácter actual es un corchete inicial (es decir, ( o { o [ ), luego empújelo para apilarlo).
• b) Si el carácter actual es un corchete de cierre (es decir ) o } o ] ), salte de la pila. Si el carácter resaltado es el corchete inicial coincidente, los paréntesis están bien, de lo contrario not balanced están not balanced .
• c) Si el carácter actual es un corchete de cierre (es decir ) o } o ] ) y la pila está vacía, entonces el paréntesis not balanced está not balanced .

3. Después de completar el recorrido, si queda algún corchete de inicio en la pila, la cadena not balanced estará not balanced contrario tendremos una cadena balanced .