Izpitno vprašanje RAČ2PRA 5600

Iz MaFiRaWiki

Vprašanje

Predstavitev dvojnega sklada

Odgovor

Ko se z računalnikom povežemo na internet, bi želeli beležiti izhodne in vhodne podatke. Izberemo si en sklad za izhodne podatke in enega za vhodne podatke. Takšen način za izkoriščanje prostora ni primeren, zato ker ima nekdo več vhodnih podatkov kot izhodnih (ali obratno). Sklad z vhodnimi podatki se lahko napolni, medtem, ko je v skladu z izhodnimi podatki neizkoriščen prostor. Zato naredimo skupen sklad, ki pa bo videti, kot da sta dva. Skupni oz. dvojni (dvobarvni) sklad se torej prilagodi uporabi. Dvobarvni sklad je sestavljen iz črnega in rdečega sklada. Ta sklad pozna barvno kodirane različice metod običajnega sklada (npr. rdečeVstavi in črnoVstavi).

Dvobarvni sklad uporablja eno tabelo velikosti N, za katero vemo, da je vedno večja kot sešteti velikosti rdečega in črnega sklada.

Program

  1. public class DvobarvniSklad extends Object {
  2. private int[] tab;
  3. private int kamR; // kazalec za rdece
  4. private int kamC; // kazalec za crne
  5. private final static int MAX_V = 40; // dolocimo max velikost
  6. public DvobarvniSklad() { // ce ne doloci velikosti jo nastvimo na max_v
  7. this(MAX_V);
  8. }
  9. public DvobarvniSklad (int n) // določimo velikost sklada (tabele)
  10. {
  11. tab = new int[n];
  12. kamR = 0; // stevec za rdeče na zacetek
  13. kamC = n - 1; // stevec za crne na konec
  14. }
  15.  
  16. public void vstaviR(int pod) // vstavljamo »rdec« podatek
  17. {
  18. tab[kamR] = pod;
  19. kamR++; // premaknemo kazalec desno po tabeli
  20. }
  21. public void vstaviC(int pod) // vstavljamo »crne« podatke
  22. {
  23. tab[kamC] = pod;
  24. kamC--; // pomaknemo kazalec levo po tabeli
  25. }
  26. public void odstraniR()
  27. {
  28. if(!prazenR())
  29. kamR--; // premaknemo kazalec
  30. }
  31. public void odstraniC()
  32. {
  33. if(!prazenC())
  34. kamC++; // premaknemo kazalec
  35. }
  36. public boolean prazenR()
  37. {
  38. return (kamR == 0); // vrne na zacetek
  39. }
  40. public boolean prazenC()
  41. {
  42. return (kamC == (tab.length - 1)); // vrne na konec
  43. }
  44. public int vrhR() // vrne rdec vrh
  45. {
  46. if(!prazenR())
  47. {
  48. return tab[kamR - 1];
  49. }
  50. return Integer.MAX_VALUE; // ce je prazen, vrne Integer.MAX_VALUE
  51. }
  52. public int vrhC() // vrne crn vrh
  53. {
  54. if(!prazenC())
  55. {
  56. return tab[kamC + 1];
  57. }
  58. return Integer.MAX_VALUE; // ce je prazen, vrne Integer.MAX_VALUE
  59. }
  60. public void izpisR() // izpise rdeci del tabele
  61. {
  62. System.out.print("Rdeci sklad: " );
  63. for(int i = kamR -1; i >= 0; i--)
  64. System.out.print(tab[i] + " ");
  65. System.out.println();
  66. }
  67. public void izpisC() // izpise crni del tabele
  68. {
  69. System.out.print("Crni sklad: " );
  70. for(int i = kamC + 1; i < tab.length; i++)
  71. System.out.print(tab[i] + " ");
  72. System.out.println();
  73. }
  74. public void izpis() // izpise dvobarvni sklad
  75. {
  76. izpisR(); izpisC();
  77. }
  78. }
Osebna orodja