スタックの配列の実装を使用して大部分（リーダー）を見つける

Question

ソートされていないスタック内で大多数またはリーダーを探していますが、私のtos（スタック変数の先頭）に問題があります。 。以下はメインコードを含む私のコードです。配列またはスタックの大部分は、配列の半分以上に現れる任意の要素です（arrSize/2）。問題が発生し

public class findLeader { 

static class ArrayStack{ 
    private int[] stackArr; 
    private int tos;//top of stack 

    public ArrayStack(){ 
     stackArr = new int[10]; 
     tos = -1; 
    } 

    public ArrayStack(int size){ 
     stackArr = new int[size]; 
     tos = -1; 
    } 

    public ArrayStack(int[] arr, int tos){ 
     stackArr = arr; 
     this.tos = tos; 
    } 

    public boolean isEmpty(){ 
     return(tos == -1); 
    } 

    public int peek(){ 
     if(isEmpty()){ 
      return -999; 
     } 
     return stackArr[tos]; 
    } 

    public void push(int x){ 
     if(tos == stackArr.length - 1){ 
      return; 
     } 
     stackArr[++tos] = x; 
    } 

    public int pop(){ 
     if(isEmpty()){ 
      return -999; 
     } 
     int popValue = stackArr[tos]; 
     stackArr[tos] = 0; 
     --tos; 
     return popValue; 
    } 

    public void print(){ 
     if(isEmpty()){ 
      return; 
     } 
     for(int i = 0; i <= tos; ++i){ 
      System.out.print(stackArr[i] + " "); 
     } 
     System.out.println(); 
    } 

} 

public static int leader(ArrayStack myStack){ 

    int initSize = myStack.tos + 1; //gets initial size of stack. 
    int leader; //initialize leader or majority. 

    while(!myStack.isEmpty()){ 
     leader = myStack.peek();//set first leader variable to the element at the tos. 
     System.out.println("leader " + leader); //just for debugging 
     System.out.println("tos " + myStack.tos); //debugging 
     //System.out.println(isLeader(myStack, initSize, leader)); //debugging 
     if(isLeader(myStack, initSize, leader)){  
      return 1; 
     } 
     else{ 
      myStack.pop(); 
     } 
     System.out.println("after function tos " + myStack.tos); //debugging   
    } 

    return -1; 
} 

public static boolean isLeader(ArrayStack myStack, int initSize, int leader){ 
    ArrayStack as = myStack; 
    int count = 0; 

    while(!as.isEmpty()){ 
     if(as.peek() == leader){ 
      as.pop(); 
      ++count; 
     } 
     else{ 
      as.pop(); 
     } 
    } 
    //System.out.println(count); 
    if(count > initSize/2) 
     return true; 
    else{ 
     return false; 
    } 
} 

public static void main(String[] args) { 
    int[] arr = {2, 5, 6, 2, 8, 2, 8, 2, 2}; 

    ArrayStack stack = new ArrayStack(); 

    stack.push(5); 
    stack.push(2); 
    stack.push(6); 
    stack.push(2); 
    stack.push(8); 
    stack.push(2); 
    stack.push(2); 
    stack.push(2); 
    stack.push(5); 

    System.out.println(leader(stack)); 

} 

はリーダーであり、かつisLeader方法は、isLeaderの最初の呼び出しの後、TOSはTOS =として返される-1以下の私の出力から示されているよう。

出力：

leader 5 
tos 8 
after function tos -1 
-1 

私の意図はisLeader（へのすべての呼び出しの後で）falseが返された場合、私は上からTOS変数をポップして、新しい小さなスタックでもう一度（）isLeaderを呼び出したいです。

本当にありがとうございました。皆様のお役に立てば幸いです。

あなたは

Answer 1

スタックは何のリーダーを持っていない場合、私は個人的に、スタックのリーダーまたはnullを返すあなたのArrayStackに方法public Integer leader()を追加したい：

public Integer leader() { 
    final Map<Integer, Integer> counts = new HashMap<>(); 
    final int neededLeaderCount = ((tos + 1)/2) + 1; 
    for (int i = 0; i <= tos; ++i) { 
     int currentElementCount = counts.getOrDefault(stackArr[i], 0) + 1; 
     if (currentElementCount >= neededLeaderCount) { 
      return stackArr[i]; 
     } 
     counts.put(stackArr[i], currentElementCount); 
    } 
    return null; 
} 

あなたisLeader機能は、その後に書き換えることができます

public static boolean isLeader(ArrayStack myStack, int leader) { 
    // use Objects.equals as myStack.leader() may be null 
    return Objects.equals(myStack.leader(), leader); 
} 

この方法は、お客様の内部構造を変更したり要求したりすることがないため、はるかにクリーンです。ArrayStackはクラス自体の外部にあります。

Answer 2

私はそれがisLeader関数に渡すこともスタックのcurrSizeを追跡することによって仕事を得ることができましたありがとうございました。誰かがもっと簡単な解決法を持っていて、それを共有したいのであれば、私は物事を複雑にしているように感じます。誰かが興味があれば私のコードは以下の通りです。

public static int leader(ArrayStack myStack){ 
    int currSize = myStack.tos; 
    int initSize = myStack.tos + 1; //gets initial size of stack. 
    int leader; //initialize leader or majority. 

    while(!myStack.isEmpty()){ 
     leader = myStack.peek();//set first leader variable to the element at the tos. 
     System.out.println("leader " + leader); //just for debugging 
     System.out.println("tos " + myStack.tos); //debugging 
     //System.out.println(isLeader(myStack, initSize, leader)); //debugging 
     if(isLeader(myStack, initSize, leader, currSize)){  
      return 1; 
     } 
     else{ 
      --currSize; 
      myStack.pop(); 
     } 
     System.out.println("after function tos " + myStack.tos); //debugging   
    } 

    return -1; 
} 

public static boolean isLeader(ArrayStack myStack, int initSize, int leader, int currSize){ 
    ArrayStack as = myStack; 
    int count = 0; 


    while(as.tos > -1){ 
     if(as.peek() == leader){ 
      --as.tos; //Just move tos pointer down stack rather than popping 
         //to maintain original stack. 
      ++count; 
     } 
     else{ 
      --as.tos; 
     } 
    } 

    if(count > initSize/2) 
     return true; 
    else{ 
     as.tos = currSize;//reset the tos pointer back to the currSize of 
          //stack. 
     return false; 
    } 
}