Pilhas: mudanças entre as edições

De Wiki Cursos IFPR Foz
Ir para navegaçãoIr para pesquisar
Linha 35: Linha 35:
==Exemplo de aplicação de pilhas==
==Exemplo de aplicação de pilhas==


==Imlementação de pilhas em linguagem C==
Antes de programar a solução de um problema usando '''pilhas''', é preciso definir como a pilha será representada na linguagem de programação que estamos utilizando<ref name="TENENBAUM"/>.


Na linguagem C, uma das maneiras de implememtar uma '''pilha''' é utilizando '''vetores'''. Contudo, pilhas e vetores são tipos de dados diferentes:
*Uma '''pilha''' é um conjunto ordenado de itens de tamanho é variável e, a princípio, não tem limite de tamanho.
*Um '''vetor''', por sua vez, é um conjunto ordenado de itens, cujo tamanho é fixado na declaração do vetor.


<!-- <ref name="KERNIGHAN">KERNIGHAN, B.W.; RITCHIE, D.M. '''The C Programming Language''', Prentice Hall, 2<sup>o</sup> ed. 1978.</ref> -->
Entretando, podemos utilizar um vetor para implementar uma pilha, desde que este vetor seja declarado suficientemente grande para conter a pilha que pretendemos implementar. Uma extremidade do vetor será o final fixo da pilha, enquanto o topo da pilha se desloca constantemente a medida que elementos são inseridos ou extraídos da pilha.


<ref name="FEOFILOFF">FEOFILOFF, p. '''Projeto de algoritmos em C''': Pilhas. http://www.ime.usp.br/~pf/algoritmos/aulas/pilha.html</ref>


<syntaxhighlight lang="c">
<syntaxhighlight lang="c">

Edição das 13h25min de 19 de setembro de 2014

Pilhas

Uma pilha é um conjunto ordenado de itens, na qual novos item podem ser inseridos ou extraídos a partir de seu topo [1].

Uma pilha é um objeto dinâmico, constantemente mutável a partir da inserção ou extração de itens, sempre a partir de seu topo.

Quando um novo item é inserido na pilha, ele passa a ocupar seu topo. Neste caso, o topo é deslocado para cima de modo a corresponder ao novo primeiro elemento. Quando um item é removido, o topo da pilha é deslocado para baixo, para apontar ao novo primeiro elemento.

Operações primitivas com pilhas [1]

As duas operações primitivas para lidar com pilhas são:

  • push: Quando um elemento é inserido, ou empilhado, na pilha;
  • pop: Quando um elemento é extraído, ou desempilhado, da pilha.
Funções para operar com pilhas

Considere uma pilha s e um item i, a função

push(s, i);

insere o item na pilha.

Por sua vez a função

i = pop(s);

extrai um item do topo da pilha.

Outra operação que pode ser utilizada é verificar o item do topo da pilha, sem extrai-lo

i = top(s);

Não existe um limite máximo para o número de item em uma pilha. Entretanto, se uma tiver um só elemento e ele for extraído, teremos a pilha vazia. Portanto, antes de utilizar o operador pop, precisamos verificar se a pilha não está vazia.

A operação

empty(s);

verifica se a pilha está vazia ou não.

Exemplo de aplicação de pilhas

Imlementação de pilhas em linguagem C

Antes de programar a solução de um problema usando pilhas, é preciso definir como a pilha será representada na linguagem de programação que estamos utilizando[1].

Na linguagem C, uma das maneiras de implememtar uma pilha é utilizando vetores. Contudo, pilhas e vetores são tipos de dados diferentes:

  • Uma pilha é um conjunto ordenado de itens de tamanho é variável e, a princípio, não tem limite de tamanho.
  • Um vetor, por sua vez, é um conjunto ordenado de itens, cujo tamanho é fixado na declaração do vetor.

Entretando, podemos utilizar um vetor para implementar uma pilha, desde que este vetor seja declarado suficientemente grande para conter a pilha que pretendemos implementar. Uma extremidade do vetor será o final fixo da pilha, enquanto o topo da pilha se desloca constantemente a medida que elementos são inseridos ou extraídos da pilha.


[2]

Referências

  1. 1,0 1,1 1,2 TENENBAUM, A. A.; LANGSAM, Y.; AUGENSTEIN, M.J. Estruturas de dados usando C, capítulo 2: A Pilha, São Paulo: Makron Books, 1995.
  2. FEOFILOFF, p. Projeto de algoritmos em C: Pilhas. http://www.ime.usp.br/~pf/algoritmos/aulas/pilha.html

--Evandro.cantu (discussão) 16h49min de 17 de julho de 2014 (BRT)