Embed Size (px)
Citation preview
Estrutura de Dados
Pilha
by Aquiles Burlamaqui
Definição
Uma pilha é uma das várias estruturas de dados que admitem remoção de elementos e inserção de novos elementos. Mais especificamente, uma pilha (= stack) é uma estrutura sujeita à seguinte regra de operação: sempre que houver uma remoção, o elemento removido é o que está na estrutura há menos tempo.
Em outras palavras, o primeiro objeto a ser inserido na pilha é o último a ser removido. Essa política é conhecida pela sigla LIFO (= Last-In-First-Out).
Analise de Código
Execute os passos:1) Baixar os arquivos pilha.h, pilha.c e main.c
2) Gerar a biblioteca pilha.o
3) Compilar o main.c
4) Executar o main.c e ententer o seu funcionamento;
5) Entender o pilha.c (funções push e pop)
6) Desenhar uma memória e fazer um passo a passo da execução desse programa e as mudanças ocorridas na memória.
7) Construir uma função para retornar o tamanho da pilha.
8) Utilizar o comando free para liberar a memória durante o pop().
pilha.h
pilha.c
main.c
Execução - main
pilha p1;
p1.tamanho = 0;
p1.topo = NULL;
push(10,&p1);
push(15,&p1);
push(20,&p1);
pop(&p1);
pop(&p1);
pop(&p1);
pop(&p1;
tamanho topo *
p1
??
Execução - main
pilha p1;
p1.tamanho = 0;
p1.topo = NULL;
push(10,&p1);
push(15,&p1);
push(20,&p1);
pop(&p1);
pop(&p1);
pop(&p1);
pop(&p1;
tamanho topo *
p1
0?
Execução - main
pilha p1;
p1.tamanho = 0;
p1.topo = NULL;
push(10,&p1);
push(15,&p1);
push(20,&p1);
pop(&p1);
pop(&p1);
pop(&p1);
pop(&p1;
tamanho topo *
p1
0
Execução - main
pilha p1;
p1.tamanho = 0;
p1.topo = NULL;
push(10,&p1);
push(15,&p1);
push(20,&p1);
pop(&p1);
pop(&p1);
pop(&p1);
pop(&p1;
tamanho topo *
p1
0
Execução - push(10,&p1);void push(int item, pilha *p) {
if(p->topo==NULL) {
p->tamanho = 1;
p->topo = malloc(sizeof(elemento));
p->topo->valor = item;
p->topo->proximo = NULL;
printf("Tava vazio, coloquei o primeiro: %i\n",item);
}else {
elemento * temp = p->topo;
p->topo = malloc(sizeof(elemento));
p->topo->valor = item;
p->topo->proximo = temp;
printf("Empilhei mais um...:%i\n",item);
}
}
tamanho topo *
p1
0
VERDADEIRO
Execução - push(10,&p1);void push(int item, pilha *p) {
if(p->topo==NULL) {
p->tamanho = 1;
p->topo = malloc(sizeof(elemento));
p->topo->valor = item;
p->topo->proximo = NULL;
printf("Tava vazio, coloquei o primeiro: %i\n",item);
}else {
elemento * temp = p->topo;
p->topo = malloc(sizeof(elemento));
p->topo->valor = item;
p->topo->proximo = temp;
printf("Empilhei mais um...:%i\n",item);
}
}
tamanho topo *
p1
1
Execução - push(10,&p1);void push(int item, pilha *p) {
if(p->topo==NULL) {
p->tamanho = 1;
p->topo = malloc(sizeof(elemento));
p->topo->valor = item;
p->topo->proximo = NULL;
printf("Tava vazio, coloquei o primeiro: %i\n",item);
}else {
elemento * temp = p->topo;
p->topo = malloc(sizeof(elemento));
p->topo->valor = item;
p->topo->proximo = temp;
printf("Empilhei mais um...:%i\n",item);
}
}
tamanho topo *
p1
1
?
valor proximo *
?
Execução - push(10,&p1);void push(int item, pilha *p) {
if(p->topo==NULL) {
p->tamanho = 1;
p->topo = malloc(sizeof(elemento));
p->topo->valor = item;
p->topo->proximo = NULL;
printf("Tava vazio, coloquei o primeiro: %i\n",item);
}else {
elemento * temp = p->topo;
p->topo = malloc(sizeof(elemento));
p->topo->valor = item;
p->topo->proximo = temp;
printf("Empilhei mais um...:%i\n",item);
}
}
tamanho topo *
p1
1
10
valor proximo *
?
Execução - push(10,&p1);void push(int item, pilha *p) {
if(p->topo==NULL) {
p->tamanho = 1;
p->topo = malloc(sizeof(elemento));
p->topo->valor = item;
p->topo->proximo = NULL;
printf("Tava vazio, coloquei o primeiro: %i\n",item);
}else {
elemento * temp = p->topo;
p->topo = malloc(sizeof(elemento));
p->topo->valor = item;
p->topo->proximo = temp;
printf("Empilhei mais um...:%i\n",item);
}
}
tamanho topo *
p1
1
10
valor proximo *
Execução - main
pilha p1;
p1.tamanho = 0;
p1.topo = NULL;
push(10,&p1);
push(15,&p1);
push(20,&p1);
pop(&p1);
pop(&p1);
pop(&p1);
pop(&p1;
tamanho topo *
p1
1
10
valor proximo *
Execução - main
tamanho topo *
p1
1
10
valor proximo *
void push(int item, pilha *p) {
if(p->topo==NULL) {
p->tamanho = 1;
p->topo = malloc(sizeof(elemento));
p->topo->valor = item;
p->topo->proximo = NULL;
printf("Tava vazio, coloquei o primeiro: %i\n",item);
}else {
elemento * temp = p->topo;
p->topo = malloc(sizeof(elemento));
p->topo->valor = item;
p->topo->proximo = temp;
printf("Empilhei mais um...:%i\n",item);
}
}
FALSO
Execução - main
tamanho topo *
p1
1
10
valor proximo *
void push(int item, pilha *p) {
if(p->topo==NULL) {
p->tamanho = 1;
p->topo = malloc(sizeof(elemento));
p->topo->valor = item;
p->topo->proximo = NULL;
printf("Tava vazio, coloquei o primeiro: %i\n",item);
}else {
elemento * temp = p->topo;
p->topo = malloc(sizeof(elemento));
p->topo->valor = item;
p->topo->proximo = temp;
printf("Empilhei mais um...:%i\n",item);
}
}
temp
Execução - maintamanho topo *
p1
1
10
valor proximo *
void push(int item, pilha *p) {
if(p->topo==NULL) {
p->tamanho = 1;
p->topo = malloc(sizeof(elemento));
p->topo->valor = item;
p->topo->proximo = NULL;
printf("Tava vazio, coloquei o primeiro: %i\n",item);
}else {
elemento * temp = p->topo;
p->topo = malloc(sizeof(elemento));
p->topo->valor = item;
p->topo->proximo = temp;
printf("Empilhei mais um...:%i\n",item);
}
}
temp
?
valor proximo *
?
Execução - maintamanho topo *
p1
1
10
valor proximo *
void push(int item, pilha *p) {
if(p->topo==NULL) {
p->tamanho = 1;
p->topo = malloc(sizeof(elemento));
p->topo->valor = item;
p->topo->proximo = NULL;
printf("Tava vazio, coloquei o primeiro: %i\n",item);
}else {
elemento * temp = p->topo;
p->topo = malloc(sizeof(elemento));
p->topo->valor = item;
p->topo->proximo = temp;
printf("Empilhei mais um...:%i\n",item);
}
}
temp
15
valor proximo *
?
Execução - maintamanho topo *
p1
1
10
valor proximo *
void push(int item, pilha *p) {
if(p->topo==NULL) {
p->tamanho = 1;
p->topo = malloc(sizeof(elemento));
p->topo->valor = item;
p->topo->proximo = NULL;
printf("Tava vazio, coloquei o primeiro: %i\n",item);
}else {
elemento * temp = p->topo;
p->topo = malloc(sizeof(elemento));
p->topo->valor = item;
p->topo->proximo = temp;
printf("Empilhei mais um...:%i\n",item);
}
}
temp
15
valor proximo *
