排序副本（JAVA）

Question

我需要幫助搞清楚的算法對於這個問題（在Java編碼）：

寫一個發生在升序整數堆棧，並採取所有重複的整數的方法和把它們放在堆棧的後面，同時保持升序。例如： {1,2,2,2,2,4,5,5,7,7,7,8}變爲{1,2,4,5,7,8,2,2， 2，5，5，7，7} 注意： 你不能使用迭代器或每個循環。您只能使用push（），pop（），isEmpty（）和size（）。您還必須僅使用一個臨時堆棧來解決問題。

這不是作業或任何東西。它正在進行測試，我無法弄清楚。

Answer 1

雖然這是非常低效的，並且可能無法正確處理邊緣情況，但這可以解決您的測試數據，並且應該是一個很好的起點。

我建議通過它逐步調試，以瞭解它是如何工作的。

public void solve(final Stack<Integer> stack) { 

    // any stack with 2 or less items will already be in the solved order by definition 
    if(stack.size() <= 2) { 
     return; 
    } 

    Stack<Integer> tempStack = new Stack<Integer>(); 

    boolean isInCorrectOrder = false; 
    do { 

     // first, reverse the order 
     while(!stack.isEmpty()) { 
      tempStack.push(stack.pop()); 
     } 

     // now pop the first item 
     int currentItem = tempStack.pop(); 
     stack.push(currentItem); 

     boolean foundDuplicate = false; 
     // while the temp stack still has items 
     while(!tempStack.isEmpty()) { 
      // pop the next item 
      int nextItem = tempStack.pop(); 

      // if the next item is the same then put it at the end of the stack after all the other elements 
      if(nextItem == currentItem) { 
       foundDuplicate = true; 
       while(!tempStack.isEmpty()) { 
        stack.push(tempStack.pop()); 
       } 
       stack.push(nextItem); 
      } else if(nextItem < currentItem) { // else if the next item is lower then we have reached the end of the main set of items 
       stack.push(nextItem); 
       while(!tempStack.isEmpty()) { 
        stack.push(tempStack.pop()); 
       } 
       isInCorrectOrder = true; 
      } else { // elsejust push this item and pop the next one 
       stack.push(nextItem); 
       currentItem = nextItem; 
      } 
     } 
     // if we did not find a duplicate, then the stack is in the correct order 
     if(!foundDuplicate) { 
      isInCorrectOrder = true; 
     } 

    } while(!isInCorrectOrder); 
}