Elementarne struktury danych: stos kolejka
C, wiem e bana, ale od czego trzeba w kocu zacz. Stos jest struktur typu LIFO Last In First Out, czyli element wchodzcy na kocu zostanie pobrany na pocztku. Na stosie s moliwe do wykonania dwie operacje: dodanie do stosu i pobranie ze stosu, obydwie dziaaj w czasie O1, czyli staym. Dodatkowo mona taki stos zresetowa, co sprowadza si do ustawienia liczby elementw na nim odoonych na 0. Z reguy stosu nie robi si dynamicznego czyli z alokowaniem i zwalnianiem pamici w trakcie dziaania, poniewa bardzo spowalnia to dziaanie programu. Poniej przykadowa implementacja stosu.
struct stack
int n, m1000
inline void push stack *s, int x //w tej procedurze popychamy elemencik na stos:
s-ms-n++x
inline int pop stack *s //a w tej go z niego cigamy:
return s-m--s-n
inline int reset stack *s //resetowanie stosu jest jak wida banalnie proste:
s-n0
Kolejka jest struktur typy FIFO First In First Out, czyli element wchodzcy na pocztku jest pobierany jako w pierwszej kolejnoci itd. itp. Znw moemy wykona dwie operacje, ktre znowu dziaaj w czasie O1. Podobnie jak przy stosie, raczej nie stosuje si dynamicznych kolejek. Przykadowa implementacja:
const int qsize 1000
struct queque
int h, t, mqsize //head, tail czyli gwka ogonek owej kolejki
inline void enqueque queque *q, int x
q-mq-h++x
if q-hqsize //kiedy gwka wychodzi poza tablice dajemy j na pocztek
q-h0 //trzeba tylko uwaa, eby nie przekroczy liczby elementw
inline int dequeque queque *q
int tmp q-mq-t++
if q-tqsize //to samo co dla gwki
q-t0
return tmp
inline int reset queque *q //czasami trzeba zresetowa tak kolejk, co jak wida dugo nie trwa:
q-hq-t0
Nostre/Marsmellow