Array-basierte Implementierungen von Liste (Cursor-Implementierung)

Question

Ich möchte einen Cursor verwenden, um einen Stapel zu bauen, aber ich nicht wirklich verstehen, die ganze Cursor Implementierung

public class cursor { 

    private int header; 
    static cursorNode[ ] cursor; 

    private static final int SPACE_SIZE = 100; 

    static 
    { 
     cursor = new cursorNode[ SPACE_SIZE ]; 
     for(int i = 0; i < SPACE_SIZE; i++) 
      cursor[ i ] = new cursorNode(null, i + 1); 
     cursor[ SPACE_SIZE - 1 ].next = 0; 
    } 
    public static int alloc() 
    { 
     int p = cursor[ 0 ].next; 
     if(p == 0) 
      return 0; 
     cursor[ 0 ].next = cursor[ p ].next; 
     cursor[ p ].next=0; 
     return p; 
    } 

    public static void free(int p) 
    { 

     cursor[ p ].next = cursor[ 0 ].next; 
     cursor[ 0 ].next = p; 
    } 
    public cursor() 
    { 
     header = alloc(); 
     cursor[ header ].next = 0; 
    } 
    public boolean isEmpty() 
    { 
     return cursor[ header ].next == 0; 
    } 
    public void addFirst(int l, Object x){ 
     int temp=alloc(); 
     cursor[temp].element=x; 
     cursor[temp].next=cursor[l].next; 
     cursor[l].next=temp; 
    } 
    public boolean removeFirst(int l){ 
     if(cursor[l].next==0) 
      return false; 
     int p =cursor[l].next; 
     cursor[l].next=cursor[p].next; 
     free(p); 
     return true; 
    } 
    public void print(int l){ 
     int p=cursor[l].next; 
     while(p!=0){ 
      System.out.print(cursor[p].element); 
      p=cursor[p].next; 
     } 
    } 


}. 

public class cursorNode { 
    Object element; 
    int  next; 

     public cursorNode(Object x){ 
      this(x, 0); 
     } 

     public cursorNode(Object x, int n) 
     { 
      element = x; 
      next = n; 
     } 


    } 

Können Sie erklären, was Cursor Implementierung und wie um daraus einen Stack zu erstellen. Ich verstehe, dass push() addFirst() verwenden und pop() removeFirst() verwendet, aber wie top() funktioniert.

Answer 1

Zunächst eine Erläuterung, was der von Ihnen gepostete Code tut. Es ist im Wesentlichen eine Möglichkeit, mehrere Sammlungen von Werten zu verwalten, die in einem Pool fester Größe gespeichert sind. Es ist so konzipiert, dass Elemente aus einer Sammlung entfernt werden und zu einer freien Liste zurückkehren, um wiederverwendet zu werden. Es ist schlecht in vielerlei Hinsicht geschrieben, aber da Sie nicht nach Kommentaren gefragt haben, überspringe ich sie.

Zweitens, wie können Sie diesen Code verwenden, um einen Stapel zu implementieren? Antwort: Sie können nicht. Es gibt keine öffentlichen Methoden zum Abrufen von Werten (erforderlich für eine Peek-Operation), und die removeFirst-Methode gibt eine boolean anstelle des Werts zurück, der entfernt wird. Sie müssen diesen Code ändern, um ihn zum Implementieren eines Stapels zu verwenden.