rydz rydz - 1 year ago 77
Java Question

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

I want to try to solve the "PALINDROME" problem using queue and stack i am using the corresponding methods like

offer()[or add()]/poll()
for inserting and removing the element from stack and queue respectively.But it seems enqueing and dequeing of elements in/from a queue does not work according to FIFO order.

public class Testhis{
Stack<Character> st=new Stack<Character>();
PriorityQueue<Character> qu=new PriorityQueue();
public void pushCharacter(Character c){
public void enqueueCharacter(Character 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();

// 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("char in action="+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;
//Finally, print whether string s is palindrome or not.
System.out.println( "The word, " + input + ", is "
+ ( (!isPalindrome) ? "not a palindrome." : "a palindrome." ) );

Answer Source

This is because you are using PriorityQueue. From the java docs found here https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html : the order in a PriorityQueue is determined by a given comparator. If none is given, the natural ordering will be used. In your case: let c1 and c2 be characters and let's assume c1 < c2, then c1 will be before c2 in the queue, no matter in what order they were inserted. So even if you added c2 first, you will get c1 before c2. So you'd need to use a different kind of queue or a list.

Edit: As @ChiefTwoPencils stated, existing implementations of Queue my be found here: https://docs.oracle.com/javase/tutorial/collections/implementations/queue.html