Stack, pop function, she has to withdraw at the end

Question

Stack, pop function, she has to withdraw at the end

Navigation

#1 by (2 votes)

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 helps me solve the problem of the pop function, it should be pulling off at the end, but I'm breaking the stack when I try, the stack insertion is in the end.

c stack

asked by anonymous 30.05.2017 / 03:28

1 answer

error left join linq MySQL does not install

score 2 · Answer 1

A stack or a queue can behave with behavior. Just follow the respective agreement that achieves the stack behavior or desired queue behavior .

The stack contract is LIFO:

last in, first out

Translating stays:

Last to enter, first to exit

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

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

I'll put here two distinct implementations for this: the first is about a fixed-length vector; the second is about list simply chained. With some adjustments to manage the internal vector, it is possible to generalize to an arbitrary vector size.

Stack over fixed-length vector

A stack made up of a fixed-length vector depends on the size of the vector created. To know where to put 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 over simple linked list

Here we have a stack 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 when I add 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;
    }
}