Como fazer pilhas em pascal

[Gthang]

Ajudem me para um trabalho de Pilhas 😛

[M6]

Claro.

[Gthang]

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?

[M6]

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

[Gthang]

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

[M6]

Sim, isso é uma pilha LIFO.

[Gthang]

Podes me postar um programinha pa eu ver?

[M6]

Não.

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

[pwseo]

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 👍

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

[merlin3000]

Podes tentar dar uma vista de olhos aqui http://www.learn-programming.za.net/programming_pascal_learn14.html

[TheDark]

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

[M6]

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.

[TheDark]

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.

[M6]

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.

[pedrosorio]

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?

[M6]

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

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

[pedrosorio]

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

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

[TheDark]

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 👍

[M6]

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.

[TheDark]

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.