Estruturas de Dados Derivadas:�Pilhas, Filas e Matrizes Esparsas
PILHAS
Pilha (em inglês, Stack)
Criando pilhas a partir de listas
pilha = [] # cria pilha vazia
pilha.append(10)
pilha.append(6)
dado = pilha.pop()
print(dado) # mostra o 6
dado = pilha.pop()
print(dado) # mostra o 10
Exemplo 5: Faça um programa de pilha de cartas de um baralho, que use ‘c’ para colocar uma carta na pilha, ‘r’ para retirar uma carta da pilha e ‘p’ para parar.
pilha = []
while True:
comando = input('(c)olocar / (r)etirar / (p) parar: ')
if comando == 'c':
carta = input('Qual a carta? ')
pilha.append(carta)
elif comando == 'r':
if pilha:
carta = pilha.pop()
print(carta)
else:
print('Não há nenhuma carta na pilha.')
elif comando == 'p':
if not pilha:
break
else:
print('A pilha ainda tem cartas.')
opção = input('Parar? (s/n): ')
if (opção == 's' or opção == 'S'):
break
else:
print('Comando inexistente!')
FILAS
Filas (em inglês, Queue)
Criando filas a partir de listas
fila = [] # cria fila vazia
fila.append(10)
fila.append(6)
dado = fila.pop(0)
print(dado) # mostra o 10
dado = fila.pop(0)
print(dado) # mostra o 6
Exemplo 6: Faça um programa de fila de atendimento, que use ‘a’ para atender, ‘c’ quando chegar alguém e ‘p’ para parar.
fila = []
while True:
comando = input('(c)hegada / (a)tender / (p) parar: ')
if comando == 'c':
nome = input('Nome do cliente: ')
fila.append(nome)
elif comando == 'a':
if fila:
nome = fila.pop(0)
print(nome)
else:
print('Não há ninguém na fila.')
elif comando == 'p':
if not fila:
break
else:
print('A fila ainda contém os seguintes clientes: ')
for nome in fila:
print(nome)
opção = input('Parar? (s/n): ')
if (opção == 's' or opção == 'S'):
break
else:
print('Comando inexistente!')
Exercícios
a) Listar o número de aviões aguardando na fila de decolagem;
b) Autorizar a decolagem do primeiro avião da fila;
c) Adicionar um avião à fila de espera;
d) Listar todos os aviões na fila de espera;
e) Listar as características do primeiro avião da fila.
Considere que os aviões possuem um nome e um número inteiro como identificador. Adicione outras características conforme achar necessário.
MATRIZES ESPARSAS A PARTIR DE DICIONÁRIOS
Criando matrizes a partir de dicionários
# Em Python:
matriz = {(1,1):2,(1,2):4,(2,1):7,(2,2):9}
print(matriz[(2,1)]) # mostra 7
print(matriz[(2,2)]) # mostra 9
matriz[(2,2)] = 15
print(matriz[(2,2)]) # mostra 15
matriz[(1,1)] = int(input())
print(matriz[(1,1)]) # mostra o que digitou
Alterando o Exemplo 2 da aula sobre matrizes para ter um loop a menos: Com dicionários, é possível
a, b, c = {}, {}, {}
for i in range(3):
for j in range(4):
print('Digite o elemento %d,%d da matriz A: ' % (i+1,j+1))
a[(i,j)] = int(input())
for i in range(3):
for j in range(4):
print('Digite o elemento %d,%d da matriz B: ' % (i+1,j+1))
b[(i,j)] = int(input())
print('\nMatriz resultante:\n')
for i in range(3):
for j in range(4):
c[(i,j)] = a[(i,j)] + b[(i,j)]
print('%5d ' % c[(i,j)], end = '')
print()
matriz = {}
matriz[(15,25)] = 32
print(matriz[(15,25)])
# Mas, imprimir uma chave inexistente dá erro
print(matriz[(3,8)]) # Como corrigir este erro?
print(matriz.get((15,25),0)) # mostra 32
print(matriz.get((3,8),0)) # mostra 0
Vantagens de usar dicionários para matrizes
Exemplo 4: Faça um programa que use um dicionário para guardar as reservas de um teatro, considerando que as filas do teatro usam uma letra entre ‘a’ e ‘z’ para identificação e cada cadeira usa um número.
PRIMEIRA_FILA = 'a'
ÚLTIMA_FILA = 'z'
CADEIRAS = 40
lugares = {} # matriz booleana de lugares no teatro
continua = 's'
while continua == 's' or continua == 'S':
reserva_fila = input('Fila: ')
reserva_cadeira = int(input('Cadeira: '))
reservado = lugares.get((reserva_fila,reserva_cadeira), False)
if reservado:
print('Este lugar já está reservado...')
else:
lugares[(reserva_fila,reserva_cadeira)] = True
print('Reserva realizada!')
continua = input('Nova reserva? (s/n): ')
print('Fim!')
Exercícios