Pilhas - por push e pop?

Question

Eu queria saber por que usar os termos "push" e "pop" para adicionar / remover itens a partir de pilhas? Existe alguma metáfora física que causaram esses termos para ser comum?

A única sugestão que eu tenho é algo como um revista mola para uma arma , onde rodadas são "empurrados" para ele e pode ser "estourou", mas que parece um pouco improvável.

A segunda pergunta pilha trivialidade: Por que a maioria das CPUs implementar a pilha de chamadas como o crescimento para baixo na memória, em vez de para cima?

Answer 1

Eu acredito que a pilha de pratos de mola está correta, como a fonte para o impulso prazo e pop.

Em particular, a cafetaria Leste Campus Commons no MIT tinha pilhas de placas na estrutura 1957-1967 tempo de mola. Os termos push e pop teria sido em uso pelo Tech Model Railroad Club. Eu acho que essa é a origem.

The Tech Model Railroad Clube definitivamente influenciou o desenho de da Digital Equipment Corporation (DEC) PDP-6. O PDP-6 foi uma das primeiras máquinas a ter pilha orientado instruções no hardware. As instruções eram Push, POP, PUSHJ, POPJ.

http://ed-thelen.org/comp- hist / pdp-6.html # especial% 20Features

Answer 2

Para sua segunda pergunta, a Wikipedia tem um artigo sobre a filosofia CS que controla a pilha:

http://en.wikipedia.org/wiki/LIFO

E, pela primeira, também no wikipedia:

A metáfora usada com frequência é a idéia de uma pilha de placas em uma mola cafetaria pilha carregada. Em um tal pilha, somente a placa de topo é visível e acessível para o usuário, todos os outros placas permanecem ocultos. À medida que novas placas são adicionados, cada nova placa torna-se o parte superior da pilha, que esconde cada placa abaixo, que empurra a pilha de placas baixa. À medida que a placa de topo é removido a pilha, eles podem ser usados, o placas pop cópia de segurança, e a segunda placa torna-se na parte superior da pilha. Dois princípios importantes são ilustrado por esta metáfora: a última Em primeiro princípio Out é um; a O segundo é que o conteúdo da pilha estão escondidos. Apenas a placa de topo é visível, de modo a ver o que está no terceira placa, o primeiro e segundo placas terão de ser removidas. este também pode ser escrita como FILO-First In Last Out, ou seja, o registro inserido primeira será saiu no último.

Answer 3

Para a segunda pergunta:. Programadores Assembler em pequenos sistemas tendem a escrever código que começa em endereços baixos na memória, e crescer para endereços mais altos como mais código é adicionado

Devido a isso, fazendo uma pilha crescem para baixo permite que você comece a pilha no topo da memória física e permitir que as duas zonas de memória para crescer em direção ao outro. Este gerenciamento de memória simplifica neste tipo de ambiente trivial.

Mesmo em um sistema com segregadas ROM / alocações de dados RAM fixo são mais fáceis de construir do-se inferior e, assim, substituir a parte do código da explicação acima.

Embora tais sistemas de memória triviais são mais muito raros, a prática hardware continua como estabelecido.

Answer 4

Pense nisso como um dispensador de pez. Você pode empurrar um novo no topo. E, em seguida, colocá-la fora do topo.

Isso é sempre o que penso quando penso push e pop. (Embora provavelmente não muito histórica)

Você está se perguntando o que diabos são PEZ? Ver comentários.

Answer 5

Alliteration é sempre atraente (ver o que eu fiz lá?), E essas palavras são curtas, alliterative, e sugestivo. O mesmo vale para os antigos comandos BASIC olhada e puxão, que têm a vantagem extra do paralelo k de.

Uma metáfora física comum é um distribuidor de placa de cafetaria, onde uma pilha de placas de mola torna de modo que pode tomar uma placa de fora da parte superior, mas a próxima placa sobe para estar na mesma posição.

Answer 6

Re sua "segunda questão trivial": Eu vi inconsistência considerável na definição do que "up" e "down" média! Desde os primeiros dias, alguns fabricantes e autores desenhou diagramas de memória com endereços baixos no topo da página (presumivelmente imitando a ordem em que uma página é lida), enquanto outros colocam endereços de altura no topo da página (presumivelmente imitando coordenadas papel de gráfico ou os andares de um edifício).

É claro que o conceito de uma pilha (eo conceito de memória endereçável também) é independente de tais metáforas visuais. Pode-se implementar uma pilha que "cresce" em qualquer direção. Na verdade, eu vi frequentemente o truque abaixo (em implementações de nível bare-metal) usado para compartilhar uma região da memória entre duas pilhas:

+---+---+--------   -------+--+--+--+
|   |   |   ->   ...   <-  |  |  |  |
+---+---+--------   -------+--+--+--+
^                                   ^
Stack 1      both stacks      Stack 2
base        "grow" toward        base
              the middle

Assim, a minha resposta é que pilhas conceitualmente não crescer tanto "para baixo" ou "para cima", mas simplesmente crescer a partir de sua base. Uma pilha indivíduo pode ser implementada em qualquer direção (ou em não direção, se ele está usando uma representação ligada com a coleta de lixo, caso em que os elementos podem ser qualquer lugar em nodespace).

Answer 7

As respostas sobre desta página praticamente responder à pergunta direção pilha. Se eu tivesse que resumir, eu diria que é para baixo feito para manter a coerência com computadores antigos.

Answer 8

Eu acho que a história original surgiu por causa de alguns desenvolvedores vendo a pilha de placas (como você vê frequentemente em restaurantes buffet). Você empurrou uma nova placa para o topo da pilha, e você bateu um fora do topo também.

Answer 9

Como a pilhas crescentes para baixo na memória, lembre-se que quando se lida com estruturas de dados hierárquicos (árvores), a maioria dos programadores são feliz para desenhar uma em uma página com a base (ou tronco) no topo da página ...

Answer 10

Eu sei que esta discussão é muito velho, mas eu tenho um pensamento sobre a segunda pergunta:

Em minha mente, a pilha cresce, mesmo que os endereços de memória diminuir. Se você fosse escrever um monte de números em um pedaço de papel, você iria começar no canto superior esquerdo, com 0. Então você teria que aumentar os números indo para a esquerda para a direita, em seguida, de cima para baixo. Então diga a pilha é assim:

000 001 002 003 004     000 001 002 003 004     000 001 002 003 004
005 006 007 008 009     005 006 007 008 009     005 006 007 008 009
010 011 012 013 014     010 011 012 013 014     010 011 012 013 014
015 016 017 018 019     015 016 017 018 019     015 016 017 018 019
020 021 022 023 024     020 021 022 023 024     020 021 022 023 024
025 026 027 028 029     025 026 027 028 029     025 026 027 028 029

onde os números em negrito representam memória de pilha, e os números unbold representam endereços de memória que a pilha não está usando. Cada bloco dos mesmos números representa um estágio de um programa onde a pilha de chamadas tem crescido.

Mesmo que os endereços de memória estão se movendo para baixo, a pilha está crescendo para cima.

Da mesma forma, com a pilha de placas de mola,
se você tomou um prato fora do topo da pilha, você chamaria de que a primeira placa (menor número) certo? Mesmo pensei que é o mais alto para cima. Um programador pode até chamá-lo a placa zeroth.

Answer 11

Para a questão de por que as pilhas crescem para baixo, eu imagino que é usado para economizar memória.

Se você começar a partir do topo da memória de pilha (os endereços de maior valor) e trabalhar para baixo a zero, eu assumir a sua mais fácil de verificar se você tiver atingido $0x00000000 endereço de alocar uma variável para dar-lhe a altura máxima da pilha e verificar se está ou não ter atingido esse endereço.

Suponho que isso faz com que seja mais fácil de verificar se você está chegando ao fim de seu espaço endereçável como não importa quanta memória está disponível o limite da pilha é sempre vai ser $0x00000000.