Abstraktní datové typy
Aplikace a implementace zásobníku a fronty
 Vytisknout studijní materiál

Zadání:

1. Implementujte zásobník pro znaky pomocí spojového seznamu. Napište program, který bude provádět kontrolu parity závorek (obecně různého typu). Otevírací závorky se ukládají do zásobníku. Po nalezení zavírací závorky musí být stejná na vrcholu zásobníku a tato se ze zásobníku vybere. Vypisujte postupně obsah zásobníku do řádků s přidáváním a ubíráním prvků zprava. Na konci, při správné paritě závorek, musí být zásobník prázdný.

Vzor vstupu 1:

{ [ ( a + b) * ( c - d ) + e ] / f }

Vzor výstupu 1:

{

{ [

{ [ (

{ [

{ [ (

{ [

{

Zásobník je prázdný. Ok!

Vzor vstupu 2:

{ [ ( a + b} * ( c - d ) + e ] / f }

Vzor výstupu 2:

{

{ [

{ [ (

Chyba - chybí pravá závorka k (

Vzor vstupu 3:

{ ( a + b) * ( c - d) + e] / f }

Vzor výstupu 3:

{

{ (

{

{ (

{

Chyba - chybí pravá závorka k {

Vzor vstupu 4:

[ ( a + b) * ( c - d) + e ] / f }

Vzor výstupu 4:

[

[ (

[

[ (

[

Zásobník je prázdný.

Chyba-chybí levá závorka k }

2. Implementujte frontu pro znaky pomocí pole. Napište program pro vytvoření a práci s dynamickou datovou strukturou fronta. Předpokládejte, že do banky k přepážkám přicházejí (p) klienti, kteří dostanou pořadové číslo a zařadí se do fronty. Pak jsou postupně u přepážek obslouženi (o). Vytvořte simulační demo.

Vzor vstupu 1:

p   p   p   o   p   o   o   o

Vzor výstupu 1:

1

1   2

1   2    3

2   3

2   3    4

3   4

4

fronta prázdná

Vzor vstupu 2:

p   o   p   p    o    o   o

Vzor výstupu 2:

1

Fronta je prázdná.

2

2   3

3

Fronta je prázdná.

Chyba - fronta je prázdná.