Transfer content from one stack to another C++
I need to solve a question, it asks me to display the contents of a stack inversely, I thought a lot and came to the conclusion that it is only possible to create a helper stack and transfer the contents from one stack to another, so the result of the helper stack would be the inverted stack.
The idea is easy, but I'm having a lot of difficulty creating this helper stack, I'm a beginner with Tad's and I'm breaking my head a lot to solve it.
My Code:
#include<iostream>
using namespace std;
struct no{
char n;
no *prox;
};
struct pilha{
no *topo;
};
int menu(){
int op;
cout << "\n1. Inserir na pilha\n";
cout << "2. Remover da pilha\n";
cout << "3. Imprimir pilha\n";
cout << "4. Imprimiir pilha invertida\n";
cout << "5. Sair\n";
cout << "Opcao: ";
cin >> op;
return op;
}
no* criarNo(){
char num;
cout << "Qual caractere deseja inserir: ";
cin >> num;
no *novo = new no;
novo->n = num;
novo->prox = NULL;
return novo;
}
void inserirPilha(pilha *inicio){
no *insere = criarNo();
if(inicio->topo == NULL){
inicio->topo = insere;
}
else{
insere->prox = inicio->topo;
inicio->topo = insere;
}
}
void imprimirPilha(pilha *inicio){
if(inicio->topo == NULL)
cout << "pilha vazia\n";
else{
no *aux = inicio->topo;
while(aux->prox != NULL){
cout << aux->n << " ";
aux = aux->prox;
}
cout << aux->n << " ";
}
}
void imprimirPilhaInvertida(pilha *inicio){
//Função para exibir a pilha auxiliar.
}
void removerPilha(pilha *inicio){
if(inicio->topo == NULL)
cout << "Fila vazia\n";
else
inicio->topo = inicio->topo->prox;
}
int main(){
int opcao;
pilha *inicio = new pilha;
inicio->topo = NULL;
while(true){
opcao = menu();
switch(opcao){
case 1:
inserirPilha(inicio);
break;
case 2:
removerPilha(inicio);
break;
case 3:
imprimirPilha(inicio);
break;
case 4:
imprimirPilhaInvertida(inicio);
break;
case 5:
return -1;
default:
cout << "Opcao invalida\n";
break;
}
}
return 0;
}
2 answers
Instead of creating a helper stack, it is more optimized to use only one helper variable. For example:
#include <iostream>
#include <vector>
void printVector(std::vector<int> myVector) {
int vectorSize = myVector.size();
std::cout << "[";
for(int i = 0; i < vectorSize; i++) {
std::cout << myVector[i];
if (i < vectorSize - 1) {
std::cout << ",";
}
}
std::cout << "]" << std::endl;
}
int main()
{
std::vector<int> pilha;
int aux = 0;
// popula a pilha
for(int i = 0; i < 5; i++){
pilha.push_back(i);
}
printVector(pilha);
int pilhaSize = pilha.size();
for(int a = 0; a < pilhaSize/2; a++){
std::cout << "loop qtts: " << pilhaSize/2 << std::endl;
std::cout << "loop iteration: " << a + 1 << std::endl;
// aux = armazena posicao mais a direita da pilha baseado em a
aux = pilha[(pilhaSize - 1) - a];
std::cout << "aux: " << aux << std::endl;
//sobrescreve o valor mais a direita com o valor mais a esquerda
pilha[(pilhaSize - 1) - a] = pilha[a];
//sobrescreve o valor mais a esquerda, com o antigo valor mais a direita
pilha[a] = aux;
// caso necessário para o seu problema, limpe o buffer
printVector(pilha);
aux = 0;
}
return 0;
}
If our initial stack contained the values [0,1,2,3,4]: Iterations: 1: [4,1,2,3,0] 2: [4,3,2,1,0] (a = 2) is equal to 2 (5/2 .... nImpar / 2 rounds down) soon the loop stops.
Link with running code: http://cpp.sh/8zijy
See also, that unlike if you had created an auxiliary vector and added The Last value to first position of the last and so on, you would have traversed the entire vector, whereas in this way you would have traversed half the vector, or, half the Vector - 1 if the vector is odd.
Tip, Use ready-made and simple structures to test if the way to solve your problem is valid, before optimizing the time (speed) and space (memory) that your program uses. Creating your own structs and allocating memory manually teaches you a lot about how the computer think and improve your code, but very little about logic.
EDIT 1: now that I realize that you are inside the stack, therefore, in order not to lose the initial state, just create a copy and after returning the inverted stack recover it.
In your case, you are using a list stack. In order for you to use a stack, you need to use push methods to enter value into the stack and pop methods to remove value from the stack. There are some details that need to be changed in your code. Firstly, when you create a stack type it is not good practice to insert the element. It should have been allocated an in-memory position for the new element instead, using (Type*) malloc(sizeof (type)). To insertion must be done inside the insert (in the case, the push). Another detail is that the stack elements must be released after the stack is used(helper stacks within the method and the main stack at the end of the program).
To print it is necessary to use a helper stack, where you use the pop in the stack, saving the value in a variable, prints the variable and saves its value in the helper stack through a push until the stack is empty. Use another loop to insert back the saved contents into the helper stack. See the code below:
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);
}
This is an impression of the stack in its normal order, from top to bottom. To print inversely, simply place the print in the second loop:
void imprime_invertido_p(TPilha *p){
TPilha *aux = inicializa_p();
while (!vazia_p(p)){
push(aux,pop(p));
}
while(!vazia_p(aux)){
int x = pop(aux);
printf("%d ",x);
push(p,x);
}
libera_p(aux);
}