Algoritmo
Um algoritmo é uma seqüência de passos que resolve algum problema ou alcança algum objetivo, como a seqüência de passos para resolver o problema de descobrir a máxima altura. É importante salientar que um algoritmo simplesmente diz o que deve ser feito.
Estrutura de Dados
Uma agenda de celular pode ser vista como uma estrutura de dados. Uma estrutura de dados mantém os dados organizados seguindo alguma lógica e disponibiliza operações para o usuário manipular os dados.
Cada celular pode implementar a sua agenda de contatos de uma forma totalmente diferente um do outro, na tentativa de obter mais performance, ser mais confiável ou gastar menos memória. Porém o conjunto básico de operações oferecidas pelas agendas é sempre o mesmo. Isso facilita a vida do usuário pois se ele tiver que trocar de celular não vai ter que aprender novamente como usar uma agenda de contatos.
Essa é a grande vantagem em se pensar em interface. Mantida a interface, podemos trocar uma agenda que não é tão eficiente ou que já não atende mais as nossas necessidades por outra mais eficiente ou adequada, sem problemas em ter de aprender a usar a nova agenda: troca-se a implementação, mas não mudamos a interface.
Fonte: http://www.ime.usp.br/~cosen/verao/alg.pdf