STACKS

[D2w0RXSz]

Hi there!

Tonight I'm having a c++ test and I still cant understand how to work with stacks. I need a brief explanation 'cause I can memorize the program but then it won't make sense once the professor may change it and I'll burn my finger.

I must confess I'm desperate due to the fact that I need a 1.8 grade out of 2 points. Otherwise I will certainly fail.

The program above was showed by the teacher in one of our classes (is it correct?):



#include <cstdlib>
#include <iostream>

using namespace std;
struct tipo_pilha
{
char elemento [100];
int indice_topo;
};

tipo_pilha push (tipo_pilha pilha, char elemento)
{
if (pilha.indice_topo+1<=100) {
pilha.indice_topo++;
pilha.elemento[pilha.indice_topo]= elemento;
}
else
cout<<"pilha cheia!!"<<endl;
return pilha;
}
tipo_pilha pop (tipo_pilha pilha){
if (pilha.indice_topo>=0)
pilha.indice_topo--;
else
cout<< "pilha vazia!!"<<endl;
return pilha;
}
char top (tipo_pilha pilha) {
if (pilha.indice_topo>=0)
return pilha.elemento[pilha.indice_topo];
else
cout<< "Pilha vazia!!"<<endl;
}


int main(int argc, char *argv[])
{
tipo_pilha pilha;
pilha.indice_topo=-1;
string lixo;
char letra;

cout<< "Digite uma palavra"<< endl;
while (letra!= '+'){
cin>>letra;
if (letra!= '+')
pilha = push (pilha, letra);
}
cout<<"A palavra em ordem inversa eh:";
while (pilha.indice_topo>=0){
cout<<top (pilha);
pilha=pop (pilha);

}
system("PAUSE");
return EXIT_SUCCESS;
}




Why do we need the letra!='+' stuff? By the way, the word letra means letter.

What are the if (pilha.indice_topo+1<=100) and if (pilha.indice_topo>=0) commands for? pilha = stack

Please I really need you help so if you could give me a hand I'd apreciatte that.

TIA

Daniel

[kbw]

They're range checks to make sure only a valid index into elemento is used.

Why 100? because char elemento [100];

[D2w0RXSz]

I see... it is a check to make sure a number is within a certain range.

now..

tipo_pilha push (tipo_pilha pilha, char elemento)
{
if (pilha.indice_topo+1<=100) {
pilha.indice_topo++;
pilha.elemento[pilha.indice_topo]= elemento;
}
else
cout<<"pilha cheia!!"<<endl;
return pilha;


In English:

type_stack push (type_stack stack, char element)
{
if (stack.indice_top++;
stack.element[stack.indice_topo] = element


Considering type_stack is the name of the structure, do I have to use it to set a command like push? Is this what it is about?

Why should I type type_stack and then (type_stack stack) again?

Thanks for replying

Daniel

[kbw]

I've reformatted the code and will go through it for you.

#include <iostream>
using namespace std;

struct tipo_pilha
{
	char elemento [100];
	int indice_topo;
};

tipo_pilha push(tipo_pilha pilha, char elemento)
{
	if (pilha.indice_topo+1<=100)
	{
		pilha.indice_topo++;
		pilha.elemento[pilha.indice_topo]= elemento;
	}
	else
		cout<<"pilha cheia!!"<<endl;

	return pilha;
}

tipo_pilha pop(tipo_pilha pilha)
{
	if (pilha.indice_topo>=0)
		pilha.indice_topo--;
	else
		cout<< "pilha vazia!!"<<endl;
	return pilha;
}

char top(tipo_pilha pilha)
{
	if (pilha.indice_topo>=0)
		return pilha.elemento[pilha.indice_topo];
	else
		cout<< "Pilha vazia!!"<<endl;
}

int main(int argc, char *argv[])
{
	tipo_pilha pilha;
	pilha.indice_topo = -1;

	cout<< "Digite uma palavra"<< endl;
	char letra = 0;
	while (letra!= '+')
	{
		cin>>letra;
		if (letra!= '+')
			pilha = push (pilha, letra);
	}

	cout<<"A palavra em ordem inversa eh:";
	while (pilha.indice_topo>=0)
	{
		cout << top(pilha);
		pilha = pop(pilha);
	}

	return 0;
}

Lines 1, 2 declare cin and cout that you use to do input/output later on.

Line 4-8 declare a data for yor stack. Its a record (struct in C++) that has 100 elements of type char and stack pointer that tracks the stack as it's used. It is used as an index into the arra of elements.

There are three things you can do to your stack, you can push an item onto it, pop an item that was previously pushed, and you can take a look at the top element.

The functions that follow implement the push, pop and top operations, and finally main reads stuff in from user and outputs it in reverse order by using the stack.

Lines 10-21 define the push function. It takes the stack data structure and the character you want to push. If the stack is not full, it increments the index, and puts the character passed in into the array of elements at the new index position.

Lines 23-30 have the pop function. It takes the stack data structure and just discards the top item.

Lines 32-38 have the top function. If the stack is not empty it returns the character that's on top of the stack; that is, the character at the index position.

Liness 40-62 have the test harness. It reads characters in and pushes them onto the stack until the user enters +, then it writes them all out in reverse order.