Stack, pop function, it has to remove at the end

Asked

Viewed 2,486 times

2

#include <stdio.h>
#include <stdlib.h>
typedef struct pilhaElement{
    int data;
    struct pilhaElement *next;
}PilhaElment;
typedef struct pilha{
    PilhaElment *head;
    PilhaElment *tail;
    int size;
}Pilha;
Pilha *iniciarpilha(){
    Pilha *pi = (Pilha *) malloc(sizeof(Pilha));
    if(pi!=NULL){
        pi->size = 0;
        pi->head = NULL;
        pi->tail = NULL;
    }
    return pi;
}
void liberapilha(Pilha *pi){
    if(pi != NULL){
        PilhaElment *node;
        while(pi->head!=NULL){
            node = pi->head;
            pi->head = pi->head->next;
            free(node);
        }
        free(pi);
    }
}
void push(Pilha *pi,int num){
    if(pi == NULL){
        return;
    }
    PilhaElment *node = (PilhaElment *) malloc(sizeof(PilhaElment));
    if(pi->size == 0){
        node->data = num;
        node->next = NULL;
        pi->head = node;
        pi->tail = node;
    }
    else{
        node->data = num;
        node->next = NULL;
        pi->tail->next = node;
        pi->tail = node;
    }
    (pi->size)++;
}
void printpilha(Pilha *pi){
    if(pi == NULL){
            printf("Pilha vazia.\n");
            return;
    }
    PilhaElment *node = pi->head;
    while(node != NULL){
        printf("%d ",node->data);
        node = node->next;
    }
}
void pop(Pilha *pi){
    if(pi == NULL){
        printf("Pilha vazia.\n");
    }
    PilhaElment *node = pi->head;
   while(node!=pi->tail){
        node = node->next;
   }
  node->next = NULL;
  free();
}
int main(){
    Pilha *pi = iniciarpilha();
    push(pi,1);
    push(pi,2);
    push(pi,3);
    printpilha(pi);
    pop(pi);
    printf("\n%d",pi->tail->data);
   //printpilha(pi);
    return 0;
}

Someone gives me help to solve the problem of the pop function, she should be removing at the end, but I’m breaking the dick when I try, the insertion of the stack is being at the end.

c stack
  • 1

    Is there a way to [Dit] the question and explain the problem better? If you are implementing a stack, it makes no sense for you to remove an element from the end, since it is LIFO (last in, first out).

  • 1

    Yes, I know it’s LIFO, so I’m inserting at the end. That’s why I’m removing at the end.

  • In fact, I must have misunderstood. The [Edit] tip the question remains. Explain what each function should do and what each one is doing, as well as the logic you tried to implement in the ones that are not working.

  • @Andersoncarloswoss , if @Pedrohenriquefariateixeira put the new elements at the end, then it makes sense to remove from the end. @Pedrohenriquefariateixeira , as you are using list on, I would give the push and the pop in the header (head in its code) of the stack; I prefer to do this manipulation of the stack at the end of it when the implement over an array

1 answer

2

A stack or a queue is managed with behavior. Just follow the respective contract that reaches the battery behavior or the queue behavior desired.

The contract of pile is lifo:

last in, first out

That translating gets:

last in, first out

So we need two actions to make the data structure behave like a stack:

  • a function that includes an element (known as push);
  • a function that removes element (known as pop).

I’m going to put two different implementations here for this: the first one is about a fixed size vector; the second one is about simply chained list. With some adjustments to manage the internal vector, it is possible to generalize to an arbitrary size vector.

Stack on vector of fixed size

A stack made on a fixed-size vector depends on the size of the created vector. To know where to place in the vector, it is also interesting to know how many elements have already been filled.

typedef struct pilha_vetor_fixo {
    int tamanho, ocupado;
    int *dados;
} Pilha_vetor_fixo;

Pilha_vetor_fixo *init_pilha_vetor_fixo(int tamanho) {
    int *dados = (int*) malloc(sizeof(int) * tamanho);
    Pilha_vetor_fixo *ret = (Pilha_vetor_fixo*) malloc(sizeof(Pilha_vetor_fixo));

    ret->ocupado = 0;
    ret->tamanho = tamanho;
    ret->dados = dados;

    return ret;
}

/* retorna 1 se deu certo, 0 caso esteja cheio/falhou a inserção */
int push_pilha_vetor_fixo(Pilha_vetor_fixo *p, int dado) {
    /* primeiro, verifica se tem espaço para inserir */
    if (p->ocupado < p->tamanho) {
        /* tem espaço, então insere no fim */
        p->dados[p->ocupado] = dado;
        p->ocupado += 1;
        return 1;
     } else {
         /* não tem espaço suficiente, retornar 0 */
         return 0;
      }
}

/* pop retornando o elemento da pilha sendo removido, ou -1 caso não seja possível */
 int pop_pilha_vetor_fixo(Pilha_vetor_fixo *p) {
     /* só é possível remover se existir pelo menos um elemento */
     if (p->ocupado > 0) {
         /* decrementa quantidade de casas ocupadas e retorna último elemento */
         p->ocupado -= 1;
         return p->dados[p->ocupado];
     } else {
         return -1; /* código de falha do retorno */
     }
}

Stack on Single Linked List

Here we have a pile that points to the head of a simple linked list. So I just need to worry about the element at the top of the stack and, by adding a new element, make it point to the rest of the stack.

typedef struct lista {
    int dado;
    struct lista *prox;
} Lista;

typedef struct pilha_lista {
    Lista *topo;
    /* sim, dá para atender ao contrato usando apenas esse elemento */
} Pilha_lista;

/* iniciando uma pilha baseada em lista, não precisa de nenhum parâmetro */
Pilha_lista *init_pilha_lista() {
    Pilha_lista *ret = (Pilha_lista*) malloc(sizeof(Pilha_lista));
     ret->topo = NULL;
     return ret;
}

/* iniciar um elemento da lista tendo seu dado e o próximo */
Lista *init_lista(int dado, Lista *prox) {
    Lista *ret = (Lista*) malloc(sizeof(Lista));
    ret->dado = dado;
    ret->prox = prox;
    return ret;
}

/* a priori, não vou tratar falha de malloc, então vou assumir que sempre dá certo */
int push_pilha_lista(Pilha_lista *p, int dado) {
    /* crio um novo elemento da lista apontando para a lista atual, então atualizo o topo */
    Lista *novo_elemento = init_lista(dado, p->topo);
    p->topo = novo_elemento;

    return 1;
}

/* assumindo o mesmo código de erro que o exemplo de pilha sobre vetor fixo */
int pop_pilha_lista(Pilha *p) {
    /* verificar o topo é o suficiente para garantir que há elementos na pilha */
    if (p->topo != NULL) {
        /* guardar o nó do topo atual, atualizar o topo para o próximo da lista, salvar o dado numa variável, liberar o espaço alocado para o elemento removido */
        Lista *removido = p->topo;
        int dado_removido = removido->dado;
        p->topo = removido->prox;
        free(removido);

        return dado_removido;
    } else {
        return -1;
    }
}

Browser other questions tagged c stack

You are not signed in. Login or sign up in order to post.