How to implement a queue using two stacks

Question

Hello, I need to implement a queue using two stacks, IE, I need to insert an integer on stack 1, and when removing an element all items on stack 1 should be transferred to stack 2, making it look like a queue.

Items on stack 1 can only be transferred if stack 2 is empty, while items should be removed from stack 2.

The code for insertion and removal on stack 1 is as follows:

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

typedef struct noLista{
    int info;
    struct noLista *prox;
} Elemento;

    Elemento* criarNovo(int Caractere);
    Elemento* Push(Elemento *Topo, int Caractere);
    Elemento* Pop(Elemento *Topo);
    Elemento* Top(Elemento *Topo);

main () {
    int Dados, i, op;
    Elemento *Pilha = NULL, *aux;

    do{
    system("cls");
    printf("1 - Adicionar elemento\n");
    printf("2 - Remover elemento\n");
    printf("0 - Encerrar\n\n");

    printf("Opcao: ");
    scanf("%d", &op);

    switch(op){
        case 1:
            printf("Digite um inteiro: ");
            scanf("%d", &Dados);

            Pilha = Push(Pilha, Dados);
            printf("Elemento adicionado\n\n");
            system("pause");
            break;

        case 2:
            aux = Top(Pilha);

            if(aux != NULL){
                Pilha = Pop(Pilha);
                printf("Elemento removido\n\n");
                system("pause");
            } else{
                printf("A pilha esta vazia\n\n");
                system("pause");
            }
            break;

        case 3:

            break;

    }
    } while(op!=0);
}

Elemento* criarNovo(int Caractere){
    Elemento *novo;

    novo = (Elemento*) malloc(sizeof(Elemento));
    novo->info = Caractere;
    novo->prox = NULL;

    return novo;
}

Elemento* Push(Elemento *Topo, int Caractere){
    Elemento *novo;

    novo = criarNovo(Caractere);

    novo->prox = Topo;
    Topo = novo;
    return Topo;
}

Elemento* Pop(Elemento *Topo){
    Elemento *aux;

    aux = Topo;
    if(Topo != NULL) {
        Topo = Topo->prox;
        free(aux);
    }
    return Topo;
}

Elemento* Top(Elemento *Topo){
    return Topo;
}

What should I do?

Answer 1

typedef struct item_p
{
    int elemento;
    struct item_p *proximo;
} pilhaItem;

typedef struct
{
    pilhaItem *raiz;
    int tamanho;
} pilha;

---

pilha* pilha_nova()
{
    /* cria pilha */
    pilha *p = (pilha*) malloc(sizeof(pilha));
    if(p == NULL)
        return NULL;

    /* pilha esta' vazia */
    p->raiz = NULL;
    p->tamanho = 0;

  return p;
}

---

int pilha_tamanho(pilha *p)
{
    if (p == NULL)
        return -1;

    return p->tamanho;
}

---

int pilha_top(pilha *p)
{
    pilhaItem *aux;

    if (p == NULL || p->tamanho == 0)
        return NULL;

    aux = p->raiz;
    return aux->elemento;
}

---

pilhaItem* pilha_novo_elemento(int valor)
{
    /* aloca memoria para a estrutura pilhaItem */
    pilhaItem *item = (pilhaItem *) malloc(sizeof(pilhaItem));
    if(item == NULL)
        return NULL;

    item->elemento=valor;

    /* item ainda nao tem proximo */
    item->proximo = NULL;

    return item;
}

---

void pilha_push(pilha *p, int valor)
{
    pilhaItem *novo = NULL;

    if (p == NULL || valor == NULL)
        return;

    /* cria novo item */
    novo = pilha_novo_elemento(valor);
    if (novo == NULL)
    return;

    p->tamanho++;

    /* inserir no topo da pilha */
    /* se a pilha esta vazia */
    if (p->raiz == NULL)
    {
        p->raiz = novo;
        return;
    }

    /* primeiro elemento */
    novo->proximo = p->raiz;
    p->raiz = novo;
}

---

void pilha_pop(pilha *p)
{
    pilhaItem *curr;

    if (p == NULL || p->tamanho == 0)
        return;

    curr = p->raiz;
    p->raiz = curr->proximo;
    p->tamanho--;

    /* liberta memoria associada ao item removido */
    free(curr);
}

Test these functions in ideone (example of how to use)

---

Main file

main () {
    int Dados, i, op;
    pilha *Pilha1=pilha_nova();
    do{
    system("cls");
    printf("1 - Adicionar elemento\n");
    printf("2 - Remover elemento\n");
    printf("0 - Encerrar\n\n");

    printf("Opcao: ");
    scanf("%d", &op);

    switch(op){
        case 1:
            printf("Digite um inteiro: ");
            scanf("%d", &Dados);

            pilha_push(Pilha1, Dados);
            printf("Elemento adicionado\n\n");
            system("pause");
            break;

        case 2:
            if(Pilha1 != NULL){
                pilha_pop(Pilha1);
                printf("Elemento removido\n\n");
                system("pause");
            } else{
                printf("A pilha esta vazia\n\n");
                system("pause");
            }
            break;

        case 3:

            break;

    }
    } while(op!=0);

    pilha *Pilha2=pilha_nova();
    while(pilha_tamanho(Pilha1)>0){
        pilha_push(Pilha2, pilha_top(Pilha1));
        pilha_pop(Pilha1);
    }
}

The final part of the code I put all data of stack 1 on stack 2 as I wanted.

    pilha *Pilha2=pilha_nova();
    while(pilha_tamanho(Pilha1)>0){
        pilha_push(Pilha2, pilha_top(Pilha1)); //inserir na pilha 2 o valor de pilha 1
        pilha_pop(Pilha1); // remover o topo da pilha 1
    }

The way to move from one pile to another stack is:

LOOP: {

1. Return the value from the top of stack 1 and place on stack 2
2. Remove top value from stack 1

}

Answer 2

Since @Fabiomorais has already responded with a possible alternative implementation to the problem, I take the opportunity to show an implementation from the code you have and changing as little as possible.

I can’t help but make an aside for the nomenclature you are using that is more important than it seems. Let’s look at these lines of code:

Elemento* criarNovo(int Caractere);
Elemento* Push(Elemento *Topo, int Caractere);
int Dados, i, op;

Here you are using camelCase and Pascalcase, in addition to defining function parameters and capitalised variables. The most important thing is to be consistent and always use the same style of nomenclature, and the most widely adopted standard in C is snake_case. In this pattern these instructions would be:

Elemento* criar_novo(int caractere);
Elemento* push(Elemento *topo, int caractere);
int dados, i, op;

Names of structures and classes are often capitalized.

Starting now for the solution. First you have to create the second stack:

Elemento *Pilha = NULL, *aux, *Pilha2 = NULL;
//                              ^---

Which will be the stack that will have the items removed. The idea now is:

• If the Pilha2 has elements so remove the top of this directly.
• If it is empty you must first pass all elements to the Pilha to the Pilha2 and then remove the top of the Pilha2

Implementation:

case 2:
    if (Top(Pilha2) == NULL){  // se a pilha 2 está vazia
        while (Top(Pilha) != NULL){ //passa tudo da pilha1 para a pilha2
            int removido = Top(Pilha)->info;
            Pilha = Pop(Pilha);
            Pilha2 = Push(Pilha2, removido);
        }
    }
    if(Top(Pilha2) != NULL) { //se existem elementos
        int removido = Top(Pilha2)->info; //remove o primeiro da pilha2
        Pilha2 = Pop(Pilha2);
        printf("Elemento %d removido\n\n", removido);
    } else {
        printf("A pilha esta vazia\n\n");
    }
    break;

Watch it work on Ideone by adding elements 5, 10 and 12 and then removing them all

Visually what happens first is that first it’s all added to the Pilha1

Pilha1:
12 -> 10 -> 5 -> NULL

Pilha2:
NULL

Then on the first removal makes Pop to all of Pilha1 and makes Push to the Pilha2.

Step 1:

Pilha1:
10 -> 5 -> NULL

Pilha2:
12 -> NULL

Step 2:

Pilha1:
5 -> NULL

Pilha2:
10 -> 12 -> NULL

Step 3:

Pilha1:
NULL

Pilha2:
5 -> 10 -> 12 -> NULL    

After these steps all removals are done by Pilha2 and so start by removing in 5, giving the order 5, 10, 12 which works as a queue and not a stack.