¿Como puedo eliminar cualquier elemento de una pila en C++?

Question

Me podrían ayudar a como en este código podría eliminar cualquiera de los elementos que se ingresen a la pila.

#include <iostream>
#include <malloc.h>
using namespace std;

struct nodo{
    char placa [6];
    nodo *sig;
};

nodo *cab, *aux;
int ingresar (){
    aux= (struct nodo *) malloc(sizeof(struct nodo));
    cout<<"Ingrese la placa del carro:";
    cin>>aux->placa;

    if (cab==NULL){
        cab = aux;
        cab->sig=NULL;
    }
    else {
        aux->sig = cab;
        cab= aux;
    }
    aux= NULL;
    free(aux);

    return 0;
}

int sacar (){
    if (cab!=NULL){
        aux= cab;
        cab= cab->sig;
        free(aux);
        return 0;
    }


}

int mostrar (){
    aux= cab;
    while(aux!=NULL){
        cout<<"Carro: ";
        cout<<aux->placa<<endl;
        aux= aux->sig;

    }
}

int main(){
    int opc=0;
    do{
        cout<<"1. Ingresar carro"<<endl;
        cout<<"2. Sacar carro"<<endl;
        cout<<"3. Mostrar carros"<<endl;
        cout<<"4. Salir"<<endl;
        cin>>opc;
        switch(opc){
            case 1: ingresar(); break;
            case 2: sacar(); break;
            case 3: mostrar(); break;
        }

    }while(opc!=4);
    return 0;
}

Está la función para sacar, pero solo saca el ultimo agregado, quiero que se pueda sacar cualquiera de los ingresados.

Answer 1

Me podrían ayudar a como en este código podría eliminar cualquiera de los elementos que se ingresen a la pila.

Si pretendes eliminar elementos arbitrarios de la pila, entonces no es una pila, es una lista.

---

Por lo que veo, estás desarrollando una lista enlazada, en general para eliminar un nodo arbitrario, los pasos a seguir son los siguientes:

Suponiendo que E es el nodo a eliminar y tanto A como P son respectivamente el anterior y el posterior a E:

1. Enlaza el siguiente de A con P.
2. Elimina E.

La función que hace eso podría parecerse a:

void Eliminar(char (&placa)[6])
{
    for (nodo *actual = cab, anterior = nullptr; actual; anterior = actual, actual = actual->sig)
    {
        if (std::equal(placa, placa + 6, actual->placa))
        {
            if (anterior)
            {
                // Enlaza el siguiente de 'A' con 'P'.
                anterior->sig = actual->sig;
            }
            else
            {
                // A no ser que sea el primer nodo, en ese caso cambiamos la cabeza
                cab = actual->sig;
            }

            delete actual;
            return;
        }
    }
}

Una vez respondida la pregunta, vamos a lo serio: Has etiquetado y titulado la pregunta como c++, pero tu código apenas sigue los paradigmas de ese lenguaje, necesitas hacer las siguientes correcciones:

• No uses cabeceras de c, <malloc.h> no es una cabecera de C++, no la uses. Lee este hilo para saber más del tema.
• Evita las variables globales. Lee esta respuesta para saber más del tema.
• No uses malloc y free, en C++ la memoria dinámica se gestiona con new y delete.
• Encapsula tus datos.

Answer 2

La pila al estar implementada como lista enlazada, cada nodo tiene como referencia un puntero que apunta hacia el siguiente elemento de la lista.

Es decir, al ser una pila solo puedes acceder al ultimo elemento. Sin embargo, como existe esta referencia, puedes recorrer toda la pila como si se tratara de recorrer una lista enlazada al revés.

Para eliminar un enésimo elemento de tiene que

• Posicionar una iteración un nodo antes que el elemento a remover.
• Usar estas referencias para conectar el nodo en la iteración actual con un nodo dos espacios adelante
• Asignarle al nodo a remover como siguiente elemento NULL, que queda perfecto por que es un puntero.

Mi ejemplo es general, defino dos structs. Uno como nodo y otro como pila:

typedef struct node {
    int value;
    struct node *next;
} NODE_t;

---

typedef struct {
    NODE_t *top;
} STACK_t;

Para hacer más abstracta la inicialización de nodos y de la pila, tengo estas dos funciones "constructoras":

NODE_t *Node(int value) {
    NODE_t *node = (NODE_t*)malloc(sizeof(node));
    node -> value = value;
    node -> next = NULL;

    return node;
}

---

STACK_t *Stack(NODE_t *node) {
    STACK_t *stack = (STACK_t*)malloc(sizeof(stack));
    stack -> top = node;

    return stack;
}

La función que se encarga de añadir elementos a la pila

• Crea un nuevo nodo.
• Redifine la referencia inicial hacia NULL, por la cima de la pila.
• Define la cima de la pila como el nuevo nodo.

---

int push(STACK_t *stack,int value) {
    NODE_t *new_node = Node(value);
    if (new_node == NULL) return -1;

    new_node -> next = (stack -> top);
    stack -> top = new_node;
    return 0;
}

Se produciría algo así:

Cima <= Nuevo Nodo

Existe la referencia de que cuando se elimine el último elemento de la pila, la cima va a ser el elemento anterior a este. Este elemento es un nodo, que tiene como siguiente a la cima.

Al existir este tipo de referencia doble, puedes recorrer la pila en dirección contraria (como lista enlazada), y eliminar el nodo como si fuera una lista enlazada.

                              NULL
                               *
                               |  
 Iteración Actual ***> Siguiente Nodo ***> Siguiente Siguiente Nodo
        |                                              *   
        |                                              |
        |===============================================

Donde ****> las referencias sin modificar

Ten en cuenta, que si se va a extraer el último elemento de la pila se tiene que usar la función para extraer solo el último.

void remove(STACK_t *stack,int index) {
    int count = 0;
    NODE_t *temp = (stack -> top);

    while(true) {
        if (count == (index - 1)) {
            NODE_t *aux = (temp -> next);
            (temp -> next) = (temp -> next) -> next;
            (aux -> next) = NULL;
            free(aux);

            break;
        }

        temp = temp -> next;
        count++;
    }
}

Al implementar esta función, la pila pierde su concepto. Debido a que estarías extrayendo un elemento que no es el último. Más bien sería una lista enlazada con una cima.

Lo más conveniente para imprimir una pila es usar el método pop() hasta que retorne NULL, pero decidí no implementarlo. Para imprimir la pila como lista enlazada se tiene que recorrer en dirección contraria hasta que un nodo equivalga a NULL:

void print(STACK_t *stack) {
    NODE_t *temp = (stack -> top);

    printf("{ ");
    while (temp != NULL) {
        std::cout << temp -> value << " ";
        temp = temp -> next;
    }
    printf("}\n");
}

Ahora implementando la "pila", se añaden los nodos se remueve x elemento y se imprime por pantalla:

int main(int argc, char const *argv[]) {
    STACK_t *mystack = Stack(Node(25));
    push(mystack,67);
    push(mystack,137);
    push(mystack,26);
    push(mystack,15);
    push(mystack,123);
    print(mystack);

    remove(mystack,3);
    print(mystack);

    return 0;
}

En ejecución muestra:

{ 123 15 26 137 67 25 }
{ 123 15 26 67 25 }

Espero haberte ayudado. :)

Answer 3

lo que pides como tal, no se puede. Sin embargo, podemos crear una funcion que:

• Crea una pila auxiliar
• Vacie todos los datos de la pila primaria a la auxiliar
• Obtenga la posicion de elemento deseado
• Pasar todos los datos, salvo el elemento a eliminar.
• Completo.

Primer paso, creamos un metodo en el cual obtendremos la posicion del elemento a eliminar:

int Pila::posicion(int x){}

Luego creamos una Pila auxiliar con la que nos apoyaremos, ademas de otras variables, como un contador y una bandera (uno para ir verificando cuantos datos hemos recorrido y, el otro para decir si, es la que deseamos eliminar o no.:

Pila paux;
int band = 0:
int contador = 0;

Muy bien ahora viene la parte donde comprobamos si la pila no esta vacia, ya que, si esta vacia, que nos arroje un mensaje, seguido de un finalizar el metodo, esto lo logramos con un return -1, entonces, esta parte quedaria algo asi:

if(estaVacia()){
    cout<<"Error en posicion()\n";
    return -1;
}

Si este no es el caso, nos dirigimos al else donde viene la parte divertida y es que debemos pensar que sigue:

• Recorrer la pila mientras esta no este vacia.
• Contar y llevar nuestro control con la variable contador
• Esperar a que nuestra bandera cambie de valor, si encontramos el dato que deseamos

Comencemos, lo primero que necesitamos es, recorrer la pila mientras esta aun tenga elementos y, durante el recorrido, ir checando el estado de nuestra bandera (para detectar si esta cambia de valor). En codigo se traduce:

while(!estaVacia() && !band)

y dentro de este ciclo while, preguntamos si el dato que tenemos, es igual al que buscamos, la bandera cambia de 0 a 1.

if(getDato()==x)
    band =1;

en caso de que esto no suceda, todos los elementos de tu pila original, se muevan a la pila auxiliar, excepto el dato que deseas sacar.

else
    contador++;
    paux.push(getDato());
    pop();

Espera, que aun no hemos acabado, ya encontramos el dato que buscabamos, tambien lo eliminamos, y usamos la pila auxiliar. Pero, no hemos devuelto los elementos a la pila original, ya que, si no las traemos de vuelta, estas pueden perderse.

Iteramos en la pila auxiliar mientras esta no este vacia, para obtener los datos, sacarlos de esta pila y agregarlos de nueva cuenta a la pila original.

while(!paux.estaVacia())
    push(paux.getDato());
    paux.pop();

Y de esa manera es como puedes sacar un dato "de cualquier lugar"

El codigo completo quedaria algo asi:

    int Pila::posicion(int x){
    Pila paux;
    
    int contador=0;
    int band = 0;
    
    if(estaVacia()){
        cout<<"Error en posicion()\n";
        return -1;
    }else{
        while(!estaVacia() && !band){
            if(getDato()==x)
                band =1;
                
                else
                    contador++;
            paux.push(getDato());
            pop();
        }while(!paux.estaVacia()){
            push(paux.getDato());
            paux.pop();
        }
        if(band)
            return contador;
        else
            return -1;
    }
}

Tambien te agrego el metodo getDato()

int Pila::getDato(){
    if(estaVacia()){
       cout<<"Error en getDato()";
        return -1;
    }
    return tope->getDato();
}

Aclaracion, el codigo que explico es de un ejercicio que resolvi en la universidad, el cual difiere un poco de sintaxis con el tuyo. Aunque la logica es la misma. Si tienes alguna duda aqui estamos :)