Melhor resposta
Em ciência da computação , um tipo de dados abstratos ( ADT ) é um modelo matemático para tipos de dados onde um tipo de dado é definido por seu comportamento ( semântica ) do ponto de vista de uma usuário dos dados, especificamente em termos de valores possíveis, operações possíveis em dados desse tipo e o comportamento dessas operações. Isso contrasta com as estruturas de dados , que são representações concretas de dados e são o ponto de vista de um implementador, não de um usuário.
De Estrutura de dados :
Em ciência da computação , um estrutura de dados é uma maneira particular de organizar dados em um computador para que possam ser usados eficientemente .
As estruturas de dados podem implementar um ou mais tipos de dados abstratos particulares (ADT), que são os meios de especificar o contrato de operações e sua complexidade
Uma estrutura de dados é uma implementação concreta do contrato fornecido por um ADT
O que isso significa é:
1. ADT é uma representação abstrata , do ponto de vista do usuário
2. DS é uma representação concreta , não do ponto de vista do usuário
Em termos simples:
1. Stack é ADT , ele apenas especifica que deve haver um push, pop, etc. para o usuário usar.
2. Stack (como outros ADTs como Queue) é implementado usando DS como array ou lista (lista vinculada, etc.)
Resumo:
Stack não é DS, é ADT e é implementado usando outro DS.
Espero que tenha ajudado.
Boa sorte
Resposta
Pilhas
Uma pilha é um contêiner de objetos que são inseridos e removidos de acordo com o princípio último a entrar, primeiro a sair (LIFO). Nas pilhas pushdown, apenas duas operações são permitidas: push o item na pilha e pop o item fora da pilha. Uma pilha é uma estrutura de dados de acesso limitado – os elementos podem ser adicionados e removidos da pilha apenas no topo. push adiciona um item ao topo da pilha, pop remove o item do topo . Uma analogia útil é pensar em uma pilha de livros; você pode remover apenas o livro do topo e também pode adicionar um novo livro ao topo.
Uma pilha é uma estrutura de dados recursiva . Aqui está uma definição estrutural de uma pilha:
Aplicativos
- A aplicação mais simples de uma pilha é inverter uma palavra. Você empurra uma determinada palavra para empilhar – letra por letra – e então retira as letras da pilha.
- Outro aplicativo é um mecanismo de “desfazer” nos editores de texto; esta operação é realizada mantendo todas as alterações de texto em uma pilha. Retrocedendo . Este é um processo em que você precisa acessar o elemento de dados mais recente em uma série de elementos. Pense em um labirinto ou labirinto – como você encontra o caminho de uma entrada para uma saída? Ao chegar a um beco sem saída, você deve voltar atrás. Mas voltar para onde? para o ponto de escolha anterior. Portanto, em cada ponto de escolha, você armazena em uma pilha todas as opções possíveis. Em seguida, retroceder significa simplesmente retirar a próxima escolha da pilha.
- Processamento de linguagem: o espaço para parâmetros e variáveis locais é criado internamente usando uma verificação de sintaxe stack.compiler para chaves correspondentes é implementada usando stack.support para recursão
Implementação
Na biblioteca padrão de classes, a pilha de tipo de dados é um adaptador classe, o que significa que uma pilha é construída sobre outras estruturas de dados. A estrutura subjacente de uma pilha pode ser uma matriz, um vetor, um ArrayList, um lista encadeada ou qualquer outra coleção. Independentemente do tipo de estrutura de dados subjacente, uma pilha deve implementar a mesma funcionalidade.Isso é conseguido fornecendo uma interface exclusiva:
public interface StackInterface
{
public void push(AnyType e);
public AnyType pop();
public AnyType peek();
public boolean isEmpty();
}
O a imagem a seguir demonstra a ideia de implementação por composição .
Outro requisito de implementação (além da interface acima) é que todas as operações de pilha devem ser executadas em
tempo constante O (1)
. Tempo constante significa que existe alguma constante k tal que uma operação leva k nanossegundos de tempo computacional, independentemente do tamanho da pilha.
Implementação baseada em array
Em uma implementação baseada em array, mantemos os seguintes campos: um array A de tamanho padrão (≥ 1 ), a variável topo que se refere ao elemento superior da pilha e a capacidade que refere-se ao tamanho da matriz. A variável top muda de -1 para capacity - 1. Dizemos que uma pilha está vazia quando top = -1 e que a pilha está cheia quando top = capacity-1.
Em um fixo -size stack abstraction, a capacidade permanece inalterada, portanto, quando top atinge capacidade , a pilha objeto lança uma exceção.
Em uma abstração de pilha dinâmica quando topo atinge capacidade , dobramos o tamanho da pilha.
Implementação baseada em lista vinculada
baseada em lista vinculada implementação fornece a melhor (do ponto de vista da eficiência) implementação de pilha dinâmica.
Fonte – Pilhas e filas