Quel est le moyen le plus rapide pour rechercher l'élément maximum dans une pile dans Java?

Question

J'ai un problème dans lequel je dois rechercher l'élément maximum dans une pile. J'ai créé ma propre classe de pile et utilisé l'approche suivante:

Node node = top; //created a new node which points to the top of stack 

    int max = node.data; //max contains the value of the top node 

    while(node != null) { 
      if(node.data > max) { 
       max = node.data; 
      } 
      node = node.next; 
    } 

    //Print the value of max. 

Quelqu'un peut-il suggérer un moyen plus efficace de le faire?

Answer 1

maintenir deux pile:

1. se composent de tous les noeuds.
2. Toujours garder le nœud Max en haut de celui-ci, ce qui facilite l'obtention de l'élément max à chaque fois.

Le code va comme ceci:

import java.util.Stack; 

public class StackWithMax extends Stack<Integer> { 

Stack<Integer> s2; 

public StackWithMax() { 
    s2 = new Stack<Integer>();  
} 

public void push(int value){ 
    if (value >= max()) { 
     s2.push(value); 
    } 
    super.push(value); 
} 

public Integer pop() { 
    int value = super.pop(); 
    if (value == max()) { 
     s2.pop();   
    } 
    return value; 
} 

public int max() { 
    if (s2.isEmpty()) { 
     return Integer.MIN_VALUE; 
    } else { 
     return s2.peek(); 
    } 
    } 
} 

Answer 2

Si vous êtes bien avec l'aide d'un espace supplémentaire, nous pouvons faire getMax() O (1) temps. L'idée est d'utiliser une PriorityQueue basée sur un comparateur qui renvoie le maximum de deux éléments. Votre PriorityQueue sera composé d'éléments disposés de manière triée en fonction de votre comparateur. Chaque fois que vous poussez un élément dans votre pile, vous poussez également l'élément maximum correspondant à cet élément dans le PriorityQueue. Prenons un exemple:

Supposons que dans votre pile vous poussez l'élément 3. Alors dans votre priorityQueue pQ, vous offrirez 3. A ce moment, 3 sera l'élément max correspondant à 3 dans la pile.

Permet d'insérer 5 dans la pile S. Offre 5 dans pQ. Puisque 5> 3, l'ordre des éléments dans pQ sera 5 3. Permet de pousser 4 dans S. Offre 4 dans pQ aussi bien. pQ contiendra maintenant des éléments: 5 4 3. Si vous obtenez getMax(), vous obtenez la tête de pQ qui prend O (1) puisque l'élément maximum est toujours au-dessus de pQ.

Dans le cas de S.pop(), vous pouvez supprimer l'élément sauté correspondant de pQ aussi bien en O (1) si vous stockez le pQ sous la forme de LinkedList. Par conséquent, toutes ces opérations prendraient vraiment O (1) temps.

En suivant la même logique, vous pouvez aussi faire popMax() aussi en O (1) temps. Renvoyez simplement la tête de pQ et supprimez le noeud correspondant de Stack, ce qui peut encore être fait en O (1).

Voici comment la structure des deux peut être:

public class Node{ 
    int data; 
    Node next; 
    Node(int data){ 
     this.data = data; 
     next = null; 
    } 
} 

PriorityQueue<Node> pQ = new PriorityQueue<Node>(); 
Stack<Node> S = new Stack<Node>();