• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Gthang

Como fazer pilhas em pascal

23 mensagens neste tópico

como e que faço um programa simples so pa explicar como funciona as pilhas em programaçao mas em pascal.

ainda nao dei isso , mas tenho de fazer uma apresentaçao . saber como faço um programinha a exeplificar o push e pop . fazer LIFO E FIFO etc. ok?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A forma mais simples é usar arrays para simular as pilhas, a forma mais "correcta"/dinâmica é usares listas.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

faço um vector e faço last in first out? mas isso nao e pilha ou é?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sim, isso é uma pilha LIFO.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não.

Não trabalho em Pascal há mais de uma década e não tenho nada assim comigo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Podes me postar um programinha pa eu ver?

Gthang, crias uma array dinâmica (por exemplo) e duas funções (push e pop) que operem na array... Se fizeres algum código talvez o resto das pessoas possam ajudar... agora, pedir o código desde o início nao é a melhor opção :thumbsup:

Uma opção mais correcta seria uma linked list, no entanto :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Podem explicar-me porque é que uma lista é mais indicada do que um array?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Uma lista é uma estrutura que não tem limite (a não ser o limite físico de memória do sistema) e um array tem um número limitado de posições.

Se usares um array tipicamente vais ter de andar com um identificador para saberes qual é a posição de topo. Podes usar a mesma técnica para uma lista, mas normalmente o último elemento aponta para nil/null sabes se estás no topo da pilha ou não.

PS: pessoalmente implementaria como lista e não como array, mas não há uma solução certa e uma errada aqui.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Uma lista é uma estrutura que não tem limite (a não ser o limite físico de memória do sistema) e um array tem um número limitado de posições.

Essa é uma das razões que me levam a crer que um array seria uma representação mais fiel de uma pilha: as arquitecturas que estudei até hoje todas têm uma dimensão pré-definida para a pilha. Outras razões são:

- Acesso aleatório mais eficiente. Podes querer aceder a posições relativas ao SP, o que com uma lista era dificultado pela sua natureza sequencial;

- Numa pilha não há remoções no meio da estrutura, que é a outra principal vantagem da lista (além do tamanho indefinido). Há apenas push e pop, sempre do último elemento da pilha, o que é perfeito para um array.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

TheDark, por acaso se for um FIFO o array é pior.

Das duas uma:

- ou metes o primeiro elemento na posição 1 e quando este salta tens de mover todos os outros de posição

- ou metes sempre o elemento mais novo na posição 1 e nesse caso casa vez que entra um novo elemento tens de empurrar todos os outros para a frente

Quanto ao acesso aleatório ser mais eficiente, isso não bem verdade. Na realidade, grosso modo, o array tem de manter uma estrutura que te permita chegar à posição que indicas. Ou seja, por trás tem apontadores para áreas de memória e um índice (ou uma forma de saber um indíce) para saber onde está o elemento de que necessitas.

Percorrer uma lista do inicio ao fim de forma sequencial é uma operação extremamente rápida, basta ver a quantidade de instruções que um processador consegue efectuar e que tudo não passa simplesmente de saber qual é a próxima área de memória.

E se a performance fosse um problema, há estruturas mais complexas baseadas em listas mais eficientes.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

TheDark, por acaso se for um FIFO o array é pior.

Quando se fala em pilhas não está subentendido LIFO?

Quanto ao acesso aleatório ser mais eficiente, isso não bem verdade. Na realidade, grosso modo, o array tem de manter uma estrutura que te permita chegar à posição que indicas. Ou seja, por trás tem apontadores para áreas de memória e um índice (ou uma forma de saber um indíce) para saber onde está o elemento de que necessitas.

Percorrer uma lista do inicio ao fim de forma sequencial é uma operação extremamente rápida, basta ver a quantidade de instruções que um processador consegue efectuar e que tudo não passa simplesmente de saber qual é a próxima área de memória.

E se a performance fosse um problema, há estruturas mais complexas baseadas em listas mais eficientes.

Hmm... Percorrer uma lista é bastante rápido, porque a "leitura" de um apontador e acesso à memória correspondente são muito rápidos, mas o acesso aleatório realiza-se em tempo constante (e muito pequeno pelas razões indicadas) no número de elementos... Porque é que não há-de ser mais eficiente?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Quando se fala em pilhas não está subentendido LIFO?

Não me parece.

Sempre aprendi que as pilhas podem ser de dois tipos: FIFO e LIFO.

Hmm... Percorrer uma lista é bastante rápido, porque a "leitura" de um apontador e acesso à memória correspondente são muito rápidos, mas o acesso aleatório realiza-se em tempo constante (e muito pequeno pelas razões indicadas) no número de elementos... Porque é que não há-de ser mais eficiente?

Creio que a coisa é idêntica para os apontadores (mas já lá vão uns anos disto :thumbsup:).

Não sei se o Pascal implementa a coisa da mesma forma que o C, mas é bem possível que no final a coisa funcione como no C, onde teres um array ou um apontador é quase irrelevante a esse nível: http://en.wikipedia.org/wiki/Pointer_%28computing%29#C_arrays

(no final tem uma referência ao Pascal mas não fala de comparação entre arrays e apontadores).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não me parece.

Sempre aprendi que as pilhas podem ser de dois tipos: FIFO e LIFO.

Sim, vocês é que sabem disto, só que imagino sempre uma pilha como uma pilha física de objectos em que só posso retirar o último objecto que coloquei (LIFO), às FIFO chamo filas, mas é uma nomenclatura minha =P

Creio que a coisa é idêntica para os apontadores (mas já lá vão uns anos disto :thumbsup:).

Não sei se o Pascal implementa a coisa da mesma forma que o C, mas é bem possível que no final a coisa funcione como no C, onde teres um array ou um apontador é quase irrelevante a esse nível: http://en.wikipedia.org/wiki/Pointer_%28computing%29#C_arrays

(no final tem uma referência ao Pascal mas não fala de comparação entre arrays e apontadores).

Um array funciona através de aritmética de apontadores em C, eu sei disso. Mas isso significa que se o array "a" está na memória 1000, e tens inteiros de 2 bytes então a[423] dá indicação para aceder a posição de memória 1000+2*423=1846 directamente.

Se falamos de listas ligadas, aceder o elemento nessa posição (começando na cabeça) equivale a avaliar o valor do apontador para o elemento 1, a aceder essa memória e avaliar o apontador para o elemento 2 (...) a aceder essa memória e avaliar o apontador para o elemento 423, aceder essa memória e retirar o inteiro que lá está.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Quando se fala em pilhas não está subentendido LIFO?

De facto, o próprio termo indica isso. Se tiveres uma pilha (de moedas, digamos - estão empilhadas, ou seja, umas em cima das outras) torna-se difícil retirar a moeda de baixo sem mexer nas outras todas.

Sempre aprendi que as pilhas podem ser de dois tipos: FIFO e LIFO.

Nunca ouvi falar dessas pilhas...

in http://en.wikipedia.org/wiki/Stack_%28data_structure%29

In computer science, a stack is a last in, first out(LIFO) abstract data type and data structure. A stack can have any abstract data type as an element, but is characterized by only two fundamental operations, the push and the pop. The push operation adds to the top of the list, hiding any items already on the stack, or initializing the stack if it is empty. The pop operation removes an item from the top of the list, and returns this value to the caller. A pop either reveals previously concealed items, or results in an empty list.

(...)

Java's library contains a Stack class that is a specialization of Vector---this could be considered a design flaw, since the inherited get() method from Vector ignores the LIFO constraint of the Stack.

Related data structures

The functionality of a queue and a stack can be combined in a deque data structure. Briefly put, a queue is a First In First Out (FIFO) data structure.

às FIFO chamo filas, mas é uma nomenclatura minha =P

E estás correctíssimo!

Hmm... Percorrer uma lista é bastante rápido, porque a "leitura" de um apontador e acesso à memória correspondente são muito rápidos, mas o acesso aleatório realiza-se em tempo constante (e muito pequeno pelas razões indicadas) no número de elementos... Porque é que não há-de ser mais eficiente?

Por muito rápido que seja, o acesso sequencial trata-se de incrementar um apontador, comparar com um determinado valor (o índice a que se quer chegar), e um jump - 3 instruções multiplicadas pelo índice pretendido. É-me difícil imaginar um cenário em que isto seja mais rápido que uma multiplicação (pelo tamanho do tipo dos objectos do array) e uma soma.

EDIT: lol, quando comecei a escrever isto não tinha visto os dois posts anteriores, parei no fim da página anterior :thumbsup:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Acho que esta discussão foi bastante enriquecedora, embora tenha deslizado um bocado da ajuda pedida no tópico inicial.

Efectivamente o facto dos array serem alocados como um bloco de memória contínua tornam-nos mais eficientes, é um "pormenor" importante.

Quanto às pilhas e filas, fui ver se estaria a fazer confusão, mas reparei que não sou o único que aprendeu que FIFO e LIFO são estruturas de dados do tipo pilha: http://pt.wikipedia.org/wiki/LIFO

Fiquei a meditar um bocado na nomenclatura descrita por vocês e a mesma faz algum sentido, pelo que me parece que pilha é apenas um termo mais genérico que inclui este tipo de estruturas de dados.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Quanto às pilhas e filas, fui ver se estaria a fazer confusão, mas reparei que não sou o único que aprendeu que FIFO e LIFO são estruturas de dados do tipo pilha: http://pt.wikipedia.org/wiki/LIFO

Ou estou a ver mal, ou só está lá a dizer que LIFO é equivalente a FILO. A única referência que vejo a FIFO é um link para o artigo correspondente.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O que estou a dizer é ambos são conhecidos quando se fala de pilhas.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ah, mas não está relacionado com o artigo da Wikipédia?

Acho que esta discussão foi bastante enriquecedora, embora tenha deslizado um bocado da ajuda pedida no tópico inicial.

Com um bocadinho de sorte ainda ajudou o OP a compreender melhor as pilhas e a fazer o trabalho :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Para quem estiver interessado, vou postar aqui uma stack (que é como quem diz, uma pilha) que fiz na aula de programação.

É um programa simples só com push e pop, e a estrutura de dados é uma lista ligada.

Se alguém quiser também tenho uma queue (uma fila).

Código:

program project1;
{$mode objfpc}{$H+}

uses crt;

type
apt=^registo;
registo= record
    seguinte:apt;
    nome:string;
end;

var
inicio_lista:apt; //apontador para o inicio da lista
fim_lista:apt;  //apontador para o fim da lista
opcao:integer;
nome:string;
queue:registo;

procedure enqueue (var queue: registo; nome:string);
var
novoreg,reg_seg,regtemp:^registo;

begin

new(novoreg);

novoreg^.nome := nome;
if inicio_lista = nil then
    begin
        novoreg^.seguinte := nil;
        inicio_lista := novoreg;
        fim_lista:= novoreg;
        end
    else

    begin
        novoreg^.seguinte := nil;
        regtemp:=fim_lista;
        regtemp^.seguinte:=novoreg;
        fim_lista := novoreg;
    end;

end;

Function empty(var queue: registo):boolean;

begin

if inicio_lista=nil then
    empty:=true
else
    empty:=false;
end;

Function dequeue(var queue:registo):string ;
var
    regtmp:^registo;

begin
    if empty (queue) then
        writeln('a queue esta vazia')
else
    begin
        regtmp:=inicio_lista;
        dequeue:=regtmp^.nome;
        inicio_lista:=regtmp^.seguinte;
        dispose(regtmp);   //liberta espaço da memoria
end;
end;

begin

inicio_lista:=nil;
fim_lista := nil;
repeat
clrscr;
writeln('1-Enqueue');
writeln('2-Dequeue');
writeln('3-Empty');
writeln('0-Terminar');
readln(opcao);
case opcao of
    1:begin
        writeln('nome');
        readln(nome);
        enqueue(queue,nome);
        end;
    2:begin
        nome:=dequeue(queue);
        writeln('nome:', nome);
        readln;
        end;
    3:begin
        if empty(queue)=true then writeln ('A queue esta vazia')
        else
        writeln('A queue nao esta vazia');
        readln;
        end;

    end;
until opcao=0;

end.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora