So implementieren Sie Java-Stack und -Warteschlange

Stack und Queue

1. Stack (Stack) ist eine Last-In-First-Off-Datenstruktur (LIFO). Stapel (Stack)

Der Stapel ist eine lineare Struktur. Im Vergleich zum Array sind die dem Stapel entsprechenden Operationen eine Teilmenge des Arrays.

2. Es können nur Elemente an einem Ende hinzugefügt und Elemente an einem Ende entfernt werden (dieses Ende wird als oberstes Ende des Stapels bezeichnet).

Stack ist eine Datenstruktur, die häufig in Computern verwendet wird, z. B. als lexikalischer Analysator in Compilern, in virtuellen Java-Maschinen, in Rückgängigmachungsoperationen (Undo) in Browsern. Implementierung von Funktionsaufrufen im Compiler usw.

Implementierung des Stapels

Schnittstelle

Beschreibung

KomplexitätO(1) Amortisiert Gleichmäßig verteilenErläuterung: drücken und Pop-Operationen werden am Ende ausgeführt, es ist möglich, die Größe zu ändern, aber die gleichmäßige Verteilung ist O(1). Welches Problem erklärt O(n)? Die Implementierung des Stapels kann über ein Array oder eine verknüpfte Liste implementiert werden. Hier verwenden wir ein Array, um die obige Schnittstelle zu implementieren.

	void push(E e)	Elemente zum Stapel hinzufügen
	E pop()	Das oberste Element des Stapels platzen lassenO(1)
	E peek()	Das oberste Element des Stapels anzeigenO(1)
int getSize()	Erhalten Sie die Anzahl der Elemente im Stapel	O(1)
boolean isEmpty()	Beurteilen Sie, ob der Stapel leer ist	O(1)
	Wenn Sie mehr über die Zeitkomplexitätsanalyse erfahren möchten, beachten Sie bitte den Artikel, den der Autor später aktualisieren wird:

Beim Design des Stapels achtet der Benutzer nur auf den Zugriff des obersten Elements des Stapels und die Stapellänge, daher lautet der Designcode wie folgt:

Leser können den

Stack

dies verwenden Datenstruktur zur Lösung von Problem Nr. 20 auf LeetCode: Für gültige Klammern siehe auch Tägliche Zählung: Gültige Klammern.

Queue

Queue ist auch eine lineare Datenstruktur. Im Vergleich zu Arrays sind die Operationen, die Warteschlangen entsprechen, eine Teilmenge von Arrays.

Elemente können nur von einem Ende (dem Ende der Warteschlange) hinzugefügt werden und Elemente können nur vom anderen Ende (dem Kopf der Warteschlange) herausgenommen werden. Die Anwendung der Warteschlange kann sich in der Wiedergabeliste des Players, im Datenstromobjekt und in der asynchronen Datenübertragungsstruktur (Datei-E/A, Pipe-Kommunikation, Socket usw.) widerspiegeln. Die intuitivste Methode ist natürlich die Warteschlange.

Implementierung der Warteschlange

Schnittstelle

Beschreibung

KomplexitätO(1) equally geteiltDer Eintritt in die Warteschlange beginnt am Ende der Warteschlange, und eine Größenänderung kann daher ausgelöst werden ist im Durchschnitt O(1). Das Entfernen aus der Warteschlange erfolgt an der Spitze der Warteschlange, und die Array-Implementierung erfordert jedes Mal das Verschieben aller Elemente, O(n).

	void enqueue(E e)	enqueue
	E dequeue( )	Aus der Warteschlange entfernenO(n)
E getFront()	Das erste Element der Warteschlange abrufen	O(1)
int getSize()	Die Anzahl der Warteschlangenelemente abrufen	O( 1)
boolean isEmpty()	Bestimmen Sie, ob die Warteschlange leer ist	O(1)

Das obige ist der detaillierte Inhalt vonSo implementieren Sie Java-Stack und -Warteschlange. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!