Stack – die neusten Beiträge

Nachdem der Code int x = 2; in in Java Bytes code kompiliert wurde interpretiert Java (JVM) den Bytecode zu Maschinencode um das heisst auch dass die JVM den Arbeitsspeicher verwaltet und der CPU vorgibt wohin die der Wert 2 adressiert werden müsste (Stack Speicher) Die Cpu lädt also den Wert 2 in den Befelsregister und danach in die arithmethisch logische einheit, danach zum Akkumulator und schlussendlich zum Arbeitsspeicher wo sich auch der Stack speicher befindet. Während dieses Vorganges führt die CPU gleichzeitig das Programm aus.

Ich bin so unsicher da ich gelesen habe dass die JVM den Arbeitsspeicher verwaltet und nicht die CPU was ja logisch ist aber ich bin mir beim Vorgang unsicher

Also, ein Stack funktioniert nach dem Last-In-First-Out (LIFO)-Prinzip, während eine Queue nach dem First-In-First-Out (FIFO)-Prinzip arbeitet...

Mir ist aufgefallen, dass man einen Stack auch ohne LinkedList implementieren kann. Eine LinkedList wäre nicht unbedingt notwendig, da wir ja nur auf das oberste Element des Stacks zugreifen müssen, oder? Wäre das dann laufzeitlich möglicherweise effizienter ein Array zu benutzten?

Aber für eine Queue dann eher doch LinkedList, da wir sowohl auf das erste als auch auf das letzte Element der Warteschlange zugreifen müssen? Aber ich könnte eine Queue auch ohne LinkedList implementieren, oder? Wovon genau hängt diese Wahl ob mit oder ohne LinkedList genau ab? Ich bin etwas verwirrt.

Und bei einer Dequeue lieber mit LinkedList?

Ich versuche, rücksprungorientierte Programmierung (ROP) zu lernen.

Und zwar habe ich ein Programm mit einem Pufferüberlauf auf dem Stack, und ich möchte das Programm dazu bringen, /bin/sh zu öffnen.

Das geht mit dem execve Syscall, wenn ich die richtigen Instruktionen finden kann, um die Funktionsparameter vorzubereiten. Das ist die Signatur von execve:

int execve(const char *pathname, char *const _Nullable argv[], char *const _Nullable envp[]);

Also muss ich die folgenden Register setzen:

• rax = 0x3b (Syscallnummer von execve)
• rdi = "/bin/sh" Pointer
• rsi = NULL
• rdx = NULL

Die folgenden Instruktionen habe ich bereits gefunden:

pop rax ; ret
pop rdi ; ret
pop rsi ; ret
pop rdx ; ret
syscall

Ich kann also die Instruktionen und Registerwerte mit dem Pufferüberlauf auf den Stack schreiben und so meine Register füllen. Das Problem ist aber, dass ich einen "/bin/sh" Pointer in rdi brauche (also nicht "/bin/sh" im Register, sondern eine Speicheradresse, an der "/bin/sh" steht).

Ich kann natürlich "/bin/sh" in den Puffer auf dem Stack schreiben, aber leider ist die Speicheradresse jedes Mal anders und ich kenne sie vorher nicht.

Ich weiß, dass "/bin/sh" in libc vorkommt, aber auch dort ist die Speicheradresse jedes Mal anders und ich kenne sie vorher nicht.

Wie komme ich also an einen "/bin/sh" Pointer? Gibt es Tricks oder bestimmte Instruktionen, nach denen ich mich umsehen sollte?

Wozu braucht man beim Programmieren Stapel? Es gibt doch Schlangen, die fast genauso funktionieren. Die Stapel sind also doch überflüssig! Wenn man das letzte ding wegnehmen will nimmt man halt nicht Schlangen sondern Listen.

Kann mir jemand die Unterschiede und Gemeinsamkeiten von Arrays, Queues und Stacks erklären? Die Sachen sind mir schon grob bewusst(bspw. LIFO & FIFO Prinzip, dynamischer Speicher), aber meiner Lehrerin reicht das nicht unn ich würde diese Punkte gerne in meiner Klausur richtig wiedergeben können.

Wäre dies so korrekt per littleEndian?
Schwarzen esp igonieren?

Was ich nicht verstanden habe ist, wie der Stack nach unten wächst. Wenn wir z.B. Push EDX oder Unterprogramm Call schreiben, stehen diese immer in die oberste Stackelemente und wächsen infolgedessen nach oben !!!

Und zu welchem Zweck wird welche dieser Semantiken verwendet?

lg Kath

ich drück die ganze Zeit die shift Taste da da muss man jedes einzele Stack einzel anklicken, gibt es da keine kompi wo ich einmal da klick und da und dann ist mein ganzes Inventar in der Truhe?

Oder das man einen geissen Bereich setzt und der Bereich geht in die Truhe

Hallo,

ich soll die umgekehrte polnische Notation / Postfix-Notation in Java mit Hilfe eines Stacks programmieren. Dafür stehen mir nur folgende Informationen zur Verfügung:

public class IntegerStack {
  public boolean emptystack();
  public int head();
  public void push(int i);
  public int pop();
}

Leider zeigt ein Testfall als Fehler Folgendes an:

IntegerStack s = new IntegerStack();
String[] input = {"1", "2", "*", "3", "4", "*", "+"};
Calculator(input, s);
System.out.println(s.compareHistory(new String[] {
  "[1]",
  "[1, 2]",
  "[1]",
  "[]",
  "[2]",
  "[2, 3]",
  "[2, 3, 4]",
  "[2, 3]",
  "[2]",
  "[2, 12]",
  "[2]",
  "[]",
  "[14]",
  "[]" }
));

// erwartet:
true
// erhalten:
wrong history length: target 14 - is 0
false

Ich kann diesen Fehler nicht deuten. Kann mir bitte jemand sagen, was da falsch sein soll? Ich weiß nicht, was ich beheben soll.

Anbei mein Code:

public int Calculator(String[] input, IntegerStack s) {
  s = new IntegerStack();

  for (int i = 0; i < input.length; i++) {
    switch(input[i]) {
      case "+":
        int x = s.pop();
        int y = s.pop();

      
          s.push(y + x);
        
        break;
      case "-":
        x = s.pop();
        y = s.pop();

       
          s.push(y - x);
        
        break;
      case "/":
        x = s.pop();
        y = s.pop();

      
          s.push(y / x);
       
        break;
      case "*":
        x = s.pop();
        y = s.pop();

        
          s.push(y * x);
        
        break;
      case " ":
        break;
      default:
        if (input[i] != null) {
          s.push(Integer.parseInt(input[i]));
        }
        else {
        }
        ;
      }
    }

    int z = s.pop();
    return z;
  }

Guten Abend,

ich bräuchte mal kurz Hilfe bei folgenden Aufgaben, bitte. Es geht mir darum, dass ich einfach nicht versteh', was zu tun ist. Wir hatten in der Vorlesung den Quicksort-Algorithmus. Ich weiß, dass bei Quicksort das zu sortierende Array in immer kleiner Teilarrays eingeteilt wird, wobei das größere Array zuerst auf den Stack gelegt wird. Das Pivotelement ist entweder das linke oder das rechte und man setzt dann links und rechts einen Pointer am entsprechenden Teilarray. Ist das erste Element des zu sortierenden Teilarrays, welches größer als das Pivotelement ist, gefunden, und es findet sich vom rechten Pointer aus das erste Element, welches kleiner als das Pivotelement ist, so werden diese vertauscht. Bei Überkreuzungen tausche jenes Element auf dass der linke Pointer zeigt mit dem Pivotelement. So hatten wir's zumindest in der Vorlesung (Partitionswahl). Zu den Aufgaben

Aufgabe 1

Ein wichtiger Faktor für die Laufzeit von Quicksort und Quickselect (das Auswahlverfahren des k-kleinsten Elements analog zu Quicksort) ist die Wahl des Pivotelements. Das Pivotelement sollte die zu sortierende Folge in zwei möglichst gleich große Teilfolgen aufspalten.Gegeben sei eine unsortierte Folge mit n paarweise verschiedenen Elementen. Weiterhin sei r(x) die Position des Elements x in der sortierten Folge. Eine mögliche Strategie für die Pivotwahl ist:Wähle uniform zufällig 7 Elemente aus der Eingabefolge und gib das viertkleinste als Pivotelement aus. Dabei können Elemente in der Auswahl mehrmals vorkommen (Ziehen mit Zurücklegen)

.a) Berechne die Wahrscheinlichkeit für das Ereignis: n/4 < r(Pivot) ≤ 3n/4.

b) Nach wie vielen unabhängigen Wiederholungen der Pivotwahl ist zu erwarten, dass der Rang des Pivotelements das erste Mal außerhalb des Intervalls aus Aufgabenteil a) liegt? Hinweis: Du darfst annehmen, dass n= 4·kfür ein k∈N.

Aufgabe 2

Konstruiere eine Folge der Länge7, so dass Quickselect bei Verwendung der Pivotfunktionpivot(links, rechts) =⌈(links+rechts)/2⌉ auf der Suche nach dem viertgrößten Schlüssel die Problemgröße stets nur um 1verringert. Der Algorithmus soll insgesamt also sieben Schritte benötigen, bis er terminiert. Wende Quickselect auf Ihre Folge an, um die Korrektheit zu zeigen

Ansatz Ich verstehe hier nicht, wie n/4 gemeint ist. Wir hatten in der Vorlesung immer das Pivotelement ganz links oder ganz rechts. Jetzt steht hier "Pivot(links,rechts) = [(links+rechts)/2]. Greift man sich also da Element in der Mitte? Das ist bei einer Folge der Länge 7 doch nicht möglich, oder? WIe gehe ich allgemein vor um eine solche Folge zu finden.

LG

Jensek81

Hallo c:,

schreibe morgen in Informatik eine Klausur und für diese müssen wir die Vor und Nachteile eines Stacks kennen. Vielleicht kennt ihr ja welche von denen ich noch nichts weiß c:
LG Kevin

Ich möchte mir eine 4x12 box kaufen, habe schon eine 2x12 box und wollte fragen ob die 4x12 lauter als die 2x12 ist oder ob die einfach wuchtiger klingt als die 2x12.

Ich hör immer irgendwas auf LEague of LEgends von stacks und das man sie bekommen kann durch kills, aber auch durch jungle monster. Was sind stacks und was bringen sie? Danke schonmal im Vorraus :D!

Guten Tag habe da ein Problem bei einem Programm an dem ich gerade arbeite: Ich soll mit Kommandos (list, pop, push und exit) einen Stack mit zeichen füllen, das letzte zeichen löschen, eine Liste des Stacks ausgeben oder das Programm verlassen. Momentan funktioniert nur das verleassen des Programms, da der Scanf-befehl hinter der if-Anweisung nach dem Kompilieren nicht ausgeführt wird, um ein Zeichen einzulesen. (fgetc() hat auch nicht funktioniert).

Vielleicht kann mir ja jemand erklären woran es liegt.

Quelltext:

int main(){ //Anfang Main

//Variablendeklaration char eingabe[6]; char stack[NSTACK]; char item; char z; //zwischenspeicher für zeichen int sp=0; //Ende Variablendeklaration

printf("\nStack auffüllen (bis 15 Zeichen)\n");
printf("Liste der Befehle:\n\n");
printf("list = Liste des Stacks anzeigen\n");
printf("push = Zeichen auf den Stack legen\n");
printf("pop = Zeichen vom Stapel nehmen\n");
printf("exit = Programm beenden\n\n");

 while(eingabe){    //Eingabeschleife

  printf("\nBitte geben Sie ihren Befehl ein: ");
  scanf("%s", &eingabe);
  printf("eingegebener Befehl: %s\n", eingabe);

  
  if (strcmp(eingabe,"exit") == 0){             //exit
printf("\n!!Das Programm wird beendet!!\n");
exit(1);
  } //ende exit
  
  else if (strcmp(eingabe,"push") == 0){            //push
scanf("%c", &z);
printf("Zeichen wird auf Stack gelegt\n");
  } //ende push
  else if (strcmp(eingabe,"pop") == 0){         //pop
printf("Das obertste Zeichen wird entfernt\n");
  } //ende pop
  else if (strcmp(eingabe,"list") == 0){            //liste ausgeben
printf("Die Liste des Stacks wird ausgegeben\n");
printf("%s\n", &stack);
  } //ende list
  
 }  //Ende eingabeschleife
 


printf("\ntest");

printf("\n\n"); return 0; } //Ende Main

Hi ich wollte fragen wie ich bei Minecraft einen Stack aus meinem Inventar schmeisse (bei mac)

danke