на примере структуры данных «Очередь (Queue)»

Самая простая форма интерфейса может выглядеть так:

interface Queue<E>
{
  void add(E e lement);
  Е remove();
  int size();
}

А реализация с-но может сильно варьироваться и определяется классом, реализующим интерфейс «Queue»

class CircularArrayQueue<E> implements Queue<E>
{
	CircularArrayQueue(int capacity)
	public void add(E element)
	public Е remove ()
	public int size () 
	private Е[] elements;
	private int head;
	private int tail;
}
// или 
class LinkedListQueue<E> implements Queue<E>
{
	LinkedListQueue ()
	void add (Е element)
	public Е remove ()
	public int size()
	private Link head;
	private Link tail;
}

Интерфейс Collection

Основополагающий для классов коллекций

public interface Collection<E>
{
  boolean add(E element);
  Iterator<E> iterator();
}

Итераторы

public interface Iterator<E>
{
  E next();
  boolean hasNext();
  void remove();
}

Нужно проверять наличие через «hasNext()» иначе генерится исключение при достижении конца
Порядок в котором перебираются элементы, зависит от типа коллекции, может быть последовательный а может быть и случайный
Итераторы в java отличаются от сишных, к ним не применим инкремент, они не моделируются по индексам, скорее это «объекты между элементами», он возвращает ссылку на элемент который он только что «прошел», когда перескочил при вызове «next()«
Тобишь для каких либо д-й с итератором, его нужно позиционировать, затем вызывать например «remove()», примечательно что после этого он автоматом не перепозиционируется, и для повторного remove() надо повторно вызывать next()

Notes

Связные списки
Двунаправленные элементы, т.е. в каждом элементе хранится ссылка предшествующего и последующего элемента, благодаря этому операция удаления в середине дается дешево

Списочные массивы
Интерфейс List описывает упорядоченную коллекцию, в которое имеет значение расположение элемента
К слову, отличие Vector и ArrayList в том что первый потокобезопасный, но на это тратятся доп ресурсы, а второй нет, с-но выбор зависит от задач и баланса эффективности

Хеш-множества
Более эффективный поиск элементов в списке
Из-за специфики реализации, элементы располагаются (извлекаются) с (псвдо-)случайном порядке

Древовидные множества
Основным отличием является то что все элементы в нем всегда отсортированы, сортируются они сразу же перед записью, вычисляется место для вставки
Работает немного медленнее чем хеш, но многое зависит от типа данных, должен быть реализован интерфейс «comparable» для сравнения элементов

Одно- и двустроние очереди
Впринципе рассмотрено уже
Так же существуют очереди по приоритету