Lesson24

Estruturas lineares

As filas e as pilhas são duas estruturas dados muito utilizadas e que, tal como os tuplos e as listas, têm os seus elementos organizados em sequência, sendo por isso conhecidas por estruturas de dados lineares.

Pilhas

Uma pilha é uma estrutura de dados constituída por uma sequência de elementos, em que os elementos podem ser removidos pela ordem inversa da inserção, i.e., LIFO (last in first out). Em geral não podemos aceder ou inspeccionar elementos arbitrários numa pilha, apenas temos acesso ao topo da mesma.

Vejamos então como definir o TAD pilha e as suas operações básicas.

• Construtores:
  • pilha_nova: {} --> pilha, permite criar uma pilha vazia, i.e., sem elementos, um tipo de construtor típico em estruturas dinâmicas e que já utilizámos algumas vezes (e.g., listas em Python);
  • Podemos ter outros construtores, e.g., um construtor que recebe uma lista ou um tuplo e que constrói uma pilha a partir dessa sequência de elementos.
• Reconhecedores:
  • e_pilha: universal --> booleano, dada um qualquer valor passado por argumento decide se este é ou não uma pilha;
  • pilha_vazia: pilha --> booleano, dada uma pilha decide se a mesma está ou não vazia.
• Selectores:
  • pilha_topo: pilha --> elemento, dada uma pilha retorna o elemento que está no topo, se a pilha estiver vazia o comportamento é indefinido (aka top).
• Modificadores (caso em que a pilha é um tipo mutável):
  • pilha_retira: pilha --> pilha, dada uma pilha retira o elemento que está no topo e retorna a pilha, se a pilha estiver vazia o comportamento é indefinido (aka pop);
  • pilha_empurra: pilha x elemento --> pilha, dada uma pilha e um elemento coloca esse elemento, empurra para, o topo da pilha, e retorna a pilha (aka push);
  • Notar que estas operações podem também ser definidas como selectores no caso da pilha ser um tipo imutável, caso em que retornam a pilha resultante mas não modificam a pilha passada por parâmetro.
• Testes:
  • pilha_igual: pilha x pilha --> booleano, dadas duas pilhas toma decide se as mesmas são ou não iguais.

Vejamos a axiomatização do TAD pilha:

e_pilha(pilha_nova())
e_pilha(pilha_empurra(p,e))              # para quaisquer pilha p e elemento e
e_pilha(pilha_retira(p))                 # para qualquer pilha p não vazia
pilha_vazia(pilha_nova())
not(pilha_vazia(pilha_empurra(p,e)))     # para quaisquer pilha p e elemento e
pilha_topo(pilha_empurra(p,e)) == e      # para quaisquer pilha p e elemento e
pilha_retira(pilha_empurra(p,e)) == p    # para quaisquer pilha p e elemento e
pilha_igual(pilha_nova(),pilha_nova())
pilha_igual(p, q) \
    if not(pilha_vazia(p)) and not(pilha_vazia(q))\
        and pilha_topo(p) == pilha_topo(q)\
        and pilha_igual(pilha_retira(p), pilha_retira(q)) # para quaisquer pilhas p e q

Podemos escolher para representação interna uma lista, em que o último elemento corresponde ao topo da pilha.

Exercício 1: Realização das operações básicas do TAD pilha, incluindo testes relativos à axiomatização recorrendo ao módulo doctest.

Exercício 2: Comparar a eficiência das operações pilha_empurra e pilha_retira tendo em conta a representação interna descrita acima e a representação interna alternativa, também sobre listas, mas em que o topo da pilha é o primeiro elemento da lista.

Exercício 3: Implementar o TAD pilha recorrendo à programação com objectos.

Exercício 4: Recorrendo ao TAD pilha, implemente uma calculadora de pilha.

Filas

Uma fila é uma estrutura de dados constituída por sequência de elementos, em que os elementos podem ser removidos pela ordem de inserção, i.e., FIFO (first in first out). Em geral não podemos aceder ou inspeccionar elementos arbitrários numa fila, apenas temos acesso ao primeiro elemento da mesma.

Vejamos então como definir o TAD fila e as suas operações básicas.

• Construtores:
  • fila_nova: {} --> fila, permite criar uma fila vazia, i.e., sem elementos;
  • Podemos ter outros construtores, e.g., um construtor que recebe uma lista ou um tuplo e que constrói uma fila a partir dessa sequência de elementos.
• Reconhecedores:
  • e_fila: universal --> booleano, dada um qualquer valor passado por argumento decide se este é ou não uma fila;
  • fila_vazia: fila --> booleano, dada uma fila decide se a mesma está ou não vazia.
• Selectores:
  • fila_inicio: fila --> elemento, dada uma fila retorna o elemento que está no início, se a fila estiver vazia o comportamento é indefinido (aka first);
  • fila_comprimento: fila --> int, dada uma fila retorna o número de elementos na mesma.
• Modificadores (caso em que a fila é um tipo mutável):
  • fila_retira: fila --> fila, dada uma fila retira o elemento que está no início e retorna a fila, se a fila estiver vazia o comportamento é indefinido (aka dequeue);
  • fila_coloca: fila x elemento --> fila, dada uma fila e um elemento coloca esse elemento no fim da fila, e retorna a fila (aka queue);
  • Notar que estas operações podem também ser definidas como selectores no caso da fila ser um tipo imutável, caso em que retornam a fila resultante mas não modificam a fila passada por parâmetro.
• Testes:
  • fila_igual: fila x fila --> booleano, dadas duas filas toma decide se as mesmas são ou não iguais.
• Transformadores:
  • fila_para_lista: fila --> lista, dada uma fila retorna uma lista com os elementos na fila, pela mesma ordem.

Vejamos a axiomatização do TAD fila:

e_fila(fila_nova())
e_fila(fila_coloca(f,e))              # para quaisquer fila f e elemento e
e_fila(fila_retira(f))                # para qualquer fila f não vazia
fila_vazia(fila_nova())
not(fila_vazia(fila_coloca(f,e)))     # para quaisquer fila f e elemento e
fila_inicio(fila_coloca(f,e)) == e    # para quaisquer fila f vazia e elemento e
fila_inicio(fila_coloca(f,e)) == fila_inicio(f) # para quaisquer fila f nao vazia e elemento e
fila_retira(fila_coloca(f,e)) == fila_nova() # para quaisquer fila f vazia e elemento e
fila_retira(fila_coloca(f,e)) == fila_coloca(fila_retira(f), e) # para quaisquer fila f nao vazia e elemento e
fila_comprimento(fila_nova()) == 0
fila_comprimento(fila_coloca(f,e)) == 1 + fila_comprimento(f) # para quaisquer fila f e elemento e
fila_igual(fila_nova(),fila_nova())
fila_igual(f, g) \
    if not(fila_vazia(f)) and not(fila_vazia(g))\
        and fila_topo(f) == fila_inicio(g)\
        and fila_igual(fila_retira(f), fila_retira(g)) # para quaisquer filas f e g

Podemos escolher para representação interna uma lista, em que o elemento no início da fila está na primeira posição da lista e o elemento no final da fila está na última posição.

Exercício 1: Realização das operações básicas do TAD fila, incluindo testes relativos à axiomatização recorrendo ao módulo doctest.

Exercício 2: Assumindo que sabemos o número máximo de elementos a guardar na fila, parâmetro dado ao construtor, proponha uma realização do TAD fila que recorra a um array circular como representação interna. Quais as vantagens em termos de eficiência em relação à representação interna considerada anteriormente?

Exercício 3: Implementar o TAD fila recorrendo à programação com objectos.

Exercício 4: Proponha um TAD que suporte simultaneamente o comportamento de uma fila e o comportamento de uma pilha.

Representação gráfica

Em muitas aplicações é desejável termos uma interface gráfica, como é o caso com aplicações de simulação em que é desejável conseguirmos observar a simulação.

Vimos um exemplo de interface gráfica numa das soluções propostas para o segundo projecto, em que fizemos uso da plataforma pygame.

Entre muitas possíveis, uma outra alternativa é o módulo desenvolvido por John Zelle e que pode ser obtida em http://mcsp.wartburg.edu/zelle/python/graphics.py, cuja documentação está disponível em http://mcsp.wartburg.edu/zelle/python/graphics/graphics/index.html.

Exemplo:

>>> from graphics import *  
>>> j = GraphWin('janela', 640, 480)
>>> o1 = Circle(Point(80, 80), 30)
>>> o2 = Rectangle(Point(300,300), Point(400,400))
>>> o1.draw(j)
>>> o2.draw(j)
>>> t1 = Text(Point(350,350), 'FP2015')
>>> t1.draw(j)

Notar que as bibliotecas para obtermos representações gráficas vistas até agora são diferentes das bibliotecas normalmente utilizadas para criar interfaces gráficas como utilizamos em muitas aplicações, onde temos botões, menus, caixas de texto, etc. Para esse fim existem módulos/bibliotecas que disponibilizam componentes que nos permitem construir essas interfaces rapidamente, como é o caso do PyGTK e do PyQT, entre outras. Nota-se em particular que a módulo desenvolvido por John Zelle recorre à biblioteca Tkinter.

Simulação de um supermercado

A simulação de sistemas reais é uma das aplicações centras da engenharia informática. Consideremos o exemplo de simulação de supermercado descrito na secção 12.1 do livro "Programação em Python: Introdução à programação com múltiplos paradigmas", João P. Martins 2015 IST Press. Uma possível visualização utilizando a biblioteca anterior está também descrita na secção 12.6 deste mesmo livro.