Banco De Dados

Pilha

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).

CONCEITOS

Para certas aplicações, tornam-se úteis estruturas de dados, constituídas por conjuntos de elementos organizados NÃO pelos VALORES DOS DADOS, mas em função de um determinado CRITÉRIO QUE REGULAMENTA A ENTRADA E A SAÍDA dos dados na estrutura.

LIFO: Last In, First Out – O primeiro elemento a sair da estrutura é último que nela entrou.

CRITÉRIO QUE DÁ ORIGEM À ESTRUTURA PILHA.

FIFO: First In, First Out – O primeiro a sair da estrutura é o primeiro que nela entrou.

CRITÉRIO QUE DÁ ORIGEM À ESTRUTURA FILA.

As operações básicas que se podem realizar sobre uma PILHA são:

Inicializar a pilha;

Verificar se a pilha está vazia;

Retornar o elemento que está no topo da pilha;

Inserir um elemento na pilha;

Retirar um elemento da pilha;

As operações básicas que se podem realizar sobre uma FILA são:

Inicializar a fila;

Verificar se a fila está vazia;

Inserir um elemento na fila;

Retirar um elemento da fila;

OVERFLOW e UNDERFLOW em Pilhas

3

Ao serem implementados no computador, os algoritmos de manipulação de pilhas em alocação seqüencial devem submeter-se às condições de programação.

· No caso, pilha é armazenada em um VETOR que deve ser dimensionado previamente;

· A pilha não pode exceder o TAMANHO MÁXIMO deste vetor

· Assim, deve-se controlar o crescimento da pilha testando o:

o LIMITE SUPERIOR

o LIMITE INFERIOR

Overflow = Pilha Cheia: ao tentar inserir mais um elemento na estrutura e esta não possui nodos disponíveis

Underflow = Pilha Vazia: ao tentar remover um elemento da estrutura e esta não possuí nenhum elemento.

4

Exercícios desenvolvidos na linguagem c

Tenho que fazer um exercício onde inicialmente vou ter n elementos (inserido pelo usuário). O número de elementos vai ser a quantidade de blocos existentes. Se n=5, então tenho os blocos 0, 1, 2, 3, 4. Primeira dúvida: Se tenho 5 elementos, e posso tirar qualquer uma da sua posição e colocar em qualquer outra posição, então não vou ter uma pilha e sim 5 pilhas??? Segunda dúvida: Já pesquisei muito no pai google, livros, mas não vi nada parecido. Todos os exemplos de pilha que vi, têm-se uma pilha onde se é inserido um elemento ou retirado, ou seja, pega-se apenas o elemento que vai ser inserido e no caso de retirado, sempre o topo da pilha. Meu problema é que tenho que definir o elemento que vou mover e a pilha de referência. EX: mover a acima b, onde a=2 e b=0. mover a acima b, onde a=1 e b=3. então a saída seria: 2 1 0**3 4 * = espaço vazio. Então não, sei como fazer essa referência, definir em qual pilha vou jogar o bloco a ser movido, como no exemplo onde o bloco 2 foi movido para cima do bloco 0 na pilha 0 e o bloco 1 foi movido para cima do bloco 3 na pilha 3 e as pilhas 1 e 2 ficaram vazias. Segue o código que já consegui fazer... [CODEBOX] /*Faça um programa que leia um arquivo de entrada, execute todos os *comandos presentes nesse arquivo e gere um arquivo de saída, no formato *definido anteriormente no desafio. */ /* Definições de movimento: *Os comandos válidos para o braço de robô manipular os blocos são listados *a seguir. Usa-se a para indicar o bloco em movimento a e b como bloco de *referência. *Mover a acima b: move o bloco a para cima do bloco b retornando *eventuais blocos que já estiverem sobre a ou b para as suas posições *originais. *Mover a topo b: coloca o bloco a no topo do monte onde está o bloco b *retornando eventuais blocos que já estiverem sobre a às suas posições *originais. *Empilhar a acima b: coloca o bloco a juntamente com todos os blocos que

5

*estiverem sobre ele em cima do bloco b, retornando eventuais blocos que *já estiverem sobre b as suas posições originais. *Empilhar a topo b: coloca o bloco a juntamente com todos os blocos que *estiverem sobre ele no topo do monte onde está o bloco b. *Encontrar maior: encontra o maior elemento da pilha mais alta e o *devolve para a posição inicial. *Sair: termina a execução. *Qualquer comando no qual a = b ou no qual a e b estejam na mesma pilha *de blocos é um comando ilegal e deve ser ignorado, não alterando a *configuração dos blocos. *RESTRIÇÃO: *Qualquer comando no qual a = b ou no qual a e b estejam na mesma pilha *de blocos é um comando ilegal e deve ser ignorado, não alterando a *configuração dos blocos. */

#include<stdio.h>

#include<stdlib.h>

#define MAX 5

struct pilha{

int entrada[MAX]; // numero de blocos

int mover_acima[1];

int mover_topo[1];

int empilhar_acima[1];

int empilhar_topo[1];

int encontrar_maior[1];

int topo;

int temp[MAX];

}modificar;

// Funções necessárias para o desafio.

int func_mover_acima();

int func_mover_topo();

int func_empilhar_acima();

int func_empilhar_topo();

int func_inicializa_pilha();

6

int func_pilha_vazia();

int func_sair();

int func_menu();

//Inicio do programa.

int main(void) {

printf("DESAFIO: MUNDO DOS BLOCOS\n");

func_menu();

}

//Fim do programa.

int func_menu() {

int op;

printf("\nEscolha o item desejado.\n\n");

printf("1 - Mover 'a' acima 'b'\n");

printf("2 - Mover 'a' topo 'b'\n");

printf("3 - Empilhar 'a' acima 'b'\n");

printf("4 - Empilhar 'a' topo 'b'\n");

printf("5 - Encontrar maior\n");

printf("6 - Sair\n");

printf("\nItem escolhido: ");

scanf("%d", &op);

switch (op) {

case 1:

system("cls");

func_mover_acima();

getchar();

getchar();

break;

7

case 2:

system("cls");

func_mover_topo();

getchar();

getchar();

break;

case 3:

system("cls");

func_empilhar_acima();

getchar();

getchar();

break;

case 4:

system("cls");

func_empilhar_topo();

getchar();

getchar();

break;

case 5:

printf("Funcao não implementada!!\n");

printf("Pressione qualquer tecla para sair");

getchar();

getchar();

break;

case 6:

func_sair();

break;

default:

printf("Opcao invalida");

}

}

8

int func_inicializa_pilha() {

modificar.topo = -1;

}

int func_pilha_vazia() {

if(modificar.topo == -1 )

return 1;

else

return 0;

}

int func_mover_acima(){

int x=0, y=0;

printf("Mover 'a' acima 'b'\n\n");

printf("Informe o bloco a ser movimentado: \n");

for (;x<MAX;x++){

scanf("%d", modificar.mover_acima[x]); // guarda bloco a ser movimentado

if ((x >= 0 || x < MAX)) {

printf("Informe o bloco de referencia: \n");

scanf("%d", modificar.mover_acima[y]); // guarda bloco de referência

if ((y >=0 || y < MAX)) {

if (x==y) {

printf("Blocos são iguai ou estao na mesma pilha\n");

printf("Nenhum alteracao será efetuada nos blocos\n");

printf("Pressione qualquer tecla para continuar");

getchar();

}

else {

printf("Código para empilhar a acima b aqui");

9

}

}

}

}

}

int func_mover_topo(){

printf("código aqui");

}

int func_empilhar_acima(){

printf("código aqui");

}

int func_empilhar_topo(){

printf("código aqui");

}int func_sair(){

printf("código aqui");

} Parti Gráfica do código

Várias áreas da ciência da computação usam domínios simples e abstratos para estudos analíticos e empíricos. Por exemplo, algumas das primeiras pesquisas de inteligência artificial nas áreas de planejamento e robótica usavam o mundo dos blocos, no qual um braço de robô realizava tarefas envolvendo a manipulação de blocos. O problema consiste em analisar uma série de comandos que instruem um braço de robô em como manipular os blocos que estão sobre uma mesa. Inicialmente, existemN (1< N < 25) blocos sobre a mesa (numerados de 0 aN-1), como mostra a figura a seguir. O problema começa com cada bloco na sua posição inicial sobre a mesa e, depois de uma série de comandos válidos, deve terminar em uma configuração final. Na figura a seguir é apresentado um exemplo para 6 blocos (N = 6), sendo (a) a configuração inicial e (b) a configuração final.

10

Entrada A entrada é composta de apenas um caso de teste. Cada caso de teste é composto de um número indeterminado de linhas. A primeira linha da entrada contém apenas um numero inteiro N, representando o numero inicial de blocos. As linhas seguintes contém cada uma um comando, que deve ser executado nas pilhas atuais de blocos. Os comandos possíveis são: (Usa-se A para indicar o bloco em movimento e B como bloco de referência.) *mover A acima B: move o bloco A diretamente acima do bloco B retornando eventuais blocos que já estiverem sobre A ou B para as suas posições originais. *mover A topo B: coloca o bloco A no topo da pilha onde está o bloco B retornando eventuais blocos que já estiverem sobre A para as suas posições originais. *empilhar A acima B: coloca o bloco A juntamente com todos os blocos que estiverem sobre ele em cima do bloco B, retornando eventuais blocos que já estiverem sobre B as suas posições originais. *empilhar A topo B: coloca o bloco A juntamente com todos os blocos que estiverem sobre ele no topo da pilha onde está o bloco B. *encontrar maior: encontra o bloco de maior número da pilha mais alta e o devolve para a posição inicial (Caso existam duas ou mais pilhas com o mesmo numero de blocos, deve retornar o maior bloco da pilha de menor valor. Por exemplo, se as pilhas 2 e 5 têm ambas 3 blocos cada, deve retornar o maior bloco da pilha 2). *sair: Indica o final da entrada.

Comandos com valores inválidos devem ser ignorados, não alterando as posições dos blocos. Um comando é inválido quando: *A é igual a B *A e B estão na mesma pilha *A,B < 0 *A,B >= N

11

Saída A saída deve ser composta de Nlinhas, que representam a configuração final do seu Mundo dos Blocos. Em cada linha deve aparecer o número da pilha seguida de dois pontos (:). Se existir pelo menos um bloco naquela posição, os dois pontos devem ser seguidos pela lista de blocos que aparecem naquela pilha separados por um espaço em branco.

Exemplo 1 1. Entrada: 2. 3. 6 4. mover 3 acima 2 5. mover 2 topo 4 6. empilhar 4 acima 0 7. empilhar 1 topo 3 8. encontra maior 9. sair 10. 11. 12. 13. Saída: 14. 15. 0: 0 2 16. 1: 17. 2: 18. 3: 3 1 19. 4: 4 20. 5: 5

Exemplo 2 1. Entrada: 2. 3. 8 4. mover 1 acima 0 5. mover 3 topo 0 6. mover 2 topo 0 7. mover 5 topo 4 8. mover 6 topo 4 9. mover 7 topo 4 10. encontra maior 11. sair 12. 13. 14. 15. Saída: 16. 17. 0: 0 1 2 18. 1: 19. 2: 20. 3: 3 21. 4: 4 5 6 7 22. 5: 23. 6:

12