04 Stacks e Queues

2º Semestre
2023/2024
Aula 4 (7 e 8)
Algoritmia e
Estruturas de
Dados
Joana Martinho Costa, João Matos, João Monge, Miguel Sales Dias, Paulo Vieira
No episódio anterior...
• ...trabalhámos a análise de algoritmos

N
1 Acessos a array
N
N-1
2 Acessos a array
N
N-1
N-2
3 Acessos a array
Stacks e Queues
• Stacks
• Resizing arrays
• Queues
• Aplicações
Stacks e Queues
• Tipos de dados fundamentais
• Operações: insert, remove, iterate, test (para testar se está vazio)
• Stack: Examinar o item que foi adicionado mais recentemente

• Estrutura LIFO: Last In First Out
• Queue: Examinar o item que foi adicionado há mais tempo
• Estrutura FIFO: First In First Out
Generalizamos
• Criamos estruturas genéricas que possam ser reutilizadas em diversos

contextos
Stack API (Application Programming
Interface)
• Contexto: Stack de Strings
Stack – Cliente de Teste
1. Lê uma String
def main(): 2. Se a String for igual a “-”, executa
for line in sys.stdin: pop da stack e imprime
stack = StackOfStrings()
for item in line.split(): 3. Se não, faz push para a stack
if item == "-":
print(stack.pop(), " ", end='')
else:
stack.push(item)
Como construir os métodos da
Stack?
• Através de uma estrutura Linked-List
• Através de um array
Versão 1: Stack com
Linked-List
O que é uma
linked-list?
• Uma lista ligada (ou encadeada) é uma
estrutura de dados que liga vários nós.
• Cada nó tem um apontador para o nó
seguinte.
• O exemplo da figura é uma lista de

Strings, onde cada nó é composto por
uma String e um apontador para o nó
seguinte
Stack com Linked-List
1º: Criar uma classe “Nó” para representar os nós da lista
class Node:
def __init__(self, item, next_node):
self.item = item
self.next = next_node
2º: Preparar a funcionalidade pop (retirar

da stack):
para retirar o nó da stack, troca-se o
apontador do primeiro nó (Nó first) para o
segundo nó
2º: Preparar a funcionalidade push (colocar

da stack):
Para adicionar um nó na stack, guarda-se a
ligação ao nó first, cria-se um novo nó e
liga-se o novo nó ao antigo nó first
class LinkedStackOfStrings:
def __init__(self):
Stack com Linked-List self.first = None
def is_empty(self):
return self.first is None
• Versão completa def push(self, item):

oldfirst = self.first
self.first = Node(item, oldfirst)
def pop(self):
class Node: item = self.first.item
def __init__(self, item, next_node): self.first = self.first.next
self.item = item return item
No mínimo, incrementa-se o i+=1 (N), no máximo incrementa-se o i+=1 e o count+=1 (2N)

1. Criar a classe LinkedStackofInts com nós
do tipo inteiro
2. Cria uma função main com:
Tarefa a)
b)
Dois push (inteiros 34 e 67)
Um pop
a) Imprime o valor que saiu da stack
Análise da performance da
Todas as operações (criação, verificar se está
vazio, push e pop) têm um custo de execução
constante no pior caso
Em relação ao custo de memória, uma stack com

N itens tem um custo de 40N bytes (excluindo o
custo do próprio tipo de dados de cada nó, como class Node:
por exemplo, o custo associado a String) def __init__(self, item, next_node):
self.item = item
Versão 2: Stack com
Array
Stack com Array
• Usar um array s[] para guardar N itens numa stack
• Método push: adiciona itens ao s[N]
• Método pop: retira itens do s[N-1]
• Se o número de itens a adicionar for maior que a capacidade do

array: stack overflow
Implementação
Stack com Array
class FixedCapacityStackOfStrings:
def __init__(self, capacity):
self.N = 0
self.s = []
for i in range(capacity):
self.s.append("")
def is_empty(self): def main():

return self.N == 0 for line in sys.stdin:
stack = FixedCapacityStackOfStrings(10)
def push(self, item): for item in line.split():
self.s[self.N] = item if item == "-":
self.N += 1 print(stack.pop(), " ", end='')
else:
stack.push(item)
def pop(self):
self.N -= 1
return self.s[self.N]
Stack com Array
• Características
• Lança uma exceção se chamar o pop() numa stack vazia
• Se a stack encher, é necessário fazer o resizing ao array
• Valores null podem ser inseridos
• Existe um problema de loitering que consiste em manter em memória
valores que já não são usados
Stack com Array
def pop(self):
def pop(self):
self.N -= 1
self.N -= 1
item = self.s[self.N]
return self.s[self.N]
self.s[self.N] = None
return item
Loitering
Resizing
Resizing
• Como aumentar o array?
• Tentativa 1
• Push(): aumenta o tamanho do array s[] para +1
• Pop(): diminui o tamanho do array s[] para -1
Tem um custo demasiado elevado ☹

Em cada push/pop seria necessário copiar todos os itens para um novo array
Inserir N itens tem um custo proporcional a 1+2+...+N – aproximadamente N^2/2

Resizing
Tentativa 2: Se o array encher,

duplica-se o tamanho e
copiam-se todos os itens para o
novo array
Inserir N itens tem um custo

proporcional a N (e não N2)
Resizing
• Como diminuir o array?
• Tentativa 1
• Push(): duplica o array s[] quando está preenchido
• Pop(): reduz o array s[] para metade quando está metade preenchido
Tem um custo demasiado elevado ☹

Em cada push/pop seria necessário copiar todos os itens para um novo array
Inserir N itens tem um custo proporcional a 1+2+...+N – aproximadamente N^2/2

Resizing
• Custo elevado!
• Se considerarmos uma sequência contínua push-pop-push-pop... Quando
o array está cheio, cada operação tem um custo proporcional a N
Resizing
• Como diminuir o array?
• Solução mais eficiente

• Push(): duplica o array s[]
quando está preenchido
• Pop(): reduz o array s[] para
metade quando está metade
¼ preenchido
Stack com Linked-List ou com
Resizing-Array?
• Implementação com linked-list

• Todas as operações têm um custo constante no pior caso
• Utiliza tempo e espaço extra para trabalhar com as ligações entre os nós
• Implementação com resizing array

• Todas as operações têm um custo amortizado N
• Menos espaço desperdiçado
Implementação de Stacks
• Botão “Retroceder” no web browser

• Botão “Anular” no processador de texto
1. Criar a classe ResizingArrayStackOfInt
Cria uma função main com:
a) Quatro push (inteiros 34, 42, 89 e
67)
b) Dois pop
Tarefa c) Imprime o tamanho do vetor a cada

operação push ou pop
Tarefa • Stack Fixa
Filas
Queues
Queues
Queue com Linked-list
• Ao contrário do Stacks, temos

de manter referência para dois
elementos: first e last
class QueueOfStrings:
def __init__(self):
Queue com Nodes self.first = None
self.last = None
def enqueue(self, item):

oldlast = self.last
• Versão Completa self.last = Node(item, None)
oldlast.next = self.last
def dequeue(self):
item = self.first.item
self.first = self.first.next
return item
def is_empty(self):
return self.first is None
Queue com Resizing
● Utiliza o array [] para guardar os items na fila

● enqueue(): adiciona o novo elemento a q[tail]
● dequeue(): remove o item da q[head].
● Atualiza os apontadores head e tail
• Implementar a estrutura de dados Queue
Tarefa com resizing
Tarefa • Tarefa Semanal 4

04 Stacks e Queues

Enviado por

Direitos autorais:

Formatos disponíveis

04 Stacks e Queues

Enviado por

Dados do documento

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

04 Stacks e Queues

Enviado por

Direitos autorais:

Formatos disponíveis

2º Semestre

• ...trabalhámos a análise de algoritmos

• Stack: Examinar o item que foi adicionado mais recentemente

• Criamos estruturas genéricas que possam ser reutilizadas em diversos

• O exemplo da figura é uma lista de

1º: Criar uma classe “Nó” para representar os nós da lista

2º: Preparar a funcionalidade pop (retirar

2º: Preparar a funcionalidade push (colocar

• Versão completa def push(self, item):

No mínimo, incrementa-se o i+=1 (N), no máximo incrementa-se o i+=1 e o count+=1 (2N)

Em relação ao custo de memória, uma stack com

• Se o número de itens a adicionar for maior que a capacidade do

def is_empty(self): def main():

• Como aumentar o array?

Tem um custo demasiado elevado ☹

Inserir N itens tem um custo proporcional a 1+2+...+N – aproximadamente N^2/2

Tentativa 2: Se o array encher,

Inserir N itens tem um custo

• Como diminuir o array?

Tem um custo demasiado elevado ☹

Inserir N itens tem um custo proporcional a 1+2+...+N – aproximadamente N^2/2

• Solução mais eficiente

• Implementação com linked-list

• Implementação com resizing array

• Botão “Retroceder” no web browser

Tarefa c) Imprime o tamanho do vetor a cada

Queue com Linked-list

• Ao contrário do Stacks, temos

def enqueue(self, item):

● Utiliza o array [] para guardar os items na fila

Você também pode gostar