Muitas vezes, a pilha é implementada como um linklist, A representação da matriz não é boa o suficiente, na matriz, podemos executar push pop facilmente e a lista vinculada sobre a matriz dificulta o código e não tem nenhuma vantagem sobre a implementação da matriz.
Você pode dar qualquer exemplo onde uma implementação de lista vinculada é mais benéfica, ou não podemos ficar sem ela.
Respostas:
2 para resposta № 1Eu diria que muitas implementações práticas de pilhas estamos escrito usando matrizes. Por exemplo, a implementação do .NET Stack usa uma matriz como um armazenamento de apoio.
Os arrays são normalmente mais eficientes porque você pode manter todos os nós da pilha próximos em uma memória contígua que possa se encaixar perfeitamente em suas linhas de cache rápidas no processador.
Eu imagino que você veja implementações de livros didáticos depilhas que usam listas vinculadas porque são mais fáceis de escrever e não forçam você a escrever um pouco de código extra para gerenciar a loja de matriz de apoio, assim como criar uma heurística de espaço de crescimento / cópia / reserva.
Além disso, se você for realmente pressionado para usarpouca memória, uma implementação de lista vinculada pode fazer sentido, já que você não "desperdiça" espaço que não é usado atualmente. No entanto, em processadores modernos com muita memória, normalmente é melhor usar arrays para obter as vantagens de cache que eles oferecem, em vez de se preocupar com falhas de página com a abordagem de lista vinculada.
1 para resposta № 2
O tamanho da matriz é limitado e predefinido. Quando você não sabe quantos deles estão lá, então lista vinculada é uma opção perfeita.
Comparação mais elaborada: - (+ para dominar lista vinculada e - para matriz)
Size and type constraint:-
(+) Outros membros da matriz são alinhados em igualdadedistância e precisa de memória contígua, enquanto na lista de links do outro lado pode fornecer solução de memória não contígua, por isso às vezes é bom para a memória, bem como no caso de dados enormes (evita a pesquisa de cpu para recurso).
(+) Suponha que em um caso você esteja usando um array como stack, e o array seja do tipo int.Agora como você vai acomodar um double nele?
Portability
- A matriz (+) pode causar exceções como exceções de índice fora do limite, mas você pode aumentar a cadeia a qualquer momento em uma lista vinculada.
Speed and performance
- (-) Se é sobre desempenho, então obviamente maisda complexidade cair em torno de O (1) para matrizes. No caso de uma lista vinculada, você terá que selecionar um nó inicial para iniciar o rastreio e isso aumenta a penalidade de desempenho.
0 para resposta № 3
Quando o tamanho da pilha pode variar muito, você desperdiça espaço se tiver rotinas generalizadas que sempre alocam uma matriz enorme.
0 para a resposta № 4
Obviamente, uma matriz de tamanho fixo tem limitação de saber o tamanho máximo antes da mão.
Se você considerar dynamic array então Lista vinculada vs. matrizes abrange os detalhes, incluindo complexidades para a realização de operações.
0 para a resposta № 5
A pilha é implementada usando Lista Vinculada porque as operações Push e Pop são de complexidade de tempo O (1), em comparação com O (n) para matrizes. (além da vantagem de tamanho flexível na Lista vinculada)