ALGORITMI I STRUKTURE PODATAKA

 

 

1.  Podsećanje: Koji rezultat vraćaju funkcije floor(x), ceil(x) u programskom jeziku C, ako x=4.7?

 

Neka x∈ℝ. Važi da: x-1<⌊x⌋<=x<=⌈x⌉<x+1

Koliko je ⌊7.51⌋, ⌈7.51⌉?

Neka n∈ℕ. Važi da: ⌊n/2⌋+⌈n/2⌉=n

 

2.  Podsećanje: 

Odredite vremensku slozenost sledecih fragmenata programskog kôda.

Broj koraka prikazati u obliku polinomijalnog izraza i O notaciji.

 

if (x == 0)

   for (i=0; i<=n-1; i++)

       for (j=0; j<n; j++) A[i][ j] = 0;

else for (i=0;i<=n-1;i++) A[i][ i] = 1;

 

2 Strukture podataka: stek, povezana lista, red

 

Na pretprošlom času smo na primerima videli da programer izborom strukture podataka može da utiče na efikasnost konstruisanog algoritama.

Zato je važno poznavati tehnike rada sa strukturama podataka, ali i složenost pojedinih operacija nad strukturom podataka.

 

PROGRAM = ALGORITAM + STRUKTURA PODATAKA


Strukture podataka se mogu grubo klasifikovati:
linearne i nelinearne (ako se gledaju relacije elemenata u susedstvu)
      Navedite primer linearne i nelinearne strukture.
statičke i dinamičke (ako se gledaju kapaciteti i mogućnost izmene veličine)
      Navedite primer statičke i dinamičke strukture.

 

Podsećanje:

 

1. Koje podatke o povezanoj listi  najčešće moramo da imamo?

 

2. Koje su najčešće operacije nad elementima liste?

 

3. Navedite na koji način se mogu implementirati liste?

 

4. Koja je prednost dvostruko povezanih lista u odnosu na (jednostruko povezane) liste?

 

5. Definišite kružnu listu? Gde se koristi?

 

6. Opišite FIFO i LIFO principe rada.

 

7. Koje podatke o steku najčešće moramo da imamo?

 

8. Koje su najčešće operacije nad elementima steka?

 

9. Navedite bar dve primene steka.

 

2.1  STEK

STEK - kolekcija podataka sa kojima se radi po LIFO(Last In First Out) principu;

Procedure za rad sa stekom

    Da li je stek prazan

     Postavi element na vrh steka  (tzv. operacija PUSH)

     Skini element sa vrha steka    (tzv. operacija POP)

Stek je prazan ako mu se vrh nije pomerio iz inicijalnog stanja.  

Funkcijom push se formira sadrzaj steka - dodavanjem elemenata na vrh steka.

Funkcijom pop elementi se uzimaju sa steka po LIFO redosledu (najpre se uzima element sa vrha steka)

Upotreba steka:

IV glava K&R - primer sa kalkulatorom i izračunavanje u postfiks notaciji (Shunting-yard algoritam) (podsećanje: AB+ ~ A+B,         ABCD-*+EF-G*H/+ ~ A+B*(C-D)+(E-F)*G/H ) ,

provera uparenosti HTML etiketa,

provera uparivanja zagrada (leksička analiza,)

kod editora teksta (editovanje reda),

pri rekurziji i pozivu potprograma

Ako se pokuša skidanja elementa sa praznog steka, nastaje potkoračenje (underflow).

Stek ograničenog kapaciteta (sa MAX elemenata) se može implementirati pomoću niza Stek[0..MAX-1]
tako da element Stek[0] je na dnu steka, element Stek[MAX-1] je na vrhu steka.
Ako se pokuša umetanje elementa na poziciju MAX, nastaje prekoračenje (overflow).

1.  NCP (napisati C program) koji će proveriti uparenost etiketa u ulaznoj HTML datoteci.
Složena etiketa A (poseduje otvaracA i zatvaracA) je korektno ugnježdena u etiketu B ako je otvaracA iza otvaracB i zatvaracA ispred zatvaracB.

Pretpostaviti da u ulaznoj datoteci nema prostih etiketa (onih koje nemaju zatvarac).

Jednostavnosti radi, pretpostaviti da maksimalna dubina ugnježdenosti je do nivoa 3

(dakle, nivo tipa <B><I>...</I> <I><p> </p></i></b> se pojavljuje, dok nivo tipa <B><I>...<p><a href="nesto.htm">...</A> </p></i></b> se ne pojavljuje). 

Pretpostaviti da nazivi etiketa su jednoslovni (P,Q,B,I,U,S,A,...).

Pri nailasku na nekorektno uparenu etiketu, prekinuti dalju proveru i ispisati poruku o grešci na standardni izlaz.
 TEST PRIMER:
<P align="center">Pasus 1 </P>
<p><B><q>Citat 1</q> <A href="link1.htm"> Hiperveza 1 </a> <Q> Citat 2 </q> ... </b>...</p>
<p><q>Citat 2</Q> <A href="link2.html"> Hiperveza 2 </a> <B> <A href="link3.htm"> Hiperveza 3 </a>...</B> </P>

IDEJA:  

 Svaka otvorena etiketa stavi se na stek 
 Pri nailasku na zatvorenu etikete proveravamo da li je stek prazan. 
       Ako jeste,  nekorektna uparenost. 
 Takođe se proveri i  da li se na vrhu steka za tekucu zatvorenu etiketu nalazi odgovarajuca otvorena etiketa. 
    Ako ne, nekorektna uparenost. Ako da, skine se otvorena etiketa sa vrha steka. 
 

    Prazan stek
P
    push(P)
    pop(), provera </p > == pop()
P
    push(P)
P B
    push(B)
P B Q
    push(Q)
P B
    provera </q > == pop() 

#include <stdio.h>
#include <ctype.h>
 
#define MAX  3  /*maksimalna dubina steka*/
void push(char); /*stavlja etiketu na stek */
char pop(void); /*vraca etiketu skinutu sa vrha steka */
 
/*globalne promenljive */
char Stek[MAX];  /*stek realizovan kao niz*/
int vrh;  /*naredna slobodna pozicija na steku */
int greska=0; /*indikator nailaska na pojavu nekorektne ugnjezdenosti*/ 
main()
{
    int c; /*znak sa ulaza*/
    int rez; /*rezultat skidanja sa steka*/
    
  while ( (c=getchar()) != EOF  && !greska)
     if (c=='<')
     {   if (isalnum(c=getchar()) )  push(toupper(c)); 
                 /*etiketa otvarac(<isalnum...) se stavlja na stek, 
                   naziv se bez  smanjenja opstosti
                   smesta veliki slovima u steku, zbog kasnijeg case insensitive  
                   poredjenja naziva etiketa otvaraca i zatvaraca; ne zaboravite   
                   da u HTMLu je naziv iste etikete i <Table> i <taBLE> */
 
          if (c=='/')  /*obrada zatvaraca, ali samo ako je oblika </slovo...> */
             { if (isalnum(c=getchar()) )  rez=pop();
                if (toupper(c) != rez)  {printf("Greska: etiketa %c\n", c);
                                         greska=1; }
             }
     }
 
    if (!greska) printf("\nKorektna uparenost unutar HTML datoteke\n");
}
 
void push(char c)  /*smesta etiketu c na vrh steka */
{    if (vrh<MAX) Stek[vrh++]=c;
     else { greska=1;
printf("\nGreska: stek je pun, dubina je %d, nemoguce je smestiti %c\n", MAX, c);
          }
}  //T(n)=O(1), gde je n duzina steka
 
char pop(void) /*kao rezultat daje etiketu skinutu sa vrha steka*/
{
   if (vrh>0) return Stek[--vrh];
   else { greska=1; printf("\nGreska: stek je prazan\n");  return 0; }
 }  //T(n)=O(1), gde je n duzina steka
   

2. Jednodimenzioni niz može se iskoristiti za smeštanje dva steka tako da prvi stek raste nagore od levog kraja niza,

a drugi stek raste nadole sa desnog kraja niza.

 Implementirajte stek operacije (kreiranje steka, provera da li je stek prazan, provera da li je stek pun, umetanje elementa u stek, uklanjanje elementa sa steka) za ovaj niz.

Ocenite vremensku složenost svake operacije (O notacija). Pretpostaviti da niz pozitivnih celih brojeva je dimeznije n.

 

RESENJE:

Neka su globalne promenljive

A - niz pozitivnih celih brojeva dimenzije n koji se koristi za smeštanje stekova

S1- indeks člana niza A koji pripada steku koji raste nagore od levog kraja

S2 - indeks člana niza A koji pripada steku koji raste nadole od desnog kraja.

 

int Stack-Stvori1(void)  {  S1 = -1;  return S1; }

 

int StackStvori2(int n) { S2 = n; return S2; }

 

int StackPrazan1(void) { if (S1 = = -1) return 1; else return 0; }

 

int StackPrazan2(int n) {if (S2 == n) return 1; else return 0; }

 

int StackPun(void) {if (S1 >= S2-1) return 1; else return 0; }

 

void PushS1(int x)

{ if (StackPun() {printf(“Prekoracenje “); exit(1); }

   else  {  S1 = S1 + 1; A[S1] = x;}

}

 

void PushS2(int x)

{

   if (StackPun() {printf(“Prekoracenje “); exit(1); }

   else { S2 = S2 − 1; A[S2] = x;}

}

 

int PopS1(void)

{

    int x=0; /* clan niza pozitivnih celih brojeva */

    if (!StackPrazan1() ) /* ako nije 1. stek prazan */

      {  x = A[S1]; S1--; return x;}

    else {printf(“Potkoracenje “); exit(1); }       

}

 

int PopS2(int n)

{  int x=0;

    if (!StackPrazan2(n) ) /* ako nije 2. stek prazan */

        { x = A[S2];  S2++; return x;}

    else {printf(“Potkoracenje “); exit(1); }

}

 

Vreme izvrsavanja svih operacija za rad sa stekom je O(1).

 

 

2.2  POVEZANA LISTA

 

Povezana lista je struktura podataka čiji su elementi uređeni linearno. Ali, za razliku od niza, čije linearno uređenje

 je određeno nizom indeksa, kod povezane liste je uređenje određeno pokazivačem u svakom od objekata.

 

Liste su vrlo rasprostranjene u programiranju – lista događaja, lista poruka, predstavljanje polinoma,…


 

Lista može biti jednostruko, dvostruko povezana. Može biti sortirana ili ne, može biti kružna ili ne.

        
3. /* Rad sa povezanom listom - iterativne verzije funkcija za rad sa povezanom listom                 */
 
 
#include <stdio.h>
#include <stdlib.h>
typedef struct elem { int broj; struct elem *sled; } Elem; /*Element liste*/
 
int duz (Elem *lst);                    /* Broj elemenata liste.          */
void pisi (Elem *lst);                  /* Ispisivanje liste.             */
Elem *na_pocetak (Elem *lst, int b);    /* Dodavanje na pocetak.          */
Elem *na_kraj (Elem *lst, int b);       /* Dodavanje na kraj.             */
Elem *citaj1 (int n);    /* Citanje liste stavljajuci brojeve na pocetak. */
Elem *citaj2 (int n);    /* Citanje liste stavljajuci brojeve na kraj.    */
Elem *umetni (Elem *lst, int b);        /* Umetanje u uredjenu listu.     */
void brisi (Elem *lst);                 /* Brisanje svih elemenata liste. */
Elem *izostavi (Elem *lst, int b); /* Izostavljanje svakog pojavljivanja. */
 
 
void main () {
  Elem *lst = NULL; int kraj = 0, izbor, broj, n;
  while (!kraj) {
    printf ("\n1. Dodavanje broja na pocetak liste\n"
              "2. Dodavanje broja na kraj liste\n"
              "3. Umetanje broja u uredjenu listu\n"
              "4. Izostavljanje broja iz liste\n"
              "5. Brisanje svih elemenata liste\n"
              "6. Citanje uz obrtanje redosleda brojeva\n"
              "7. Citanje uz cuvanje redosleda brojeva\n"
              "8. Odredjivanje duzine liste\n"
              "9. Ispisivanje liste\n"
              "0. Zavrsetak rada\n\n"
              "Vas izbor? "
            );
    scanf ("%d", &izbor);
    switch (izbor) {
    case 1: case 2: case 3: case 4:
      printf ("Broj?      "); scanf ("%d", &broj);
      switch (izbor) {
      case 1: /* Dodavanje broja na pocetak liste: */ 
        lst = na_pocetak (lst, broj); break;
      case 2: /* Dodavanje broja na kraj liste: */
        lst = na_kraj (lst, broj);    break;
      case 3: /* Umetanje broja u uredjenu listu: */
        lst = umetni (lst, broj);     break;
      case 4: /* Izostavljanje broja iz liste: */
        lst = izostavi (lst, broj);   break;
      }
      break;
    case 5: /* Brisanje svih elemenata liste: */
      brisi (lst); lst = NULL; break;
    case 6: case 7: /* Citanje liste: */
      printf ("Duzina?    "); scanf ("%d", &n);
      printf ("Elementi?  "); brisi (lst);
      switch (izbor) {
      case 6: /* uz obrtanje redosleda brojeva: */
        lst = citaj1 (n); break;
      case 7: /* uz cuvanje redosleda brojeva: */
        lst = citaj2 (n); break;
      }
      break;
    case 8: /* Odredjivanje duzine liste: */
      printf ("Duzina=    %d\n", duz (lst)); break;
    case 9: /* Ispisivanje liste: */
      printf ("Lista=     "); pisi (lst); putchar ('\n'); break;
    case 0: /* Zavrsetak rada: */
      kraj = 1; break;
    default: /* Pogresan izbor: */
      printf ("*** Neozvoljeni izbor! ***\a\n"); break;
    }
  }
}
  
/* Definicije  funkcija za obradu lista (iterativno).    */
  
int duz (Elem *lst) {                   /* Broj elemenata liste.          */
  int n = 0; while (lst) { n++; lst = lst -> sled; } return n;
}
 
void pisi (Elem *lst) {                 /* Ispisivanje liste.             */
  while (lst) { printf ("%d ", lst->broj); lst = lst -> sled; }
}
 Elem *na_pocetak (Elem *lst, int b) {   /* Dodavanje na pocetak.          */
  Elem *novi = malloc (sizeof(Elem));
  novi->broj = b; novi->sled = lst;
  return novi;
}
 //T(n)=O(1), gde je n duzina liste
 
Elem *na_kraj (Elem *lst, int b) {      /* Dodavanje na kraj.             */
  Elem *novi = malloc (sizeof(Elem));
  novi->broj = b; novi->sled = NULL;
  if (!lst) return novi;
  else {
    Elem *tek = lst;
    while (tek->sled) tek = tek->sled;
    tek->sled = novi;
    return lst;
  }
}
 
Elem *citaj1 (int n) {   /* Citanje liste stavljajuci brojeve na pocetak. */
  Elem *prvi = NULL; int i;
  for (i=0; i<n; i++) {
    Elem *novi = malloc (sizeof(Elem));
    scanf ("%d", &novi->broj); novi->sled = prvi;
    prvi = novi;
  }
  return prvi;
}
 
Elem *citaj2 (int n) {   /* Citanje liste stavljajuci brojeve na kraj.    */
  Elem *prvi = NULL, *posl = NULL; int i;
  for (i=0; i<n; i++) {
    Elem *novi = malloc (sizeof(Elem));
    scanf ("%d", &novi->broj); novi->sled = NULL;
    if (!prvi) prvi = novi; else posl->sled = novi;
    posl = novi;
  }
  return prvi;
}
 
Elem *umetni (Elem *lst, int b) {       /* Umetanje u uredjenu listu.     */
  Elem *tek = lst, *pret = NULL, *novi;
  while (tek && tek->broj < b) { pret = tek; tek = tek->sled; }
  novi = malloc (sizeof(Elem));
  novi->broj = b; novi->sled = tek;
  if (!pret) lst = novi; else pret->sled = novi;
  return lst;
} //T(n)=O(n), gde je n duzina liste, jer u najgorem slučaju možda moramo da
//prođemo celu listu dok nađemo član sa informacionim poljem b
 
void brisi (Elem *lst) {                /* Brisanje svih elemenata liste. */
  while (lst) { Elem *stari = lst; lst = lst->sled; free (stari); }
}
 
 
 
Elem *izostavi (Elem *lst, int b){/*Izostavljanje svakog pojavljivanja clana b*/
  Elem *tek = lst, *pret = NULL;
  while (tek)
    if (tek->broj != b) { pret = tek; tek = tek->sled; }
    else {
      Elem *stari = tek;
      tek = tek->sled;
      if (!pret) lst = tek; else pret->sled = tek;
      free (stari);
    }
  return lst;
} //T(n)=O(n), gde je n duzina liste, jer moramo daprođemo celu listu dok nađemo 
//sve članove sa informacionim poljem b
 
 

4. /* Rad sa povezanom listom - REKURZIVNE verzije funkcija za rad sa povezanom listom; UPOREDITI SA PRETHODNIM  ZADATKOM               */ 

#include <stdio.h>
#include <stdlib.h>
 
typedef struct elem { int broj; struct elem *sled; } Elem; /*Element liste*/
 
int duz (Elem *lst);                    /* Broj elemenata liste.          */
void pisi (Elem *lst);                  /* Ispisivanje liste.             */
Elem *na_pocetak (Elem *lst, int b);    /* Dodavanje na pocetak.          */
Elem *na_kraj (Elem *lst, int b);       /* Dodavanje na kraj.             */
Elem *citaj1 (int n);    /* Citanje liste stavljajuci brojeve na pocetak. */
Elem *citaj2 (int n);    /* Citanje liste stavljajuci brojeve na kraj.    */
Elem *umetni (Elem *lst, int b);        /* Umetanje u uredjenu listu.     */
void brisi (Elem *lst);                 /* Brisanje svih elemenata liste. */
Elem *izostavi (Elem *lst, int b); /* Izostavljanje svakog pojavljivanja. */
  
void main () {
  Elem *lst = NULL; int kraj = 0, izbor, broj, n;
  while (!kraj) {
    printf ("\n1. Dodavanje broja na pocetak liste\n"
              "2. Dodavanje broja na kraj liste\n"
              "3. Umetanje broja u uredjenu listu\n"
              "4. Izostavljanje broja iz liste\n"
              "5. Brisanje svih elemenata liste\n"
              "6. Citanje uz obrtanje redosleda brojeva\n"
              "7. Citanje uz cuvanje redosleda brojeva\n"
              "8. Odredjivanje duzine liste\n"
              "9. Ispisivanje liste\n"
              "0. Zavrsetak rada\n\n"
              "Vas izbor? "
            );
    scanf ("%d", &izbor);
    switch (izbor) {
    case 1: case 2: case 3: case 4:
      printf ("Broj?      "); scanf ("%d", &broj);
      switch (izbor) {
      case 1: /* Dodavanje broja na pocetak liste: */
        lst = na_pocetak (lst, broj); break;
      case 2: /* Dodavanje broja na kraj liste: */
        lst = na_kraj (lst, broj);    break;
      case 3: /* Umetanje broja u uredjenu listu: */
        lst = umetni (lst, broj);     break;
      case 4: /* Izostavljanje broja iz liste: */
        lst = izostavi (lst, broj);   break;
      }
      break;
    case 5: /* Brisanje svih elemenata liste: */
      brisi (lst); lst = NULL; break;
    case 6: case 7: /* Citanje liste: */
      printf ("Duzina?    "); scanf ("%d", &n);
      printf ("Elementi?  "); brisi (lst);
      switch (izbor) {
      case 6: /* uz obrtanje redosleda brojeva: */
        lst = citaj1 (n); break;
      case 7: /* uz cuvanje redosleda brojeva: */
        lst = citaj2 (n); break;
      }
      break;
    case 8: /* Odredjivanje duzine liste: */
      printf ("Duzina=    %d\n", duz (lst)); break;
    case 9: /* Ispisivanje liste: */
      printf ("Lista=     "); pisi (lst); putchar ('\n'); break;
    case 0: /* Zavrsetak rada: */
      kraj = 1; break;
    default: /* Pogresan izbor: */
      printf ("*** Neozvoljeni izbor! ***\a\n"); break;
    }
  }
}
 
 
/* Definicije  funkcija za obradu lista (REKURZIVNO).    */ 
int duz (Elem *lst) {                   /* Broj elemenata liste.          */
  return lst ? duz (lst->sled) + 1 : 0;
}
 
void pisi (Elem *lst) {                 /* Ispisivanje liste.             */
  if (lst) { printf ("%d ", lst->broj); pisi (lst->sled); }
}
  
Elem *na_pocetak (Elem *lst, int b) {   /* Dodavanje na pocetak.          */
  Elem *novi = malloc (sizeof(Elem));
  novi->broj = b; novi->sled = lst;
  return novi;
}
 
Elem *na_kraj (Elem *lst, int b) {      /* Dodavanje na kraj.             */
  if (!lst) {
   lst = malloc (sizeof(Elem));
   lst->broj = b; lst->sled = NULL;
 } else
   lst->sled = na_kraj (lst->sled, b);
 return lst;
}
 
Elem *citaj1 (int n) {   /* Citanje liste uz obrtanje redosleda.          */
  if (n == 0) return NULL;
  else {
    Elem *novi = malloc (sizeof(Elem));
    novi->sled = citaj1 (n - 1); scanf ("%d", &novi->broj);
    return novi;
  }
}
 
Elem *citaj2 (int n) {   /* Citanje liste uz cuvanje redosleda.           */
  if (n == 0) return NULL;
  else {
    Elem *novi = malloc (sizeof(Elem));
    scanf ("%d", &novi->broj); novi->sled = citaj2 (n - 1);
    return novi;
  }
} 
Elem *umetni (Elem *lst, int b) {       /* Umetanje u uredjenu listu.     */
  if (!lst || lst->broj >= b) {
    Elem *novi = malloc (sizeof(Elem));
    novi->broj = b; novi->sled = lst;
    return novi;
  } else {
    lst->sled = umetni (lst->sled, b);
    return lst;
  }
}
 
void brisi (Elem *lst) {                /* Brisanje svih elemenata liste. */
  if (lst) { brisi (lst->sled); free (lst); }
}
 
Elem *izostavi (Elem *lst, int b){ /* Izostavljanje svakog pojavljivanja. */
  if (lst) {
    if (lst->broj !=  b) {
      lst->sled = izostavi (lst->sled, b);
    } else {
      Elem *stari = lst;
      lst = izostavi (lst->sled, b);
      free (stari);
    }
  }
  return lst;
}
 
 




2.3 DVOSTRUKO POVEZANA LISTA



Svaki element dvostruko povezane liste ima informaciono polje (npr. broj) i dva pokazivača: pret, sled. 
Ako pret=NULL, taj element nema prethodnika, tj. on je glava liste. 
Ako sled=NULL, taj element nema sledbenika, tj. on je rep liste.
 
Ponekad je pogodno da se kretanje kroz listu, od elementa do elementa vrši u oba smera (napred i nazad).
 U takvim slučajevima organizuju se liste sa dva pointera, jedan za kretanje unapred kao kod obične liste,
 i dodatni pointer za kretanje unazad, što je ilustrovano na sledećoj slici.
 
 
5.  
#include <stdio.h>
#include <stdlib.h>
 
typedef struct elem { int broj; struct elem *pret, *sled; } Elem;
typedef struct { Elem *prvi, *posl, *tek; } Lista;
typedef enum {NAPRED, NAZAD} Smer;
 
Lista stvori (void);                    /* Stavaranje prazne liste.       */
void na_prvi (Lista *lst);              /* Pomeranje na prvi element.     */
void na_posl (Lista *lst);              /* Pomeranje na poslednji element.*/
void na_sled (Lista *lst);              /* Pomeranje na sledeci element.  */
void na_pret (Lista *lst);              /* Pomeranje na prethodni element.*/
void nadji_sled (Lista *lst, int b);    /* Pomer. na sled. pojavljivanje. */
void nadji_pret (Lista *lst, int b);    /* Pomer. na pret. pojavljivanje. */
int ima_tekuci (Lista lst);             /* Da li postoji tekuci element?  */
int dohvati (Lista lst);                /* Dohvatanje tekuceg elementa.   */
void promeni (Lista lst, int b);        /* Menjanje tekuceg elementa.     */
void dodaj_poc    (Lista *lst, int b);  /* Dodavanje ispred prvog elemanta*/
void dodaj_kraj   (Lista *lst, int b);  /* Dodavanje iza poslednjeg elem. */
void dodaj_ispred (Lista *lst, int b);  /* Dodavanje ispred tekuceg elem. */
void dodaj_iza    (Lista *lst, int b);  /* Dodavanje iza tekuceg elementa.*/
void izbaci (Lista *lst, Smer smer);    /* Izbacivanje tekuceg elementa.  */
void brisi (Lista *lst);                /* Brisanje svih elemenata.       */
void pisi (Lista lst, Smer smer);       /* Ispisivanje liste.             */
void citaj (Lista *lst, int n, Smer smer); /* Citanje liste.              */
 
void main () {
  Lista lst = stvori (); int n, k;
  while (1) {
    printf ("n?        "); scanf ("%d", &n);
  if (n <0) break;
    printf ("Lista?    "); citaj (&lst, n, NAPRED);
    if (n == 0) putchar ('\n');
    printf ("Izostavljate?    "); scanf ("%d", &k);
    printf ("Napred=   "); pisi (lst, NAPRED); putchar ('\n');
    printf ("Nazad=    "); pisi (lst, NAZAD);  putchar ('\n');
 
    /* Izbacivanje svakog pojavljivanja datog broja: */
    na_prvi (&lst); nadji_sled (&lst, k);
    while (ima_tekuci(lst)) { izbaci (&lst, NAPRED); nadji_sled (&lst ,k); }
    printf ("Skraceno= "); pisi (lst, NAPRED); printf ("\n\n");
  }
}
 
Lista stvori (void)                      /* Stvaranje prazne liste.       */
  { Lista lst; lst.prvi = lst.posl = lst.tek = NULL; return lst; }
 
void na_prvi (Lista *lst)               /* Pomeranje na prvi element.     */
  { lst->tek = lst->prvi; }
 
void na_posl (Lista *lst)               /* Pomeranje na poslednji element.*/
  { lst->tek = lst->posl; }
 
void na_sled (Lista *lst)               /* Pomeranje na sledeci element.  */
  { if (lst->tek) lst->tek = lst->tek->sled; }
 
void na_pret (Lista *lst)               /* Pomeranje na prethodni element.*/
  { if (lst->tek) lst->tek = lst->tek->pret; }
 
void nadji_sled (Lista *lst, int b)     /* Pomer. na sled. pojavljivanje. */
  { while (lst->tek && lst->tek->broj != b) lst->tek = lst->tek->sled; }
 
void nadji_pret (Lista *lst, int b)     /* Pomer. na pret. pojavljivanje. */
  { while (lst->tek && lst->tek->broj != b) lst->tek = lst->tek->pret; }
 
int ima_tekuci (Lista lst)              /* Da li postoji tekuci element?  */
  { return lst.tek != NULL; }
 
int dohvati (Lista lst) {               /* Dohvatanje tekuceg elementa.   */
  if (! lst.tek) exit (1);
  return lst.tek->broj;
}
 
void promeni (Lista lst, int b) {       /* Menjanje tekuceg elementa.     */
  if (! lst.tek) exit (1);
  lst.tek->broj = b;
}
 
void dodaj_poc    (Lista *lst, int b) { /* Dodaj b ispred prvog elemanta*/
  Elem *novi = malloc (sizeof(Elem));
  novi->broj = b; novi->sled = lst->prvi; novi->pret = NULL;
  if (! lst->prvi) lst->posl = novi; else lst->prvi->pret = novi;
  lst->prvi = lst->tek = novi;
}  //T(n)=O(1), gde je n duzina liste
 
void dodaj_kraj   (Lista *lst, int b) { /* Dodaj b iza poslednjeg elem. */
  Elem *novi = malloc (sizeof(Elem));
  novi->broj = b; novi->pret = lst->posl; novi->sled = NULL;
  if (! lst->posl) lst->prvi = novi; else lst->posl->sled = novi;
  lst->posl = lst->tek = novi;
}  //T(n)=O(1), gde je n duzina liste
 
void dodaj_ispred (Lista *lst, int b) { /* Dodavanje ispred tekuceg elem. */
  Elem *novi = malloc (sizeof(Elem));
  if (! lst->tek) exit (1);
  novi->broj = b; novi->pret = lst->tek->pret; novi->sled = lst->tek;
  if (! lst->tek->pret) lst->prvi = novi; else lst->tek->pret->sled = novi;
  lst->tek->pret = lst->tek = novi;
}
 
void dodaj_iza    (Lista *lst, int b) { /* Dodavanje iza tekuceg elementa.*/
  Elem *novi = malloc (sizeof(Elem));
  if (! lst->tek) exit (1);
  novi->broj = b; novi->sled = lst->tek->sled; novi->pret = lst->tek;
  if (! lst->tek->sled) lst->posl = novi; else lst->tek->sled->pret = novi;
  lst->tek->sled = lst->tek = novi;
}
 
void izbaci (Lista *lst, Smer smer) {   /* Izbacivanje tekuceg elementa.  */
  Elem *stari = lst->tek;
  if (! lst->tek) exit (1);
  if (! lst->tek->pret) lst->prvi = lst->tek->sled;
    else                lst->tek->pret->sled = lst->tek->sled;
  if (! lst->tek->sled) lst->posl = lst->tek->pret;
    else                lst->tek->sled->pret = lst->tek->pret;
  lst->tek = (smer == NAPRED) ? lst->tek->sled : lst->tek->pret;
  free (stari);
}
 
void brisi (Lista *lst) {               /* Brisanje svih elemenata.       */
  while (lst->prvi) {
    Elem *stari = lst->prvi; lst->prvi = lst->prvi->sled; free (stari);
  }
  lst->posl = lst->tek = NULL;
}
 
void pisi (Lista lst, Smer smer){       /* Ispisivanje liste.             */
  if (smer == NAPRED)
    for (na_prvi (&lst); ima_tekuci (lst); na_sled (&lst))
      printf ("%d ", dohvati (lst));
  else
    for (na_posl (&lst); ima_tekuci (lst); na_pret (&lst))
      printf ("%d ", dohvati (lst));
}
void citaj (Lista *lst, int n, Smer smer) { /* Citanje liste.             */
  int i, b;
  brisi (lst);
  for (i = 0; i<n; i++) {
    scanf ("%d", &b);
    (smer == NAPRED) ? dodaj_kraj (lst, b) : dodaj_poc (lst, b);
  }
}

 

6. Opisati implementaciju steka koristeći jednostruko povezanu listu L.

Operacije PUSH i POP i dalje treba da budu složenosti O(1). /* rad sa  stekom unapred nepoznatog kapaciteta      */

 

RESENJE:

 

IDEJA: Operacija PUSH se implementira dodavanjem novog elementa na pocetak liste.

Operacija POP se implementira brisanjem prvog elementa liste.

 

 
 
#include <stdio.h>
#include <stdlib.h>
 
typedef struct elem { int broj; struct elem *sled; } Elem;
typedef Elem *Stek;
 
Stek stvori (void);                     /* Stvaranje praznog steka.       */
void stavi (Stek *stk, int b);         /* PUSH-Stavljanje broja na stek.  */
int uzmi (Stek *stk);                  /* POP-Uzimanje broja sa steka.    */
int prazan (Stek stk);                  /* Da li je stek prazan?          */
void pisi (Stek stk);                   /* Ispisivanje sadrzaja steka.    */
void prazni (Stek *stk);                /* Praznjenje steka.              */
void unisti (Stek *stk);                /* Unistavanje steka.             */
 
int main () {
  Stek stk = stvori (); int b, izbor, kraj = 0;
  while (! kraj) {
    printf ("\n1. Smestaj podataka na stek\n"
              "2. Skidanje podatka sa steka\n"
              "3. Ispisivanje sadrzaja steka\n"
              "4. Praznjenje steka\n"
              "0. Zavrsetak rada\n\n"
              "Vas izbor? "
            );
    scanf ("%d", &izbor);
    switch (izbor) {
    case 1: /* podatak na stek: */
      printf ("Broj?      "); scanf ("%d", &b); stavi (&stk, b);break;
    case 2: /* podatak sa steka: */
      if (! prazan (stk))  printf ("Broj=      %d\n", uzmi (&stk));
      else printf ("*** Stek je prazan! ***\a\n");      break;
    case 3: /* Ispisivanje sadrzaja steka: */
      printf ("Stek=      "); pisi (stk); putchar ('\n');      break;
    case 4: /* Praznjenje steka: */      prazni (&stk); break;
    case 0: /* Zavrsetak rada: */      kraj = 1; break;
    default: /* Pogresan izbor: */ printf ("*** Neozvoljeni izbor! ***\a\n");    
            break;
    }
  }
  return 0;
}
  
Stek stvori () { return NULL; }         /* Stvaranje praznog steka.       */
 
void stavi (Stek *stk, int b) {         /* Stavljanje broja na stek.      */
  Elem *novi = malloc (sizeof(Elem));
  novi->broj = b; novi->sled = *stk; *stk = novi;
}   //T(n)=O(1)
 
int uzmi (Stek *stk) {                  /* Uzimanje broja sa steka.       */
  Elem *stari; int b;
  if (*stk == NULL) exit (2); //potkoracenje, underflow
  b = (*stk)->broj; stari = *stk; *stk = (*stk)->sled; free (stari);
  return b;
}  //T(n)=O(1)
 
int prazan (Stek stk) { return stk == NULL; } /* Da li je stek prazan?    */
 
 
void pisi  (Stek stk) { Elem *tek;      /* Ispisivanje sadrzaja steka.    */
  for (tek=stk; tek; tek=tek->sled) printf ("%d ", tek->broj);
}
 
void prazni (Stek *stk) {               /* Praznjenje steka.              */
  while (*stk) { Elem *stari=*stk; (*stk)=(*stk)->sled; free(stari); }
}
 
void unisti (Stek *stk) { prazni (stk); } /* Unistavanje steka.           */

 

7. Konstruisati nerekurzivnu proceduru složenosti O(n) koja obrće jednostruko povezanu listu od n elemenata.

Procedura ne treba da koristi više od konstantne dodatne memorije pored one potrebne za smeštanje liste.

Kako bi se implementirala procedura za dvostruko povezane liste?

 

 

8. Neka su elementima pridruženi brojevi iz opsega od 1 do n, pri čemu n nije veliko, pa je na raspolaganju memorija veličine O(n).

Svaki element može se pojaviti najviše jednom. Opisati realizaciju apstraktnog tipa podataka koji podržava sledeće operacije:

(a) umetni(x)

(b) ukloni(y) - uklanja se ma koji (proizvoljan) element iz strukture podataka i dodeljuje promenljivoj y.

Operacije treba da budu složenosti O(1).

 

 

 

2.4 Red – QUEUE

 

Redovima se implementira FIFO (first-in first-out) princip.

Za razliku od stekova, kod redova se dodavanje elemenata i uklanjanje elemenata ne vrši na istom kraju reda.

 

Dve osnovne operacije sa redovima:

–dequeue: brisanje elementa sa početka reda

–enqueue: dodavanje člana na kraj reda

 

 

Primene redova

 

o Printer redovi za čekanje na štampu

o Redovi za raspoređivanje rada procesora (FCFS-first come first served)

o  Telekomunikacioni redovi

 

 

 

9. Realizovati red ograničenog kapaciteta korišćenjem niza.

 

IDEJA:

 

 

#include <stdio.h>

#include <stdlib.h>

 

/*  Deklaracije funkcija za rad sa redovim ogranicenog kapaciteta.          */

 

typedef struct { int *niz, kap, duz, prvi, posl; } Red;  

/* niz=cuva elemente reda, kap=kapacitet reda, duz = dostignuta duzina reda, prvi=pocetak reda, posl=kraj reda*/

 

Red stvori (int k);                     /* Stvaranje praznog reda.        */

void stavi (Red *rd, int b);            /* Stavljanje broja u red.        */

int uzmi (Red *rd);                     /* Uzimanje broja iz reda.        */

int prazan (Red rd);                    /* Da li je red prazan?           */

int pun    (Red rd);                    /* Da li je red pun?              */

void pisi (Red rd);                     /* Ispisivanje sadrzaja reda.     */

void prazni (Red *rd);                  /* Praznjenje reda.               */

void unisti (Red *rd);                  /* Unistavanje reda.              */

 

int main () {

  Red rd = stvori (10); int k, b, izbor, kraj = 0;

  while (! kraj) {

    printf ("\n1. Stavaranje reda\n"

              "2. Stavljanje podatka u red\n"

              "3. Uzimanje podatka iz reda\n"

              "4. Ispisivanje sadrzaja reda\n"

              "5. Praznjenje reda\n"

              "0. Zavrsetak rada\n\n"

              "Vas izbor? "

            );

    scanf ("%d", &izbor);

    switch (izbor) {

    case 1: /* Stvaranje novog reda: */

      printf ("Kapacitet? "); scanf ("%d", &k);

      if (k > 0) { unisti (&rd); rd = stvori (k); }    else printf ("*** Nedozvoljeni kapacitet! ***\a\n");

      break;

    case 2: /* Stavljanje podatka u red: */

      if (! pun (rd)) {        printf ("Broj?      "); scanf ("%d", &b); stavi (&rd, b);      }

         else printf ("*** Red je pun! ***\a\n");

      break;

    case 3: /* Uzimanje broja iz reda: */

      if (! prazan (rd))        printf ("Broj=      %d\n", uzmi (&rd));

      else printf ("*** Red je prazan! ***\a\n");

      break;

    case 4: /* Ispisivanje sadrzaja reda: */      printf ("Red=       "); pisi (rd); putchar ('\n');      break;

    case 5: /* Praznjenje reda: */      prazni (&rd); break;

    case 0: /* Zavrsetak rada: */

      kraj = 1; break;

    default: /* Pogresan izbor: */

      printf ("*** Nedozvoljeni izbor! ***\a\n"); break;

    }

  }

  return 0;

}

 

Red stvori (int k) { Red rd;            /* Stvaranje praznog reda.        */

  rd.niz = malloc (k * sizeof(int)); rd.kap = k;

  rd.duz = rd.posl = rd.prvi = 0;

  return rd;

}

 

void stavi (Red *rd, int b) {           /* Stavljanje broja u red.        */

  if (rd->duz == rd->kap) exit (1);

  rd->niz[rd->posl++] = b; rd->duz++;

  if (rd->posl == rd->kap) rd->posl = 0;

}  //T(n)= O(1), n je broj clanova reda

 

int uzmi (Red *rd) { int b;             /* Uzimanje broja iz reda.        */

  if (rd->duz == 0) exit (2);

  b = rd->niz[rd->prvi++]; rd->duz--;

  if (rd->prvi == rd->kap) rd->prvi = 0;

  return b;

} //T(n)=O(1), n je broj clanova reda

 

 

int prazan (Red rd) { return rd.duz == 0; }      /* Da li je red prazan?  */

 

int pun    (Red rd) { return rd.duz == rd.kap; } /* Da li je red pun?     */

 

void pisi  (Red rd) { int i;                /* Ispisivanje sadrzaja reda. */

  for (i=0; i<rd.duz; printf ("%d ", rd.niz[(rd.prvi + i++) % rd.kap]));

}

 

void prazni (Red *rd) { rd->duz = rd->posl = rd->prvi = 0; } /* Praznjenje*/

 

void unisti (Red *rd) { free (rd->niz); }   /* Unistavanje reda.          */

 

10. Opisati implementaciju reda koristeći jednostruko povezanu listu (za redove neogranicenog kapacieta).  

 

IDEJA:

 

 

 


#include <stdio.h>
#include <stdlib.h>

typedef struct elem
{
    int broj;
    struct elem *sled;
} Elem;
typedef struct
{
    Elem *prvi, *posl;
} Red;

Red stvori (void);                      /* Stvaranje praznog reda.        */
void stavi (Red *rd, int b);            /* Stavljanje broja u red.        */
int uzmi (Red *rd);                     /* Uzimanje broja iz reda.        */
int prazan (Red rd);                    /* Da li je red prazan?           */
void pisi (Red rd);                     /* Ispisivanje sadrzaja reda.     */
void prazni (Red *rd);                  /* Praznjenje reda.               */
void unisti (Red *rd);                  /* Unistavanje reda.              */
int greska(const char *poruka, int kodRezultata); /* Ispis poruke o gresci */


int main ()
{
    Red rd = stvori ();
    int b, izbor, kraj = 0;
    while (! kraj)
    {
        printf ("\n1. Stavljanje podatka u red\n"
                "2. Uzimanje podatka iz reda\n"
                "3. Ispisivanje sadrzaja reda\n"
                "4. Praznjenje reda\n"
                "0. Zavrsetak rada\n\n"
                "Vas izbor? "
               );
        scanf ("%d", &izbor);
        switch (izbor)
        {
        case 1: /* Stavljanje podatka u red: */
            printf ("Broj?      ");
            scanf ("%d", &b);
            stavi (&rd, b);
            break;
        case 2: /* Uzimanje broja iz reda: */
            if (! prazan (rd))        printf ("Broj=      %d\n", uzmi (&rd));
            else greska ("*** Red je prazan! ***\a\n", 1);
            break;
        case 3: /* Ispisivanje sadrzaja reda: */
            printf ("Red=       ");
            pisi (rd);
            putchar ('\n');
            break;
        case 4: /* Praznjenje reda: */
            prazni (&rd);
            break;
        case 0: /* Zavrsetak rada: */
            kraj = 1;
            break;
        default: /* Pogresan izbor: */
            greska ("*** Neozvoljeni izbor! ***\a\n", 1);
            break;
        }
    }
    return 0;
}


int greska(const char *poruka, int kodRezultata)
{
    fprintf(stderr, "%s\n", poruka);
    return kodRezultata;
}

Red stvori()
{
    Red rd;    /* Stvaranje reda.*/
    rd.prvi=rd.posl=NULL;
    return rd;
}

void stavi (Red *rd, int b)              /* Stavljanje broja u red.       */
{
    Elem *novi = malloc (sizeof(Elem));
    if (!novi) greska("Greska u alokacijii\n", 2);
    novi->broj = b;
    novi->sled = NULL;
    if (! rd->posl) rd->prvi = novi;
    else rd->posl->sled = novi;
    rd->posl = novi;
}  //T(n)= O(1), n je broj clanova reda

int uzmi (Red *rd)
{
    Elem *stari;
    int b; /* Uzimanje broja iz reda.       */
    if (! rd->prvi) exit (2);
    b = rd->prvi->broj;
    stari = rd->prvi;
    rd->prvi = rd->prvi->sled;
    free (stari);
    if (! rd->prvi) rd->posl = NULL;
    return b;
} //T(n)= O(1), n je broj clanova reda


int prazan (Red rd)
{
    return rd.prvi == NULL;    /* Da li je red prazan?   */
}

void pisi  (Red rd)
{
    Elem *tek;         /* Ispisivanje sadrzaja reda.    */
    for (tek=rd.prvi; tek; tek=tek->sled)
        printf ("%d ", tek->broj);
}

void prazni (Red *rd)                    /* Praznjenje reda.              */
{
    while (rd->prvi)
    {
        Elem *stari = rd->prvi;
        rd->prvi = rd->prvi->sled;
        free(stari);
    }
}

void unisti (Red *rd)
{
    prazni (rd);    /* Unistavanje reda.             */
}

11. Objasniti kako je moguće implementirati red koristeći dva steka. Analizirati vreme izvršavanja operacija za red.

Oznacimo sa q red koji implementiramo. Oznacimo dva steka koja koristimo sa stack1, stack2.
Postoje 2 rešenja: 

Ideja 1 (Operacija enQueue je kljucna da simulira red i ima vecu vremensku složenost) 
U ovom rešenju, element koji je prvi ušao u red je uvek na vrhu u stack 1, 
tako da operacija deQueue jedino što radi je  pop sa stack1. 
Kad želimo da stavimo element na vrhu u stack1, onda koristimo stack2.

enQueue(q, x)  - DODAJ vrednost x na kraj reda q
  1) Dok stack1 nije prazan, uradi push svih elemenata sa  stack1 na stack2.
  2) Push vrednost x  na stack1 (pod pretpostavkom da radimo sa neogranicenim stekovima).
  3) Push sve elemente nazad na stack1.

deQueue(q) - BRISANJE elementa sa pocetka reda q
  1) Ako stack1 nije prazan, onda greška
  2) Skini element sa  stack1 i vrati ga kao rezultat operacije deQueue(q)
  
Ideja 2 (Operacija deQueue je kljucna da simulira red i ima vecu vremensku složenost) 
U ovom rešenju, u operaciji en-queue, novi element se dodaje na vrh u  stack1. 
U operaciji de-queue, ako stack2 je prazan, onda se svu elementi pomeraju na stack2 i kao rezultat dequeue vraca vrh za  stack2.

enQueue(q,  x)  - DODAJ vrednost x na kraj reda q
  1) Push vrednost x na stack1 (pod pretpostavkom da radimo sa neogranicenim stekovima).

deQueue(q) - BRISANJE elementa sa pocetka reda q
  1) Ako su oba steka prazna, onda greška.
  2) Ako stack2 je prazan
       Dok stack1 nije prazan, uradi push svih elemenata sa  stack1 na stack2.
  3) Uradimo Pop elementa sa vrha stack2 i vratimo ga kao rezultat.
  
Koja ideja je efikasnija?
Ideja 2.
Naime, u ideji 1, u operaciji enQueue svi elementi se premeštaju 2 puta.
ALI, u ideji 2 (u operaciji deQueue) elementi se premeštaju jednom i to samo ako  stack2 je prazan.

Metod 2 - implementacija (C)

#include<stdio.h>
#include<stdlib.h>
 
/* cvor steka */
struct sNode
{
    int data;
    struct sNode *next;
};
 
/* push za stack*/
void push(struct sNode** top_ref, int new_data);
 
/* pop za stack*/
int pop(struct sNode** top_ref);
 
/* queue ima 2 steka */
struct queue
{
    struct sNode *stack1;
    struct sNode *stack2;
};
 
/*  enqueue za queue */
void enQueue(struct queue *q, int x)
{
    push(&q->stack1, x);
}
 
/* dequeue za queue */
int deQueue(struct queue *q)
{
    int x;
    /* Oba steka su prazna, onda greska */
    if(q->stack1 == NULL && q->stack2 == NULL)
    {
        printf("Q - empty");
        exit(0);
    }
 
/* Premestanje elemenata sa stack1 na stack 2 samo ako 
stack2 je prazan */
if(q->stack2 == NULL)
{
    while(q->stack1 != NULL)
    {
        x = pop(&q->stack1);
        push(&q->stack2, x);
         
    }
}
 
x = pop(&q->stack2);
return x;
}
 
/*  push za stack*/
void push(struct sNode** top_ref, int new_data)
{
    /* alokacija cvora reda/steka */
    struct sNode* new_node =
        (struct sNode*) malloc(sizeof(struct sNode));
        if(new_node == NULL)
        {
            printf("Stack overflow \n");
            exit(0);
             
        }
 
new_node->data = new_data;
 new_node->next = (*top_ref);
 (*top_ref) = new_node;
}
 
/* Funkcija pop na steku */
int pop(struct sNode** top_ref)
{
    int res;
    struct sNode *top;
     
    /*Ako je stack prazan, greska */
    if(*top_ref == NULL)
    {
        printf("Stack overflow \n");
        exit(0);
         
    }
    else
    {
        top = *top_ref;
        res = top->data;
        *top_ref = top->next;
        free(top);
        return res;
         
    }
}
 
int main()
{
    /* red sa elementima 10 20 30*/
    struct queue *q = (struct queue*)malloc(sizeof(struct queue));
    q->stack1 = NULL;
    q->stack2 = NULL;
    enQueue(q, 10);
    enQueue(q, 20);
    enQueue(q, 30);
     
    /* Dequeue operacija */
    printf("%d ", deQueue(q));
    printf("%d ", deQueue(q));
    printf("%d ", deQueue(q));
 
   return 0;
}


Metod 2 - implementacija (Java)

 
import java.util.Stack;
 
 public class FIFOstacks
{
    
    static class Queue
    {
        Stack<Integer> stack1 ;
        Stack<Integer> stack2 ;
    }
     
    /* push za stack*/
    static void push(Stack top_ref, int new_data)
    {
        //Push  stack
        top_ref.push(new_data);
    }
     
    /* pop za stek*/
    static int pop(Stack top_ref)
    {
        /*Ako je  stack prazan, onda greska */
        if(top_ref.isEmpty())
        {
            System.out.println("Stack Overflow");
            System.exit(0);    
        }
        //pop  stack
        return top_ref.pop(); 
    }
    //enqueue vrednosti x u red
    static void enQueue(Queue q, int x)
    {
        push(q.stack1, x);
    }
    /* dequeue za red */
    static int deQueue(Queue q)
    {
        int x;
        /* GRESKA */
        if(q.stack1.isEmpty() && q.stack2.isEmpty() )
        {
            System.out.println("Q - empty");
            System.exit(0);
        }
      
        /* premestanje  elemenat sa stack1 na stack 2 samo ako
        stack2 je prazan */
        if(q.stack2.isEmpty())
        {
            while(!q.stack1.isEmpty())
            {
            x = pop(q.stack1);
            push(q.stack2, x);
              
            }
        }
        x = pop(q.stack2);
        return x;
    }
     
 
    public static void main(String args[]) 
    {
        
        Queue q= new Queue();
        q.stack1 = new Stack<>();
        q.stack2 = new Stack<>();
        enQueue(q, 10);
        enQueue(q, 20);
        enQueue(q, 30);
         
        System.out.print(deQueue(q)+" ");
        System.out.print(deQueue(q)+" ");
        System.out.println(deQueue(q)+" ");
    }
}

 

 

 

 

2.5 KRUŽNA LISTA

 

Kružna lista nastaje kada umesto da poslednji član liste ima NULL pointer (NULL pointer je pointer koji ne pokazuje ni na jedan element)

 on sadrži adresu prvog člana.


Time se omogućava cirkularno kretanje kroz listu, kao što se možete uveriti posmatranjem sledeće slike.