#include <stdio.h>
#include <stdlib.h>

typedef struct lista{
  int info;
  struct lista *prox;
} TLSE;

typedef struct pilha{
	TLSE *prim;
}TPilha;

TLSE* inserel(TLSE *l, int elem);
void imprimel(TLSE *l);
void liberal(TLSE *l);
TLSE* retiral(TLSE *l, int elem);
TLSE* buscal(TLSE *l, int elem);

void push(TPilha *p, int elem);
int pop(TPilha *p);
int vazia_p(TPilha *p);
TPilha *inicializa_p(void);
void libera_p(TPilha *p);
void imprime_p(TPilha *p);

TPilha*copia(TPilha*p);
TPilha* misc (TPilha*p, int y);

int main(void){
    int n;
    TPilha*p=inicializa_p();
    int op=1;
    while(op==1)
    {
        printf("Digite um valor para alocar na pilha: ");
        scanf("%d",&n);
        push(p,n);
        printf("Operar novamente? 1 ou 0? ");
        scanf("%d",&op);
    }
    printf("Pilha original:\n");
    imprime_p(p);
    printf("Qual valor de miscelania? ");
    int m;
    scanf("%d",&m);
    TPilha*resp=misc(p,m);
    printf("\n");
    printf("Pilha misc:\n");
    imprime_p(resp);
    libera_p(p);
    libera_p(resp);
    return 0;
}
TPilha* misc (TPilha*p, int y)
{
    TPilha*resp=inicializa_p();
    TPilha*aux=inicializa_p();
    resp=copia(p);
    int x;
    int fora;
    while(!vazia_p(resp))
    {
        x=pop(resp);
        if(x==y)
        {
            if(!vazia_p(resp))fora=pop(resp);
            if(!vazia_p(aux))fora=pop(aux);
            push(aux,x);
        }
        else
        {
            push(aux,x);
        }
    }
    while(!vazia_p(aux))
    {
        x=pop(aux);
        push(resp,x);
    }
    libera_p(aux);
    return resp;
}
TPilha*copia(TPilha*p)
{
    TPilha*Copia=inicializa_p();
    TPilha*aux=inicializa_p();
    int aux_i;
    while(!vazia_p(p))
    {
        aux_i=pop(p);
        push(aux,aux_i);
    }
    while(!vazia_p(aux))
    {
        aux_i=pop(aux);
        push(Copia,aux_i);
        push(p,aux_i);
    }
    libera_p(aux);
    return Copia;
}
TLSE* inserel(TLSE *l, int elem){
  TLSE *novo = (TLSE *) malloc(sizeof(TLSE));
  novo->prox = l;
  novo->info = elem;
  return novo;
}

void imprimel(TLSE *l){
  TLSE *p = l;
  while(p){
    printf("% d ", p->info);
    p = p->prox;
  }
}

void liberal(TLSE *l){
  TLSE *p = l, *q;
  while(p){
    q = p;
    p = p->prox;
    free(q);
  }
}

TLSE* retiral(TLSE *l, int elem){
  TLSE *p = l, *ant = NULL;
  while((p) && (p->info != elem)){
    ant = p;
    p = p->prox;
  }
  if(!p) return l;
  if(!ant) l = l->prox;
  else ant->prox = p->prox;
  free(p);
  return l;
}

TLSE* buscal(TLSE *l, int elem){
  TLSE *p = l;
  while((p) && (p->info != elem)) p = p->prox;
  return p;
}
TPilha *inicializa_p(void){
	TPilha *p = (TPilha *)malloc(sizeof(TPilha));
	p->prim = NULL;
	return p;
}

int vazia_p(TPilha *p){
	return (p->prim == NULL);
}

void push(TPilha *p,int elem){
	TLSE *novo = (TLSE *)malloc(sizeof(TLSE));
	novo->info = elem;
	novo->prox = p->prim;
	p->prim = novo;
}

int pop(TPilha *p){
	if (!vazia_p(p)){
		TLSE *aux = p->prim;
		int x = aux->info;
		p->prim = aux->prox;
		free(aux);
		return x;
	}
	else{ // pilha vazia
		exit(1);
	}
}

void libera_p(TPilha *p){
	TLSE *q = p->prim,*r ;
	while(q){
		r = q;
		q=q->prox;
		free(r);
	}
	free(p);
}

void imprime_p(TPilha *p){
 	TPilha *aux = inicializa_p();
	while (!vazia_p(p)){
		int x = pop(p);
		printf("%d ",x);
		push(aux,x);
	}
	while(!vazia_p(aux)){
		push(p,pop(aux));
	}

	libera_p(aux);
}