Improving time complexity of cheapest travel route algorithm

Below is the code to find the cheapest route for a passenger. stationsUnexplored is a Queue to which stations are added and examined. Once we are done with a station, it is removed from Queue and added to a Set stationsExplored. The purpose of stationsExplored is to avoid queuing of stations more than once. Before adding a station to stationsUnexplored I check if it has been explored earlier i.e !stationsExplored.contains(adjacentStation.getKey(). Or it is already present in the queue i.e !stationsUnexplored.contains(adjacentStation.getKey()). First contains() is on a Set, so it has time complexity of \$\mathcal{O}(1)\$. But second contains() is called on a Queue hence the time complexity is \$\mathcal{O}(N)\$.

Is there a way to get rid of the second check on queue or improve it to \$\mathcal{O}(1)\$?

 Queue<Integer> stationsUnexplored = new ArrayDeque<>();
 Set<Integer> stationsExplored = new HashSet<>();
 stationsUnexplored.add(1);

 while (!stationsUnexplored.isEmpty()) {  
     int currentStation = stationsUnexplored.remove();
     Map<Integer, Integer> stations = stationsNFares.get(currentStation); // returns neighboring stations.
     if (stations != null) {
        Iterator<Map.Entry<Integer, Integer>> stationIterator = stations.entrySet().iterator();
        while (stationIterator.hasNext()) { 
           Map.Entry<Integer, Integer> adjacentStation = stationIterator.next();

           // code for computing cheapest fare for current adjacent station.....

           if (!stationsExplored.contains(adjacentStation.getKey()) && !stationsUnexplored.contains(adjacentStation.getKey())) { //O(N)
              stationsUnexplored.add(adjacentStation.getKey());
           }
        }
     }
     stationsExplored.add(currentStation);
 }