Elementarne struktury danych: stos & kolejka

C¢¾, wiem ¾e banaˆ, ale od czego˜ trzeba w koäcu zacz¥†. Stos jest struktur¥ typu LIFO (Last In First Out), czyli element wchodz¥cy na koäcu zostanie pobrany na pocz¥tku. Na stosie s¥ mo¾liwe do wykonania dwie operacje: dodanie do stosu i pobranie ze stosu, obydwie dziaˆaj¥ w czasie O(1), czyli staˆym. Dodatkowo mo¾na taki stos zresetowa†, co sprowadza si© do ustawienia liczby element¢w na nim odˆo¾onych na 0. Z reguˆy stosu nie robi si© dynamicznego (czyli z alokowaniem i zwalnianiem pami©ci w trakcie dziaˆania), poniewa¾ bardzo spowalnia to dziaˆanie programu. Poni¾ej przykˆadowa implementacja stosu.

struct stack {
 int n, m[1000];
};

inline void push (stack *s, int x) //w tej procedurze popychamy elemencik na stos:)
{
 s->m[s->n++]=x;
}

inline int pop (stack *s) //a w tej go z niego ˜ci¥gamy:)
{
 return s->m[--s->n];
}

inline int reset (stack *s) //resetowanie stosu jest jak wida† banalnie proste:)
{
 s->n=0;
}
	
	Kolejka jest struktur¥ typy FIFO (First In First Out), czyli element wchodz¥cy na pocz¥tku jest pobierany jako w pierwszej kolejno˜ci itd. itp. Zn¢w mo¾emy wykona† dwie operacje, kt¢re znowu dziaˆaj¥ w czasie O(1). Podobnie jak przy stosie, raczej nie stosuje si© dynamicznych kolejek. Przykˆadowa implementacja:

const int qsize = 1000;

struct queque {
 int h, t, m[qsize]; //head, tail czyli gˆ¢wka & ogonek owej kolejki
};

inline void enqueque (queque *q, int x)
{
 q->m[q->h++]=x;
 if (q->h==qsize) //kiedy gˆ¢wka wychodzi poza tablice dajemy j¥ na pocz¥tek
  q->h=0;         //trzeba tylko uwa¾a†, ¾eby nie przekroczy† liczby element¢w
}

inline int dequeque (queque *q)
{
 int tmp = q->m[q->t++];
 if (q->t==qsize) //to samo co dla gˆ¢wki
  q->t=0;
 return tmp;
}

inline int reset (queque *q) //czasami trzeba zresetowa† tak¥ kolejk©, co jak wida† dˆugo nie trwa:)
{
 q->h=q->t=0;
}


Nostre/Marsmellow