Java 队列 add()/offer() 和 poll() 方法未按预期按照 FIFO 工作

Question

我想尝试使用队列和堆栈解决 "PALINDROME" 问题我正在使用相应的方法，如 push/pop 和 offer()[or add()]/poll() 从堆栈和队列中插入和删除元素respectively.But 似乎元素的入队和出队 in/from 队列不按照 FIFO 顺序工作。

  public class Testhis{
      Stack<Character> st=new Stack<Character>();
      PriorityQueue<Character> qu=new PriorityQueue();
      public void pushCharacter(Character c){
       st.push(c);
      }
     public void enqueueCharacter(Character c){
        qu.offer(c);
     }
    public  char popCharacter(){
       return st.pop();
    }
    public  char dequeueCharacter(){

        return qu.poll();
    }

   public static void main(String[] args) {
         Scanner scan = new Scanner(System.in);
         String input = scan.nextLine();
         scan.close();

        // Convert input String to an array of characters:
        char[] s = input.toCharArray();

        // Create a Solution object:
        Testhis p = new Testhis();

        // Enqueue/Push all chars to their respective data structures:
       for (char c : s) {
           System.out.println();
           System.out.println("char in action="+c);
           System.out.println();
           p.pushCharacter(c);
           p.enqueueCharacter(c);

        }



   // Pop/Dequeue the chars at the head of both data structures and     
   compare them:

    boolean isPalindrome = true;
    for (int i = 0; i < s.length/2; i++) {
        if (p.popCharacter() != p.dequeueCharacter()) {
            isPalindrome = false;                
            break;
        }
    }
         //Finally, print whether string s is palindrome or not.
         System.out.println( "The word, " + input + ", is " 
                       + ( (!isPalindrome) ? "not a palindrome." : "a   palindrome." ) );
    }
 }

Answer 1

"Queues typically, but do not necessarily, order elements in a FIFO (first-in-first-out) manner. Among the exceptions are priority queues..."。您可能应该使用标准 Queue 而不是 PriorityQueue.

Answer 2

这是因为您正在使用 PriorityQueue。从此处 https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html 找到的 java 文档：PriorityQueue 中的顺序由给定的比较器确定。如果给出 none，将使用自然顺序。在你的情况下：让 c1 和 c2 是字符，让我们假设 c1 < c2，那么 c1 将在队列中的 c2 之前，无论顺序如何他们被插入了。所以即使你先加了c2，你也会在c2之前得到c1。所以你需要使用不同类型的队列或列表。

编辑： 正如@ChiefTwoPencils 所述，Queue 的现有实现可以在这里找到：https://docs.oracle.com/javase/tutorial/collections/implementations/queue.html

Java 队列 add()/offer() 和 poll() 方法未按预期按照 FIFO 工作

Java Queue add()/offer() and poll() method not working according to FIFO as expected

java

queue

stack

palindrome

data-structures