Container

From Alda
Jump to navigationJump to search

Container verwalten eine Menge von Datenobjekten.

mögliche Operationen

v = value)

c.size() ist immer unterstützt

  • 1 a) v = c.get(i) / b)v = c.get(pos)
       ites Objekt suchen
  • 2 v.set(i, value)
       ites Element überschreiben
  • 3 a) v = c.first/last
  • 4 v = c.largest/smallest
  • 5 v = c.get(key)
       Verallgemeinerung von 1 für beliebige Schlüssel
  • 6 c.append(v)
       Objekt am Ende anhängen
  • 7 c.prepend(v)
       Objekt vorne einfügen
  • 8 c.insert(i, v)
       Objekt an beliebiger Position einfügen
  • 9 c.insert(key, v)
  • 10 c.removeFirst/Last()
  • 11 c.remove(i)
  • 12 c.remove(key)
  • 13 c.removeSmallest/Largest()

Facts

  • Jede dieser Operationen kann sehr effizient implementiert werden.
  • Keine Datenstruktur ist bekannt die alle diese Operationen effizient implementiert.

Beispiele

  • Array: unterstützt die ersten 3
  • dynamischens Array: wie Array, zusätzlich c.append & c.removeLast
  • Dictionnary: wie Array ausserdem c.geht(key), c.insert(key,value), c.remove(key)
  • verkettete Liste:c.first(), c.insert(pos, value), c.remove(pos), c.get(pos)
  • doppelt verkettete Liste:* wie Liste + ...
  • Stack(Stapel): LIFO (Last In First Out) c.last(), c.append(), c.removeLast()
  • Queue: FIFO (First In First Out) c.first(), c.append(), c.removeFirst()
  • Deque: (Double Ended Queue) wie STACK + QUEUE
  • MinPriorityQueue: c.smallest(), c.removeSmallest(), c.insert()
  • MaxPriorityQueue: c.largest(), c.removeLargest(), c.insert()
  • MinMaxPriorityQueue: MinPriorityQueue + MaxPriorityQueue