Estrutura de Dados Pilha by Aquiles Burlamaqui. Definição Uma pilha é uma das várias estruturas...

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 *