{"id":2678,"date":"2020-04-01T17:25:00","date_gmt":"2020-04-01T20:25:00","guid":{"rendered":"https:\/\/www.ufsm.br\/pet\/sistemas-de-informacao\/?p=2678"},"modified":"2025-09-02T13:53:54","modified_gmt":"2025-09-02T16:53:54","slug":"entendendo-listas-pilhas-e-filas","status":"publish","type":"post","link":"https:\/\/www.ufsm.br\/pet\/sistemas-de-informacao\/2020\/04\/01\/entendendo-listas-pilhas-e-filas","title":{"rendered":"Entendendo listas, pilhas e filas"},"content":{"rendered":"\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n

Nesta edi\u00e7\u00e3o do PET-Reda\u00e7\u00e3o iremos falar sobre algumas estruturas de dados do mundo da computa\u00e7\u00e3o, sendo elas: as listas encadeadas, as pilhas e filas.<\/p>\n

No entanto, iremos abordar pontos espec\u00edficos de cada uma delas, principalmente de que modo s\u00e3o estruturadas e como implementar algumas fun\u00e7\u00f5es b\u00e1sicas para manipul\u00e1-las.<\/p>\n

\n
\n
\n
\u00a0<\/div>\n<\/div>\n<\/div>\nListas encadeadas<\/strong><\/div>\n

Em uma lista encadeada , para cada novo elemento inserido na estrutura, alocamos um espa\u00e7o de mem\u00f3ria para armazen\u00e1-lo. Dessa forma, o espa\u00e7o total ocupado na mem\u00f3ria \u00e9 proporcional ao n\u00famero de elementos da lista. No entanto, n\u00e3o podemos garantir que os elementos armazenados na mem\u00f3ria ocupar\u00e3o um espa\u00e7o cont\u00edguo, e por isso n\u00e3o temos acesso aos elementos da lista diretamente.<\/p>\n

Para percorrer e ter acesso aos elementos da lista devemos guardar o seu encadeamento. Sendo assim a estrutura consiste em uma sequ\u00eancia encadeada de elementos, chamados de n\u00f3s da lista. Cada n\u00f3 da lista tem a sua informa\u00e7\u00e3o, podendo ser um valor inteiro, real, caractere ou at\u00e9 uma sequ\u00eancia de caracteres, e um ponteiro para o pr\u00f3ximo elemento da lista.<\/p>\n

A imagem a seguir representa este conceito, onde do primeiro elemento, temos acesso ao segundo, e assim por diante. Sendo que o \u00faltimo elemento armazenado um ponteiro inv\u00e1lido, com valor NULL, indicando o fim da lista.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/section>\n

\n
\u00a0<\/div>\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\"\"<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/section>\n
\n
\u00a0<\/div>\n
\n
\n
\n
\n
\n
\n
\n
\n
\n

O c\u00f3digo abaixo exemplifica a implementa\u00e7\u00e3o de uma lista encadeada na linguagem C para armazenar valores inteiros.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/section>\n

\n
\n
\n
\n
\n
\u00a0<\/div>\n<\/div>\n<\/div>\n
\n
\n
\n
\n
\n
\n
\n
\"\"<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n
\n
\u00a0<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/section>\n
\n
\u00a0<\/div>\n
\n
\n
\n
\n
\n
\n
\n
\n
\n

Devemos notar que essa estrutura \u00e9 auto-referenciada, pois o campo \u201cstruct lista* prox;<\/strong><\/em>\u201d<\/em>\u00a0\u00e9 um ponteiro para para uma estrutura do mesmo tipo. Al\u00e9m disso, uma boa estrat\u00e9gia e definir o tipo \u201cLista<\/strong><\/em>\u201c como sin\u00f4nimo de \u201dstruct lista<\/strong><\/em>\u201c conforme demonstra o trecho de c\u00f3digo acima. Com isso, o tipo \u201cLista<\/strong><\/em>\u201c representa um n\u00f3 da lista, e a estrutura de lista encadeada ser\u00e1 representada por um ponteiro para o primeiro elemento da lista (tipo\u00a0Lista*<\/strong><\/em>). Sabendo a defini\u00e7\u00e3o de lista , agora podemos come\u00e7ar a implementar fun\u00e7\u00f5es necess\u00e1rias para manipular essa estrutura.<\/p>\n

\n
\n
\n
\u00a0<\/div>\n<\/div>\n<\/div>\nFun\u00e7\u00e3o de inserir elementos<\/strong><\/div>\n

Para cada novo elemento inserido na lista devemos alocar dinamicamente a mem\u00f3ria para armazen\u00e1-lo, e posteriormente fazer o encadeamento na lista. Uma poss\u00edvel implementa\u00e7\u00e3o dessa fun\u00e7\u00e3o \u00e9 exemplificada a seguir. Deve-se observar que a inser\u00e7\u00e3o ocorre sempre no in\u00edcio da lista neste exemplo. A fun\u00e7\u00e3o tem como par\u00e2metros um tipo\u00a0Lista*<\/em>, que representa um ponteiro para o primeiro elemento de uma lista e o valor da informa\u00e7\u00e3o que queremos armazenar.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/section>\n

\n
\u00a0<\/div>\n
\n
\n
\n
\n
\u00a0<\/div>\n<\/div>\n<\/div>\n
\n
\n
\n
\n
\n
\n
\n
\"\"<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n
\n
\u00a0<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/section>\n
\n
\u00a0<\/div>\n
\n
\n
\n
\n
\n
\n
\n
\n
\n

Note que ap\u00f3s alocar a mem\u00f3ria para o novo elemento, devemos atualizar o ponteiro que representa a lista. Nesse caso, o novo n\u00f3 aponta (ou seja,tem como pr\u00f3ximo elemento) para o elemento que era o primeiro da lista. E ent\u00e3o a fun\u00e7\u00e3o retorna a nova lista, representada pelo ponteiro para o novo primeiro elemento.<\/p>\n

\n
\n
\n
\u00a0<\/div>\n<\/div>\n<\/div>\nFun\u00e7\u00e3o para remover um elemento<\/strong><\/div>\n

Se o elemento que queremos remover for o primeiro, devemos fazer o novo valor da lista passar a ser o ponteiro para o segundo elemento, e ent\u00e3o liberamos o espa\u00e7o alocado para o elemento que iremos retirar. Se o elemento a ser removido estiver no meio da lista, devemos fazer com que o elemento anterior passe a apontar para o seguinte a ele, e ent\u00e3o poderemos liberar o espa\u00e7o de mem\u00f3ria (free(p)<\/strong><\/em>).<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/section>\n

\n
\u00a0<\/div>\n
\n
\n
\n
\n
\u00a0<\/div>\n<\/div>\n<\/div>\n
\n
\n
\n
\n
\n
\n
\n
\"\"<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n
\n
\u00a0<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/section>\n
\n
\u00a0<\/div>\n
\n
\n
\n
\n
\n
\n
\n
\n
\n

A fun\u00e7\u00e3o percorre a lista em busca do elemento com o valor enviado como par\u00e2metro, caso o ponteiro\u00a0p\u00a0<\/strong><\/em>tenha como valor final\u00a0NULL<\/strong><\/em>, significa que toda a lista foi percorrida e n\u00e3o foi encontrado o elemento. Caso ele seja diferente de\u00a0NULL<\/strong><\/em>, o elemento foi encontrado e temos dois poss\u00edveis casos j\u00e1 citados anteriormente:<\/p>\n