Políticas de acesso e manipulação

Algumas estruturas de dados não requerem novas formas de armazenamento dos dados em memória. Nesses casos, tais estruturas são definidas apenas pela forma com a qual elas permitem o acesso e manipulação dos dados armazenados, o que chamei de política de acesso e manipulação.

Para melhor compreendermos essa ideia, iniciaremos o estudo de duas estruturas de dados (ou políticas de acesso e manipulação) de grande relevância: pilhas (stack) e filas (queue). Por serem apenas políticas de acesso, pilhas e filas podem ser implementadas utilizando como base diferentes tipos de estruturas de dados (contêiners). Neste primeiro momento, no entanto, assumiremos apenas a implementação de pilhas e filas utilizando o contêiner vector como base.

Pilhas (stack)

A estrutura de dados Pilha recebe este nome em analogia ao processo de empilhamento. De acordo com o dicionário web Michaelis, empilhar tem o seguinte significado:

em·pi·lhar Dispor em pilha ou ficar amontoado em pilha; amontoar(-se):
- Empilhou os pratos que havia acabado de enxugar.
- “[…] erguia o que estava pelo chão e empilhava as cadeiras sobre as mesinhas de mármore” (AA2).
- “Entrou no seu escritório e foi sentar-se à secretária. Defronte dele, com uma gravidade oficial, empilhavam-se grandes livros de escrituração mercantil” (AA2).

De acordo com esta definição, empilhar significa inserir um objeto em cima de outro. Desempilhar, portanto, se refere a remoção do objeto no topo da pilha.

Dada a analogia, define-se que uma estrutura de dados pilha é caracterizada pelo fato de que novos elementos somente podem ser inseridos em seu topo. A remoção de elementos da pilha, similarmente, somente pode acontecer para elementos no topo. O acesso ao elemento no topo da pilha, sem a remoção do mesmo, é muitas vezes necessário, desta forma um operador se faz necessário. Em resumo:

Novos elementos são inseridos em apenas uma direção.
- O último elemento inserido é chamado o topo da pilha
- Essa operação é chamada push
Elementos são removidos em direção oposta à inserção
- Somente o elemento no topo pode ser removido diretamente.
- Essa operação é chamada pop
Este tipo de política de acesso ficou conhecido pela sigla:
- LIFO, do inglês last in, first out. O último elemento inserido é necessáriamente o primeiro a ser removido.

pilhas

Estruturas do tipo stack são de grande utilidade em aspectos fundamentais da ciência da computação. Seja na construção de compiladores e linguagens de programação, por uma perspectiv teórica, ou no gerenciamento de memória da pilha de chamadas (stack call)

Implementações de pilhas em linguagens de programação:

C++/STL, stack
- http://www.cplusplus.com/reference/stack/stack/
Python, Using lists as stacks
- https://docs.python.org/2/tutorial/datastructures.html#using-lists-as-stacks
C#, Stack
- https://msdn.microsoft.com/pt-br/library/system.collections.stack(v=vs.110).aspxs

Filas (queue)

A estrutura de dados fila (ou política de acesso) também recebe este nome por analogia ao processo de enfileiramento

fi·la (Michaelis) Sequência de pessoas ou coisas alinhadas uma atrás da outra, organizada geralmente por ordem cronológica de chegada ou por diferentes critérios…
- “Havia agora Betinha, Aureluce, Tanara e outras amigas barulhentas em volta, uma fila inteira delas no Cine Cruzeiro do Sul” (CFA).
- “Conjunto de soldados em fileira”

Por essa analogia é fácil notarmos que a estrutura de dados fila deve suportar operações análogas ao enfileiramento e o desenfileiramento. Em termos mais diretos, isso significa que a inserção de novos elementos em uma fila deve ser feita sempre em uma das pontas da estrutua (push_back ou push_front) enquanto a remoção poderia apenas ser feita na ponta oposta da estrutura (pop_front ou pop_back). Em resumo:

Novos elementos são inseridos em apenas uma das pontas.
- Essa operação é chamada push
Elementos são removidos da ponta oposta à inserção.
- Somente o elemento inicial pode ser removido diretamente.
- Essa operação é chamada pop
Este tipo de política de acesso ficou conhecido pela sigla:
- FIFO, do inglês first in, first out. O primeiro elemento inserido é necessáriamente o primeiro a ser removido.

Implementação sobre vector

Pilhas e filas, sendo apenas políticas de acesso, podem ser implementadas utilizando diferentes estruturas de dados como base (contêiner). Neste primeiro momento, utilizaremos como contêiner a estrutura vector implementada anteriormente.

Pilhas

É fácil notar que todas as funcionalidades necessárias para manipular uma pilha estão implementadas para vector. De fato, precisamos apenas de um subconjunto das funcionalidades disponíveis em vector, ou seja, pilhas são mais restritivas.

// **** stack.h ****
#include "vector.h"
#include <stdbool.h>
typedef vector stack;
#define STACK_INIT_SIZE 10
// Alocação desalocação
stack* new_stack();
void free_stack(stack* v);
// Inserção e remoção de elementos
Type stack_pop(stack* v);
void stack_push(stack* v, Type value);
// Observer o topo da pilha, sem remoção
Type* stack_top(stack* v);
bool stack_empty(stack* v);

Vejamos quais funcionalidades de vector serão úteis para implementarmos uma estrutura pilha (stack).

Opção 1

void vector_push_back(vector* v, Type value);
Type vector_pop_back(vector* v);

Opção 2

void vector_push_front(vector* v, Type value);
Type vector_pop_front(vector* v);

Cada uma dessas opções insere e remove elementos de uma das pontas de vector. Por razões de eficiência, utilizaremos a opção 1 a seguir.

Questão: Porque devemos preferir a opção 1 para implementação de stack se o contêiner base for vector?

// **** stack.c ****
#include "stack.h"
// Alocação desalocação
stack* new_stack() {
    stack* s = new_vector(STACK_INIT_SIZE);
    return s;
}
void free_stack(stack* v){
    free_vector(v);
}
// Inserção e remoção de elementos
Type stack_pop(stack* v) {
    return vector_pop_back(v);
}
void stack_push(stack* v, Type value) {
    vector_push_back(v, value);
}
// Retorna um ponteiro para o topo da pilha
Type* stack_top(stack* v) {
    return vector_at(v, v->size-1);
}
bool stack_empty(stack* v) {
    return v->size == 0;
}

Filas

É fácil notar que todas as funcionalidades necessárias para manipular uma estão implementadas para vector. De fato, precisamos apenas de um subconjunto das funcionalidades disponíveis em vector, ou seja, filas são mais restritivas.

Vejamos quais funcionalidades de vector serão úteis para implementarmos uma estrutura pilha (queue).

Opção 1

void vector_push_back(vector* v, Type value);
Type vector_pop_front(vector* v);

Opção 2

void vector_push_front(vector* v, Type value);
Type vector_pop_back(vector* v);

Cada uma dessas opções insere elementos em uma das pontas de vector e remove da outra.

Questão: Quais as deficiências em termos da eficiência de cada uma das opções?

// **** queue.c ***
#include "queue.h"
// Alocação desalocação
queue* new_queue() {
    queue* s = new_vector(QUEUE_INIT_SIZE);
    return s;
}
void free_queue(queue* v){
    free_vector(v);
}
// Inserção e remoção de elementos
Type queue_pop(queue* v) {
    return vector_pop_back(v);
}
void queue_push(queue* v, Type value) {
    vector_push_back(v, value);
}
// Retorna um ponteiro para o topo da pilha
Type* queue_begin(queue* v) {
    return vector_at(v, 0);
}

Eficiência das implementações

Qual a ineficiência da implementação de queue utilizando vector diretamente.
Implementação circular (pg. 207 Tenenbaum)