4. Lister, stakker og køer

4.1 ADT'er

ADT står for Abstrakt DataType. En ADT er et sett objekter sammen med et sett operasjoner. Abstrakte datatyper er matematiske abstraksjoner. Det defineres ikke i ADT'en hvordan operasjonene er implementert. Objekter sånn som lister, sett, og grafer, sammen med deres operasjoner, kan sees som abstrakte datatyper, akkurat som heltall, realtall og boolske tall er datatyper. (-Oversatt etter Weiss)

4.2 Lister

4.2.0 En kuriositet

En uortodoks og vakker måte å innsette og slette objekter i en lenket liste: program.

4.3 Stakker

På en "stakk" (eng. stack - stabel) kan du legge elementer på i en ende, og fjerne fra den samme enden, akkurat som med en stabel tallerkener. Stakken er altså en liste med LIFO-struktur: Last In, First Out. Det elementet du la sist på stakken, er det første du må plukke av den. Å legge noe på stakken blir gjerne kalt å "pushe" noe på stakken, å fjerne blir kalt å "pope" (fra eng. push & pop). I tillegg velger noen å definere funksjonaliteten "top", som går ut på at man får se det øverste objektet uten å pop'e det, og da kaller de gjerne funksjonen som både skal vise og pop'e det øverste objektet for "topAndPop" e.l. Programeksemplene bruker den gode gamle varianten, der "pop" både returnerer øverste element og fjerner det fra stakken.

4.3.1 Array-implementasjon

(Etter Sedgewick) 
typedef int itemType;
typedef int BOOL;
class Stack {
        private:
                itemType *stack;
                int p;
        public:
                Stack(int max=100)
                        { stack = new itemType[max]; p=0; }
                ~Stack()
                        { delete stack; }
                inline void push(itemType v)
                        { stack[p++] = v; }
                inline itemType pop()
                        { return stack[--p]; }
                inline BOOL empty()
        { return !p; }
};

4.3.2 Lenket liste-implementasjon

(Etter Sedgewick) 
#include <iostream.h>
#include <conio.h>
typedef char itemType;
class Stack {
 public:
  Stack(int max);
  ~Stack();
  void push(itemType v);
  itemType pop();
  int empty();
 private:
  struct node
   { itemType key; struct node *next; };
  struct node *head, *z;
};
Stack::Stack(int max) {
 head = new node; z = new node;
 head->next=z; z->next=z;
}
Stack::~Stack() {
 struct node *t = head;
 while (t!=z)
  { head = t; t=t->next; delete head; }
}
void Stack::push(itemType v) {
 struct node *t = new node;
 t->key = v; t->next=head->next;
 head->next=t;
}
itemType Stack::pop() {
 itemType x;
 stuct *node t = head->next;
 head->next = t->next; x=t->key;
 delete t; return x;
}
int Stack::empty()
 { return head->next==z; }

4.3.3 Bruksområder

Stakker kan brukes til mye forskjellig, her skal jeg bare gi et eksempel: å balansere symboler. I et C(++) program skal parentesene balansere. Vær oppmerksom på at det er noen særtilfeller dette programmet ikke takler. Er det noen som har en løsning, blir jeg glad for det.
Balanseringprogram

4.4 Køer

 I likhet med stakker, er køer lister, men i køer setter man inn i den ene enden, og sletter i den andre (FIFO-struktur: First In, First Out).
queue.cpp (Etter Sedgewick)
 

4.4.x Deque

En "deque" er en litt spesiel kø; en kø der du kan legge til i begge ender, men bare slette fra den ene. Det vil si at en deque typisk har funksjonene "pop", "push" og "put".
Deque'er brukes for eksempel til å lage programmer som matcher mønstre. For teorien her, se Sedgewick.
match.cpp
ASCII-tegning av mønster-maskinen, og hendelsesforløp i programmet.