Index: /trunk/src/org/openstreetmap/josm/actions/CombineWayAction.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/actions/CombineWayAction.java	(revision 8855)
+++ /trunk/src/org/openstreetmap/josm/actions/CombineWayAction.java	(revision 8856)
@@ -8,9 +8,7 @@
 import java.awt.event.ActionEvent;
 import java.awt.event.KeyEvent;
-import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
-import java.util.Deque;
 import java.util.LinkedHashMap;
 import java.util.LinkedHashSet;
@@ -19,4 +17,5 @@
 import java.util.Map;
 import java.util.Set;
+import java.util.Stack;
 
 import javax.swing.JOptionPane;
@@ -569,9 +568,9 @@
         }
 
-        protected boolean isSpanningWay(Deque<NodePair> way) {
+        protected boolean isSpanningWay(Stack<NodePair> way) {
             return numUndirectedEges == way.size();
         }
 
-        protected List<Node> buildPathFromNodePairs(Deque<NodePair> path) {
+        protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
             List<Node> ret = new LinkedList<>();
             for (NodePair pair: path) {
@@ -593,6 +592,6 @@
             if (startNode == null)
                 return null;
-            Deque<NodePair> path = new ArrayDeque<>();
-            Deque<NodePair> nextPairs  = new ArrayDeque<>();
+            Stack<NodePair> path = new Stack<>();
+            Stack<NodePair> nextPairs  = new Stack<>();
             nextPairs.addAll(getOutboundPairs(startNode));
             while (!nextPairs.isEmpty()) {
Index: /trunk/src/org/openstreetmap/josm/actions/UploadSelectionAction.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/actions/UploadSelectionAction.java	(revision 8855)
+++ /trunk/src/org/openstreetmap/josm/actions/UploadSelectionAction.java	(revision 8856)
@@ -8,9 +8,8 @@
 import java.awt.event.KeyEvent;
 import java.io.IOException;
-import java.util.ArrayDeque;
 import java.util.Collection;
-import java.util.Deque;
 import java.util.HashSet;
 import java.util.Set;
+import java.util.Stack;
 
 import javax.swing.JOptionPane;
@@ -322,5 +321,5 @@
         protected void realRun() throws SAXException, IOException, OsmTransferException {
             try {
-                Deque<OsmPrimitive> toCheck = new ArrayDeque<>();
+                Stack<OsmPrimitive> toCheck = new Stack<>();
                 toCheck.addAll(getPrimitivesToCheckForParents());
                 Set<OsmPrimitive> checked = new HashSet<>();
Index: /trunk/src/org/openstreetmap/josm/actions/upload/CyclicUploadDependencyException.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/actions/upload/CyclicUploadDependencyException.java	(revision 8855)
+++ /trunk/src/org/openstreetmap/josm/actions/upload/CyclicUploadDependencyException.java	(revision 8856)
@@ -4,13 +4,14 @@
 import static org.openstreetmap.josm.tools.I18n.tr;
 
-import java.util.ArrayDeque;
-import java.util.Deque;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Stack;
 
 import org.openstreetmap.josm.data.osm.Relation;
 
 public class CyclicUploadDependencyException extends Exception {
-    private final Deque<Relation> cycle;
+    private final Stack<Relation> cycle;
 
-    public CyclicUploadDependencyException(Deque<Relation> cycle) {
+    public CyclicUploadDependencyException(Stack<Relation> cycle) {
         this.cycle = cycle;
     }
@@ -33,9 +34,9 @@
         sb.append(tr("Cyclic dependency between relations:"))
           .append('[');
-        for (Relation r : cycle) {
-            if (sb.length() > 0) {
+        for (int i = 0; i < cycle.size(); i++) {
+            if (i > 0) {
                 sb.append(',');
             }
-            sb.append(formatRelation(r));
+            sb.append(formatRelation(cycle.get(i)));
         }
         sb.append(']');
@@ -43,6 +44,6 @@
     }
 
-    public Deque<Relation> getCyclicUploadDependency() {
-        return new ArrayDeque<>(cycle);
+    public List<Relation> getCyclicUploadDependency() {
+        return new ArrayList<>(cycle);
     }
 }
Index: /trunk/src/org/openstreetmap/josm/actions/upload/RelationUploadOrderHook.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/actions/upload/RelationUploadOrderHook.java	(revision 8855)
+++ /trunk/src/org/openstreetmap/josm/actions/upload/RelationUploadOrderHook.java	(revision 8856)
@@ -6,6 +6,4 @@
 import java.awt.BorderLayout;
 import java.awt.Dimension;
-import java.util.ArrayList;
-import java.util.Deque;
 import java.util.Iterator;
 import java.util.List;
@@ -69,6 +67,6 @@
      */
     protected void warnCyclicUploadDependency(CyclicUploadDependencyException e) {
-        Deque<Relation> dep = e.getCyclicUploadDependency();
-        Relation last = dep.getLast();
+        List<Relation> dep = e.getCyclicUploadDependency();
+        Relation last = dep.get(dep.size() -1);
         Iterator<Relation> it = dep.iterator();
         while (it.hasNext()) {
@@ -79,5 +77,5 @@
             }
         }
-        JPanel pnl = buildWarningPanel(new ArrayList<>(dep));
+        JPanel pnl = buildWarningPanel(dep);
         ExtendedDialog dialog = new ExtendedDialog(
                 Main.parent,
Index: /trunk/src/org/openstreetmap/josm/data/APIDataSet.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/data/APIDataSet.java	(revision 8855)
+++ /trunk/src/org/openstreetmap/josm/data/APIDataSet.java	(revision 8856)
@@ -2,10 +2,8 @@
 package org.openstreetmap.josm.data;
 
-import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Comparator;
-import java.util.Deque;
 import java.util.HashMap;
 import java.util.HashSet;
@@ -14,4 +12,5 @@
 import java.util.Map;
 import java.util.Set;
+import java.util.Stack;
 
 import org.openstreetmap.josm.actions.upload.CyclicUploadDependencyException;
@@ -310,5 +309,5 @@
         }
 
-        protected void visit(Deque<Relation> path, Relation current) throws CyclicUploadDependencyException {
+        protected void visit(Stack<Relation> path, Relation current) throws CyclicUploadDependencyException {
             if (path.contains(current)) {
                 path.push(current);
@@ -329,5 +328,5 @@
             visited = new HashSet<>();
             uploadOrder = new LinkedList<>();
-            Deque<Relation> path = new ArrayDeque<>();
+            Stack<Relation> path = new Stack<>();
             for (Relation relation: relations) {
                 visit(path, relation);
Index: /trunk/src/org/openstreetmap/josm/gui/NavigatableComponent.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/NavigatableComponent.java	(revision 8855)
+++ /trunk/src/org/openstreetmap/josm/gui/NavigatableComponent.java	(revision 8856)
@@ -11,10 +11,8 @@
 import java.nio.charset.StandardCharsets;
 import java.text.NumberFormat;
-import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Date;
-import java.util.Deque;
 import java.util.HashSet;
 import java.util.LinkedList;
@@ -23,4 +21,5 @@
 import java.util.Map.Entry;
 import java.util.Set;
+import java.util.Stack;
 import java.util.TreeMap;
 import java.util.concurrent.CopyOnWriteArrayList;
@@ -650,6 +649,6 @@
     }
 
-    private Deque<ZoomData> zoomUndoBuffer = new ArrayDeque<>();
-    private Deque<ZoomData> zoomRedoBuffer = new ArrayDeque<>();
+    private Stack<ZoomData> zoomUndoBuffer = new Stack<>();
+    private Stack<ZoomData> zoomRedoBuffer = new Stack<>();
     private Date zoomTimestamp = new Date();
 
Index: /trunk/src/org/openstreetmap/josm/gui/dialogs/FilterDialog.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/dialogs/FilterDialog.java	(revision 8855)
+++ /trunk/src/org/openstreetmap/josm/gui/dialogs/FilterDialog.java	(revision 8856)
@@ -9,12 +9,11 @@
 import java.awt.event.KeyEvent;
 import java.awt.event.MouseEvent;
-import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
-import java.util.Deque;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Set;
+import java.util.Stack;
 
 import javax.swing.AbstractAction;
@@ -292,5 +291,5 @@
         // Filters can use nested parent/child expression so complete tree is necessary
         Set<OsmPrimitive> result = new HashSet<>();
-        Deque<OsmPrimitive> stack = new ArrayDeque<>();
+        Stack<OsmPrimitive> stack = new Stack<>();
         stack.addAll(primitives);
 
Index: /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/ChildRelationBrowser.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/ChildRelationBrowser.java	(revision 8855)
+++ /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/ChildRelationBrowser.java	(revision 8856)
@@ -12,10 +12,9 @@
 import java.io.IOException;
 import java.net.HttpURLConnection;
-import java.util.ArrayDeque;
-import java.util.Deque;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Set;
+import java.util.Stack;
 
 import javax.swing.AbstractAction;
@@ -330,5 +329,5 @@
     class DownloadAllChildrenTask extends DownloadTask {
         private final Relation relation;
-        private final Deque<Relation> relationsToDownload;
+        private final Stack<Relation> relationsToDownload;
         private final Set<Long> downloadedRelationIds;
 
@@ -336,5 +335,5 @@
             super(tr("Download relation members"), parent);
             this.relation = r;
-            relationsToDownload = new ArrayDeque<>();
+            relationsToDownload = new Stack<>();
             downloadedRelationIds = new HashSet<>();
             relationsToDownload.push(this.relation);
Index: /trunk/src/org/openstreetmap/josm/io/GpxReader.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/io/GpxReader.java	(revision 8855)
+++ /trunk/src/org/openstreetmap/josm/io/GpxReader.java	(revision 8856)
@@ -7,12 +7,11 @@
 import java.io.InputStream;
 import java.io.Reader;
-import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Collection;
-import java.util.Deque;
 import java.util.HashMap;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
+import java.util.Stack;
 
 import javax.xml.parsers.ParserConfigurationException;
@@ -65,6 +64,6 @@
         private GpxLink currentLink;
         private Extensions currentExtensions;
-        private Deque<State> states;
-        private final Deque<String> elements = new ArrayDeque<>();
+        private Stack<State> states;
+        private final Stack<String> elements = new Stack<>();
 
         private StringBuilder accumulator = new StringBuilder();
@@ -75,5 +74,5 @@
         public void startDocument() {
             accumulator = new StringBuilder();
-            states = new ArrayDeque<>();
+            states = new Stack<>();
             data = new GpxData();
         }
@@ -477,5 +476,5 @@
         @Override
         public void endDocument() throws SAXException  {
-            if (!states.isEmpty())
+            if (!states.empty())
                 throw new SAXException(tr("Parse error: invalid document structure for GPX document."));
             Extensions metaExt = (Extensions) data.get(META_EXTENSIONS);
Index: /trunk/src/org/openstreetmap/josm/io/imagery/ImageryReader.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/io/imagery/ImageryReader.java	(revision 8855)
+++ /trunk/src/org/openstreetmap/josm/io/imagery/ImageryReader.java	(revision 8856)
@@ -4,12 +4,11 @@
 import java.io.IOException;
 import java.io.InputStream;
-import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Arrays;
-import java.util.Deque;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.Objects;
+import java.util.Stack;
 
 import javax.xml.parsers.ParserConfigurationException;
@@ -73,5 +72,5 @@
         private StringBuilder accumulator = new StringBuilder();
 
-        private Deque<State> states;
+        private Stack<State> states;
 
         private List<ImageryInfo> entries;
@@ -96,5 +95,5 @@
             accumulator = new StringBuilder();
             skipEntry = false;
-            states = new ArrayDeque<>();
+            states = new Stack<>();
             states.push(State.INIT);
             entries = new ArrayList<>();
Index: /trunk/src/org/openstreetmap/josm/tools/XmlObjectParser.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/tools/XmlObjectParser.java	(revision 8855)
+++ /trunk/src/org/openstreetmap/josm/tools/XmlObjectParser.java	(revision 8856)
@@ -10,6 +10,4 @@
 import java.lang.reflect.Method;
 import java.lang.reflect.Modifier;
-import java.util.ArrayDeque;
-import java.util.Deque;
 import java.util.HashMap;
 import java.util.Iterator;
@@ -18,4 +16,5 @@
 import java.util.Locale;
 import java.util.Map;
+import java.util.Stack;
 
 import javax.xml.XMLConstants;
@@ -65,5 +64,5 @@
 
     private class Parser extends DefaultHandler {
-        private Deque<Object> current = new ArrayDeque<>();
+        private Stack<Object> current = new Stack<>();
         private StringBuilder characters = new StringBuilder(64);
 
Index: /trunk/test/data/regress/11957/data.osm
===================================================================
--- /trunk/test/data/regress/11957/data.osm	(revision 8856)
+++ /trunk/test/data/regress/11957/data.osm	(revision 8856)
@@ -0,0 +1,30 @@
+<?xml version='1.0' encoding='UTF-8'?>
+<osm version='0.6' upload='true' generator='JOSM'>
+  <node id='30203000' timestamp='2012-06-04T07:43:48Z' uid='207581' user='Hjart' visible='true' version='4' changeset='11793732' lat='55.510607' lon='8.4295289' />
+  <node id='30203008' timestamp='2010-12-04T12:37:53Z' uid='207581' user='Hjart' visible='true' version='4' changeset='6537026' lat='55.5078651' lon='8.4287936' />
+  <node id='35213705' timestamp='2010-12-04T10:40:06Z' uid='80543' user='findvej' visible='true' version='2' changeset='6535476' lat='55.507892' lon='8.4307184' />
+  <node id='1618968998' timestamp='2012-06-04T07:43:44Z' uid='207581' user='Hjart' visible='true' version='2' changeset='11793732' lat='55.5090061' lon='8.4285087' />
+  <node id='1618968999' timestamp='2012-02-05T14:55:52Z' uid='599792' user='jorgenj' visible='true' version='1' changeset='10594291' lat='55.5097831' lon='8.4284817' />
+  <node id='1618969016' timestamp='2012-02-05T14:55:52Z' uid='599792' user='jorgenj' visible='true' version='1' changeset='10594291' lat='55.5107187' lon='8.4297369' />
+  <node id='1618969019' timestamp='2012-02-05T14:55:52Z' uid='599792' user='jorgenj' visible='true' version='1' changeset='10594291' lat='55.5099168' lon='8.4285353' />
+  <node id='1618969020' timestamp='2012-02-05T14:55:52Z' uid='599792' user='jorgenj' visible='true' version='1' changeset='10594291' lat='55.5100444' lon='8.4286211' />
+  <node id='1618969035' timestamp='2012-06-04T07:43:44Z' uid='207581' user='Hjart' visible='true' version='2' changeset='11793732' lat='55.5078814' lon='8.428584' />
+  <node id='1618969038' timestamp='2012-02-05T14:55:53Z' uid='599792' user='jorgenj' visible='true' version='1' changeset='10594291' lat='55.5079483' lon='8.4284817' />
+  <way id='5116361' timestamp='2012-06-04T07:43:34Z' uid='207581' user='Hjart' visible='true' version='3' changeset='11793732'>
+    <nd ref='35213705' />
+    <nd ref='30203008' />
+    <tag k='highway' v='unclassified' />
+  </way>
+  <way id='148830403' timestamp='2012-06-04T07:43:39Z' uid='207581' user='Hjart' visible='true' version='2' changeset='11793732'>
+    <nd ref='1618969016' />
+    <nd ref='30203000' />
+    <nd ref='1618969020' />
+    <nd ref='1618969019' />
+    <nd ref='1618968999' />
+    <nd ref='1618968998' />
+    <nd ref='1618969038' />
+    <nd ref='1618969035' />
+    <nd ref='30203008' />
+    <tag k='highway' v='unclassified' />
+  </way>
+</osm>
Index: /trunk/test/unit/org/openstreetmap/josm/actions/CombineWayActionTest.java
===================================================================
--- /trunk/test/unit/org/openstreetmap/josm/actions/CombineWayActionTest.java	(revision 8856)
+++ /trunk/test/unit/org/openstreetmap/josm/actions/CombineWayActionTest.java	(revision 8856)
@@ -0,0 +1,57 @@
+// License: GPL. For details, see LICENSE file.
+package org.openstreetmap.josm.actions;
+
+import static org.junit.Assert.assertEquals;
+
+import java.io.FileInputStream;
+import java.io.IOException;
+import java.io.InputStream;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+import org.junit.BeforeClass;
+import org.junit.Test;
+import org.openstreetmap.josm.JOSMFixture;
+import org.openstreetmap.josm.TestUtils;
+import org.openstreetmap.josm.actions.CombineWayAction.NodeGraph;
+import org.openstreetmap.josm.data.osm.DataSet;
+import org.openstreetmap.josm.data.osm.Node;
+import org.openstreetmap.josm.io.IllegalDataException;
+import org.openstreetmap.josm.io.OsmReader;
+
+/**
+ * Unit tests for class CombineWayAction.
+ */
+public class CombineWayActionTest {
+
+    /**
+     * Setup test.
+     */
+    @BeforeClass
+    public static void setUp() {
+        JOSMFixture.createUnitTestFixture().init(false);
+    }
+
+    /**
+     * Non-regression test for bug #11957.
+     * @throws IOException if any I/O error occurs
+     * @throws IllegalDataException if OSM parsing fails
+     */
+    @Test
+    public void testTicket11957() throws IOException, IllegalDataException {
+        try (InputStream is = new FileInputStream(TestUtils.getRegressionDataFile(11957, "data.osm"))) {
+            DataSet ds = OsmReader.parseDataSet(is, null);
+            NodeGraph graph = NodeGraph.createNearlyUndirectedGraphFromNodeWays(ds.getWays());
+            List<Node> path = graph.buildSpanningPath();
+            assertEquals(10, path.size());
+            Set<Long> firstAndLastObtained = new HashSet<>();
+            firstAndLastObtained.add(path.get(0).getId());
+            firstAndLastObtained.add(path.get(path.size()-1).getId());
+            Set<Long> firstAndLastExpected = new HashSet<>();
+            firstAndLastExpected.add(1618969016L);
+            firstAndLastExpected.add(35213705L);
+            assertEquals(firstAndLastExpected, firstAndLastObtained);
+        }
+    }
+}