3.2. O que são estruturas lineares?¶

Começaremos nosso estudo de estruturas de dados considerando quatro estruturas simples, mas muito uteis. Pilhas, filas, deques e listas são exemplos de coleções de dados cujos itens são ordenados de acordo com ordem que são inseridos ou removidos da estrutura. Uma vez que um item é inserido, fica em uma mesma posição em relação aos demais itens que foram inseridos antes ou que serão inseridos depois. Coleções como essas são frequentemente chamadas de estruturas de dados lineares.

Estruturas lineares podem ser consideradas como tendo duas extremidades. Às vezes essas estremidades são chamadas de esquerda e direita ou, em alguns casos, de frente e traseira. Você também pode chamá-las de topo e base. Os nomes dados às extremidades não são relevantes. O que distingue uma estrutura linear de outra é a maneira em que itens são inseridos e removidos, em particular a extremidade onde estes inserções e remoções ocorrem. Por exemplo, uma estrutura pode permitir que novos itens sejam inseridos em apenas uma das extremidades (pilhas e filas). Algumas estruturas podem permitir que itens sejam removidos de ambas as extremidades (deques).

Essas variações dão origem a algumas das estruturas de dados mais utilizadas Ciência da Computação. Elas aparecem em muitos algoritmos utilizados diariamente e podem ser usadas ​​para resolver uma variedade de problemas importantes.