Pilhas: mudanças entre as edições

De Wiki Cursos IFPR Foz
Ir para navegaçãoIr para pesquisar
 
(43 revisões intermediárias pelo mesmo usuário não estão sendo mostradas)
Linha 1: Linha 1:
=Pilhas=
=Pilhas=
Uma '''pilha''' é  um conjunto ordenado de itens, na qual novos item podem ser inseridos ou extraídos a partir de seu '''topo''' <ref name="TENENBAUM">TENENBAUM, A. A.; LANGSAM, Y.; AUGENSTEIN, M.J. Estruturas de dados usando C, São Paulo: Makron Books, 1995.</ref>.
Uma '''pilha''' é  um conjunto ordenado de itens, na qual novos item podem ser inseridos ou extraídos a partir de seu '''topo''' <ref name="TENENBAUM">TENENBAUM, A. A.; LANGSAM, Y.; AUGENSTEIN, M.J. Estruturas de dados usando C, capítulo 2: A Pilha, São Paulo: Makron Books, 1995.</ref>.


[[Arquivo:Pilha.png]]
[[Arquivo:Pilha.png]]
Linha 7: Linha 7:


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.
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.
Uma '''pilha''' é também chamada de uma lista '''LIFO''' (''Last In First Out''), ou último que entra é o primeiro que sai.


==Operações primitivas com pilhas==
==Operações primitivas com pilhas==


As duas operações primitivas para lidar com pilhas são:
As duas operações primitivas para lidar com pilhas são <ref name="TENENBAUM"/>:
* '''''push''''': Quando um elemento é inserido, ou '''empilhado''', na pilha;
* '''''push''''': Quando um elemento é '''inserido''', ou '''empilhado''', na pilha;
*'''''pop''''': Quando um elemento é extraído, ou '''desempilhado''', da 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
Considere uma pilha '''s''' e um item '''i''', a função
Linha 22: Linha 26:
extrai um item do topo da pilha.
extrai um item do topo da pilha.


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.
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 pilha 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  
A operação  
Linha 28: Linha 35:
verifica se a pilha está vazia ou não.
verifica se a pilha está vazia ou não.


Outra operação que pode ser utilizada é verificar o item do topo da pilha, sem extrai-lo
==Imlementação de pilhas em linguagem C==
i = stacktop(s);
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.
 
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<ref name="TENENBAUM"/> <ref name="FEOFILOFF">FEOFILOFF, p. '''Projeto de algoritmos em C''': Pilhas. http://www.ime.usp.br/~pf/algoritmos/aulas/pilha.html</ref>.
 
[[Arquivo:PilhaVetor.png]]
 
===Implementando pilhas com vetores===
Uma implementação de uma pilha em C pode ser realizada a partir da declaração de uma estrutura com dois campos<ref>Wikipedia: Stack. http://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29#Implementation</ref>:
*Um '''vetor''' de items para armazenar os '''elementos da pilha''';
*Um '''inteiro''' que aponta para o '''topo da pilha''' dentro do vetor.
 
====Declaração da pilha====
Uma '''pilha''' de inteiros '''p''' pode ser declarada usando uma '''estrutura''', com um campo indicando o '''topo''' e outro com um '''vetor que implementa a pilha''':
<source lang="c">
#define TAM 100
struct pilha {
  int topo;
  int vetor[TAM];
} p;
</source>
:No programa principal, depois de declarada a variável de pilha o topo deve ser inicializado com zero.
 
====Operação push====
'''Insere item''' recebido como argumento no '''topo da pilha'''.
<source lang="c">
void push(struct pilha *p, int item)
{
  p->vetor[p->topo] = item;
  p->topo = p->topo + 1;
}
</source>
:Note que o campo '''p->vetor[]''' é um vetor que implementa a pilha e '''item''' é um parâmetro da função que recebe um item para ser inserido na pilha.
 
ou, de forma mais compacta
<source lang="c">
void push(struct pilha *p, int item)
{
  p->vetor[p->topo++] = item;
}
</source>
:Esta operação faz p->vetor[p->topo] = item e depois incrementa topo.
 
Poderia também fazer um '''controle de erro''' para verificar se o tamanho da pilha são será ultrapassado:
<source lang="c">
void push(struct pilha *p, int item)
{
    if (p->topo == TAM) {
        fputs("Erro: overflow\n", stderr);
        abort();
    } else
        p->vetor[p->topo++] = item;
}
</source>
 
====Operação pop====
'''Extrai e retorna item''' no topo da pilha.
<source lang="c">
int pop(struct pilha *p)
{
  p->topo = p->topo -1;
  return p->vetor[p->topo];
}
</source>
ou, de forma mais compacta
<source lang="c">
int pop(struct pilha *p)
{
  return p->vetor[--p->topo];
}
</source>
:Esta operação decrementa topo e depois retorna p->vetor[topo].
 
A operação '''pop()''' somente pode ser utilizada se a pilha não estiver vazia. Para isto, verificar antes com a função '''empty()'''.
<!--
Poderia também fazer um controle de erro para verificar se a pilha não está vazia:
<source lang="c">
void push(struct pilha *p, int item)
{
    if (p->topo == 0) {
        fputs("Erro: underfow\n", stderr);
        abort();
    } else
        return p->vetor[--p->topo];
}
</source>
-->
 
====Operação top====
'''Retorna o item''' do topo da pilha, '''sem extraí-lo'''.
<source lang="c">
int top(struct pilha *p)
{
  return p->vetor[p->topo - 1];
}
</source>
 
====Operação empty====
Verifica se a pilha está vazia.
<source lang="c">
int empty(struct pilha *p)
{
    if (p->topo == 0)
        return -1;
    else
        return 0;
}
</source>
 
==Exemplos de aplicação de pilhas==
 
===Análise de expressões com chaves, colchetes e parêntesis===
Um exemplo de '''aplicação de pilhas''' pode ser para verificar se uma '''expressão''' escrita com '''chaves, colchetes e parêntesis'''  aninhados está bem escrita.
 
Por exemplo, a expressão:
{a * (b + c) * [d / (e + f)]} + g
está escrita corretamente, pois, para cada chave, colchete ou parêntesis abertos, há um correspondente que se fecha.
 
Para verificar se a expressão está correta, cada chave, colchete ou parêntesis que for aberto deve ser adicionado no topo da pilha. Quando encontrar um elemento que fecha, deve-se verificar a pilha. Se a pilha estiver vazia o elemento que fecha não terá um correspondente que abre e a expressão será inválida. Se a pilha não estiver vazia, deve-se extrair o elemento que está no topo e verificar se ele corresponde ao elemento que fecha. Se ocorrer coincidência, continua a análise, senão a expressão será inválida. Quando o final da expressão for alcançado, a pilha deve estar vazia. Senão, é sinal que foram abertos chaves, colchetes ou parêntesis sem correspondentes para fechar.


===''Backtracking''===
Outro exemplo de aplicação para pilhas pode ser para guardar um caminho de volta (''backtracking''), por exemplo, quando percorremos um labirinto. A cada decisão tomada, guardamos a informação na pilha. Caso chegarmos a um fim de caminho, podemos retornar recuperando a informação de volta do topo da pilha.


===Notação polonesa ou posfixa===


Normalmente as calculadoras comuns usam a notação '''infixa''' para expressar uma operação matemática, por exemplo:
A + B
ou
A * (B + C)


<!-- <ref name="KERNIGHAN">KERNIGHAN, B.W.; RITCHIE, D.M. '''The C Programming Language''', Prentice Hall, 2<sup>o</sup> ed. 1978.</ref> -->
Algumas calculadoras, como as calculadoras HP, usam notação polonesa ou '''posfixa''' para expressar operações matemáticas, por exemplo:
A B +
ou
A B C + *


Uma calculadora HP tem uma pilha de tamanho 4 e funciona da seguinte maneira. Para efetuar a última expressão, primeiro insire A na pilha, depois B e depois C. Faço a operação de soma entre B e C e o resultado ocupa o topo da pilha. Faço a operação de multiplicação do topo da pilha com A.


<syntaxhighlight lang="c">
==Exercícios==
#Implementar uma pilha em linguagem C;
#Implementar uma função que receba uma '''string''', com uma '''expressão com chaves, colchetes e parêntesis''', e que faça a análise da expressão, verificando se as chaves, colchetes e parêntesis aninhados estão escritos corretamente, usando '''pilhas'''.


</syntaxhighlight>
;Exercício resolvido: Por aluno Luiz Felipe
<source lang="c">
#include <stdio.h>
#include <string.h>
#define TAM 100
struct lifo{
        int topo;
        int pilha[TAM];
};
void push(struct lifo *p, int item){
        if(p->topo == TAM){
                fputs("Erro: overflow\n", stderr);
        }else p->pilha[p->topo++] = item;
}
int empty(struct lifo *p){
        if(p->topo == 0) return -1;
        else return 0;
}
int pop(struct lifo *p){
        if(empty(p)){
                fputs("Nenhum elemento na pilha.\n", stdout);
        }else return p->pilha[--p->topo];
}
int top(struct lifo *p){
        if(empty(p)){
                fputs("Nenhum elemento na pilha.\n", stdout);
        }else return p->pilha[p->topo-1];
}
void main(){
        struct lifo arquivo;
        int abre, fecha, id, i;
        char expressao[TAM];
        i = abre = fecha = arquivo.topo = 0;
        printf("Informe uma expressao matematica com parenteses, chaves e/ou colchetes: ");
        fgets(expressao, TAM, stdin);
        for(i; expressao[i] != '\n'; i++){
                if((expressao[i] == '(') || (expressao[i] == '[') || (expressao[i] == '{')){
                        abre++;
                        if(expressao[i] == '(') id = 1;
                        else if(expressao[i] == '[') id = 2;
                        else id = 3;
                        push(&arquivo, id);
                }else if((expressao[i] == ')') || (expressao[i] == ']') || (expressao[i] == '}')){
                        fecha++;
                        if(expressao[i] == ')') id = 1;
                        else if(expressao[i] == ']') id = 2;
                        else id = 3;
                        if(id == top(&arquivo)) pop(&arquivo);
        }      }
        if(empty(&arquivo)){
                if(abre == fecha) printf("\nA expressao foi escrita corretamente!\n");
                else printf("\nHa parenteses, colchetes e/ou chaves fechando nada. Tente retira-los.\n");
        }else{
                printf("\nA expressao esta desordenada.\n");
                if(abre < fecha) printf("Alem disso, ha parenteses, colchetes e/ou chaves abertos sem fechar.\n");
                else if(abre > fecha) printf("Alem disso, ha mais parenteses, colchetes e/ou chaves de fechamento do que de abertura.\n");
        }
        if(i - abre - fecha < abre + fecha + 1) printf("Apenas um observacao e uma sugestao: os parenteses, colche... voce sabe. Ha mais do que o necessario. Entao, porque nao os tira logo da expressao?\n");
}
</source>


==Referências==
==Referências==

Edição atual tal como às 22h29min de 3 de outubro 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.

Uma pilha é também chamada de uma lista LIFO (Last In First Out), ou último que entra é o primeiro que sai.

Operações primitivas com pilhas

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

  • 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 pilha 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.

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.

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[1] [2].

Implementando pilhas com vetores

Uma implementação de uma pilha em C pode ser realizada a partir da declaração de uma estrutura com dois campos[3]:

  • Um vetor de items para armazenar os elementos da pilha;
  • Um inteiro que aponta para o topo da pilha dentro do vetor.

Declaração da pilha

Uma pilha de inteiros p pode ser declarada usando uma estrutura, com um campo indicando o topo e outro com um vetor que implementa a pilha: 

#define TAM 100
struct pilha {
  int topo;
  int vetor[TAM];
} p;
No programa principal, depois de declarada a variável de pilha o topo deve ser inicializado com zero.

Operação push

Insere item recebido como argumento no topo da pilha. 

void push(struct pilha *p, int item)
{
   p->vetor[p->topo] = item;
   p->topo = p->topo + 1;
}
Note que o campo p->vetor[] é um vetor que implementa a pilha e item é um parâmetro da função que recebe um item para ser inserido na pilha.

ou, de forma mais compacta 

void push(struct pilha *p, int item)
{
   p->vetor[p->topo++] = item;
}
Esta operação faz p->vetor[p->topo] = item e depois incrementa topo.

Poderia também fazer um controle de erro para verificar se o tamanho da pilha são será ultrapassado: 

void push(struct pilha *p, int item)
{
    if (p->topo == TAM) {
        fputs("Erro: overflow\n", stderr);
        abort();
    } else
        p->vetor[p->topo++] = item;
}

Operação pop

Extrai e retorna item no topo da pilha. 

int pop(struct pilha *p)
{
   p->topo = p->topo -1;
   return p->vetor[p->topo];
}

ou, de forma mais compacta 

int pop(struct pilha *p)
{
   return p->vetor[--p->topo];
}
Esta operação decrementa topo e depois retorna p->vetor[topo].

A operação pop() somente pode ser utilizada se a pilha não estiver vazia. Para isto, verificar antes com a função empty().

Operação top

Retorna o item do topo da pilha, sem extraí-lo. 

int top(struct pilha *p)
{
   return p->vetor[p->topo - 1];
}

Operação empty

Verifica se a pilha está vazia. 

int empty(struct pilha *p)
{
    if (p->topo == 0) 
        return -1;
    else
        return 0;
}

Exemplos de aplicação de pilhas

Análise de expressões com chaves, colchetes e parêntesis

Um exemplo de aplicação de pilhas pode ser para verificar se uma expressão escrita com chaves, colchetes e parêntesis aninhados está bem escrita.

Por exemplo, a expressão: 

{a * (b + c) * [d / (e + f)]} + g

está escrita corretamente, pois, para cada chave, colchete ou parêntesis abertos, há um correspondente que se fecha.

Para verificar se a expressão está correta, cada chave, colchete ou parêntesis que for aberto deve ser adicionado no topo da pilha. Quando encontrar um elemento que fecha, deve-se verificar a pilha. Se a pilha estiver vazia o elemento que fecha não terá um correspondente que abre e a expressão será inválida. Se a pilha não estiver vazia, deve-se extrair o elemento que está no topo e verificar se ele corresponde ao elemento que fecha. Se ocorrer coincidência, continua a análise, senão a expressão será inválida. Quando o final da expressão for alcançado, a pilha deve estar vazia. Senão, é sinal que foram abertos chaves, colchetes ou parêntesis sem correspondentes para fechar.

Backtracking

Outro exemplo de aplicação para pilhas pode ser para guardar um caminho de volta (backtracking), por exemplo, quando percorremos um labirinto. A cada decisão tomada, guardamos a informação na pilha. Caso chegarmos a um fim de caminho, podemos retornar recuperando a informação de volta do topo da pilha.

Notação polonesa ou posfixa

Normalmente as calculadoras comuns usam a notação infixa para expressar uma operação matemática, por exemplo: 

A + B

ou 

A * (B + C)

Algumas calculadoras, como as calculadoras HP, usam notação polonesa ou posfixa para expressar operações matemáticas, por exemplo: 

A B +

ou 

A B C + *

Uma calculadora HP tem uma pilha de tamanho 4 e funciona da seguinte maneira. Para efetuar a última expressão, primeiro insire A na pilha, depois B e depois C. Faço a operação de soma entre B e C e o resultado ocupa o topo da pilha. Faço a operação de multiplicação do topo da pilha com A.

Exercícios

  1. Implementar uma pilha em linguagem C;
  2. Implementar uma função que receba uma string, com uma expressão com chaves, colchetes e parêntesis, e que faça a análise da expressão, verificando se as chaves, colchetes e parêntesis aninhados estão escritos corretamente, usando pilhas.
Exercício resolvido
Por aluno Luiz Felipe
#include <stdio.h>
#include <string.h>
#define TAM 100
struct lifo{
        int topo;
        int pilha[TAM];
};
void push(struct lifo *p, int item){
        if(p->topo == TAM){
                fputs("Erro: overflow\n", stderr);
        }else p->pilha[p->topo++] = item;
}
int empty(struct lifo *p){
        if(p->topo == 0) return -1;
        else return 0;
}
int pop(struct lifo *p){
        if(empty(p)){
                fputs("Nenhum elemento na pilha.\n", stdout);
        }else return p->pilha[--p->topo];
}
int top(struct lifo *p){
        if(empty(p)){
                fputs("Nenhum elemento na pilha.\n", stdout);
        }else return p->pilha[p->topo-1];
}
void main(){
        struct lifo arquivo;
        int abre, fecha, id, i;
        char expressao[TAM];
        i = abre = fecha = arquivo.topo = 0;
        printf("Informe uma expressao matematica com parenteses, chaves e/ou colchetes: ");
        fgets(expressao, TAM, stdin);
        for(i; expressao[i] != '\n'; i++){
                if((expressao[i] == '(') || (expressao[i] == '[') || (expressao[i] == '{')){
                        abre++;
                        if(expressao[i] == '(') id = 1;
                        else if(expressao[i] == '[') id = 2;
                        else id = 3;
                        push(&arquivo, id);
                }else if((expressao[i] == ')') || (expressao[i] == ']') || (expressao[i] == '}')){
                        fecha++;
                        if(expressao[i] == ')') id = 1;
                        else if(expressao[i] == ']') id = 2;
                        else id = 3;
                        if(id == top(&arquivo)) pop(&arquivo);
        }       }
        if(empty(&arquivo)){
                if(abre == fecha) printf("\nA expressao foi escrita corretamente!\n");
                else printf("\nHa parenteses, colchetes e/ou chaves fechando nada. Tente retira-los.\n");
        }else{
                printf("\nA expressao esta desordenada.\n");
                if(abre < fecha) printf("Alem disso, ha parenteses, colchetes e/ou chaves abertos sem fechar.\n");
                else if(abre > fecha) printf("Alem disso, ha mais parenteses, colchetes e/ou chaves de fechamento do que de abertura.\n");
        }
        if(i - abre - fecha < abre + fecha + 1) printf("Apenas um observacao e uma sugestao: os parenteses, colche... voce sabe. Ha mais do que o necessario. Entao, porque nao os tira logo da expressao?\n");
}

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
  3. ↑ Wikipedia: Stack. http://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29#Implementation

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

Disponível em “http://wiki.foz.ifpr.edu.br/wiki/index.php?title=Pilhas&oldid=4869”