Deque (estruturas de dados): diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m |
|||
Linha 26:
A Deque é dividida pelo total de posições em duas extremidades, onde o total não pode ser extrapolado, senão ocorre o estouro da memória, que já foi programada para uma determinada quantidade, não havendo possibilidade de mudança após já se ter definido o total. Os primeiros que são inseridos são os últimos a serem retirados, e é possível inserir elementos em ambos os lados (tanto no seu início como no seu final) mesmo que desproporcionalmente, desde que não ultrapasse o limite máximo.
== Pseudocódigo de exemplo ==
O algoritmo abaixo implementa genericamente um deque circular estático (de <math>N</math> posições, indexadas de 0 até <math>N - 1</math>).
=== Variáveis ===
<syntaxhighlight>
INTEIRO N
INTEIRO inicio = -1
INTEIRO fim = -1
TIPO VETOR deque[DE 0 ATÉ N]
</syntaxhighlight>
=== Verificar se o deque está cheio ===
<syntaxhighlight>
FUNÇÃO cheio() RETORNA BOOLEANO
SE ((fim + 1) % N = inicio) ENTÃO
RETORNA VERDADEIRO
SENÃO
RETORNA FALSO
FIM DO SE
FIM DA FUNÇÃO
</syntaxhighlight>
=== Verificar se o deque está vazio ===
<syntaxhighlight>
FUNÇÃO vazio() RETORNA BOOLEANO
SE (inicio = -1) ENTÃO
RETORNA VERDADEIRO
SENÃO
RETORNA FALSO
FIM DO SE
FIM DA FUNÇÃO
</syntaxhighlight>
=== Inserir no começo ===
<syntaxhighlight start="1">
PROCEDIMENTO inserirComeço(TIPO valor)
SE cheio() ENTÃO
ESCREVA "Deque cheio!"
SENÃO
SE vazio() ENTÃO
inicio = 0
fim = 0
SENÃO
SE (inicio = 0) ENTÃO
inicio = N - 1
SENÃO
inicio = inicio - 1
FIM DO SE
FIM DO SE
deque[inicio] = valor
FIM DO SE
FIM DO PROCEDIMENTO
</syntaxhighlight>
=== Inserir no final ===
<syntaxhighlight>
PROCEDIMENTO inserirFinal(TIPO valor)
SE cheio() ENTÃO
ESCREVA "Deque cheio!"
SENÃO
SE vazio() ENTÃO
inicio = 0
fim = 0
SENÃO
SE (fim = N - 1) ENTÃO
fim = 0
SENÃO
fim = fim + 1
FIM DO SE
FIM DO SE
deque[fim] = valor
FIM DO SE
FIM DO PROCEDIMENTO
</syntaxhighlight>
=== Remover do começo ===
<syntaxhighlight>
FUNÇÃO removerComeço() RETORNA TIPO
SE vazio() ENTÃO
RETORNA (TIPO) NULO
SENÃO
TIPO valor = deque[inicio]
deque[inicio] = (TIPO) NULO
SE (inicio = fim) ENTÃO
inicio = -1
fim = -1
SENÃO
SE (inicio = N - 1) ENTÃO
INICIO = 0
SENÃO
inicio = inicio + 1
FIM DO SE
FIM DO SE
RETORNA valor
FIM DO SE
FIM DA FUNÇÃO
</syntaxhighlight>
=== Remover do final ===
<syntaxhighlight>
FUNÇÃO removerFinal() RETORNA TIPO
SE vazio() ENTÃO
RETORNA (TIPO) NULO
SENÃO
TIPO valor = deque[fim]
deque[fim] = (TIPO) NULO
SE (inicio = fim) ENTÃO
inicio = -1
fim = -1
SENÃO
SE (fim = 0) ENTÃO
fim = N - 1
SENÃO
fim = fim - 1
FIM DO SE
FIM DO SE
RETORNA valor
FIM DO SE
FIM DA FUNÇÃO
</syntaxhighlight>
=== Buscar valor no começo ===
<syntaxhighlight>
FUNÇÃO buscarComeço() RETORNA TIPO
SE vazio() ENTÃO
RETORNA (TIPO) NULO
SENÃO
RETORNA deque[inicio]
FIM DO SE
FIM DA FUNÇÃO
</syntaxhighlight>
=== Buscar valor no fim ===
<syntaxhighlight>
FUNÇÃO buscarFinal() RETORNA TIPO
SE vazio() ENTÃO
RETORNA (TIPO) NULO
SENÃO
RETORNA deque[fim]
FIM DO SE
FIM DA FUNÇÃO
</syntaxhighlight>{{Referências}}
{{esboço-programação}}
| |||