{{indexmenu_n>9}}
====== 9 - Spojové seznamy, fronta, zásobník ======


===== Procvičované témata =====

  * Dynamická alokace
  * Rekurze
  * Valgrind
  * Spojový seznam
  * Zásobník vs. fronta


===== Úkoly na cvičení =====

  - Implementujte frontu, která bude obsahovat celá čísla, která bude uživatel zadávat z klávesnice.
    - Společně s cvičícím navrhněte vhodnou datovou stukturu, na které bude fronta založena.
    - Společně s cvičícím navrhněte prototypy funkcí, které umožní vkládání dat do fronty (PUSH), odebírání z fronty (POP), dotaz na poslední prvek.
    - Vytvořte funkci, která vypíše na konzoli obsah celé fronty.
    - Nezapomeňte implementovat i funkci, která uvolní všechna data spojená s implementovanou frontou.
    - Kontrolujte správnost dynamické alokace paměti pomocí Valgrindu.
  - Upravte vhodně kód tak, abyste naimplementovali zásobník.
    - S cvičícím diskutujte změny, které jste v kódu provedli.

===== Další úkoly na procvičení =====

  - Implementujte spojový seznam, který v sobě bude obsahovat vždy dvojici dat - dvě celá čísla - první bude datová složka a druhé bude představovat prioritu.
  - Upravte předchozí seznam tak, aby implementoval prioritní frontu tak, aby funkce PUSH od začátku vytvářela vnitřní stukturu seznamu seřazenou podle priority.

===== Ukázkové příklady =====

==== 1. Lineární seznam ====
<code c>
#include <malloc.h>

struct polozka
{
	int data;
	struct polozka * dalsi;
};

struct polozka * insert (struct polozka * a, int d)
{
	struct polozka * tmp = (struct polozka *) malloc(sizeof(struct polozka));
	tmp->data = d;
	tmp->dalsi = a;
	return tmp;
}

int projdi (struct polozka *a)
{
	if (a == NULL) 
		return 0;
	else 
	{
		printf("data: %d\n", a->data);
		projdi (a->dalsi);
	}
}

int main()
{
	struct polozka * seznam = NULL;
	
	seznam = insert(seznam, 10);
	seznam = insert(seznam, 20);
	seznam = insert(seznam, 30);
	
	projdi (seznam);
	
	return 0;
}
</code>

==== 2. Zásobník ====

<code c>
#include <malloc.h>

typedef struct u
{
	int data;
	struct u * predchozi;
} uzel;

uzel * push (uzel * a, int data)
{
	uzel * tmp = (uzel *)malloc(sizeof(uzel));
	tmp->data = data;
	tmp->predchozi = a;
	return tmp;
}

uzel * pop (uzel * a, int * data)
{
	*data = a->data;
	uzel * tmp = a->predchozi;
	free (a);
	return tmp;
}

int main()
{
	int a;
	uzel * zasobnik = NULL;
	
	zasobnik = push (zasobnik, 10);
	zasobnik = push (zasobnik, 33);
	zasobnik = pop (zasobnik, &a);
	printf("pop: %d\n", a);
	zasobnik = pop (zasobnik, &a);
	printf("pop: %d\n", a);
		
	return 0;
}
</code>