Are there any interesting algorithms using both a stack and queue (deque) ADT?

We often use stacks or queues in our algorithms, but are there any cases where we use a doubly linked list to implement both a stack and a queue in the algorithm? For example, at one stage, we pu开发者_运维问答sh() 6 items onto the stack, pop() 2 items, and then dequeue() the rest of the items (4) from the tail of the doubly linked list. What I am looking for are obscure, interesting algorithms that implement something in this method, or even stranger. Pseudocode, links and explanations would be nice.

---

The Melkman algorithm (for computing the convex hull of a simple polygonal chain in linear time) uses a double-ended queue (a.k.a deque) to store an incremental hull for the vertices already processed.

Input: a simple polyline W with n vertices V[i]

    Put first 3 vertices onto deque D so that:
    a) 3rd vertex V[2] is at bottom and top of D
    b) on D they form a counterclockwise (ccw) triangle

    While there are more polyline vertices of W to process
    Get the next vertex V[i]
    {
        Note that:
        a) D is the convex hull of already processed vertices
        b) D[bot] = D[top] = the last vertex added to D

        // Test if V[i] is inside D (as a polygon)
        If V[i] is left of D[bot]D[bot+1] and D[top-1]D[top]
            Skip V[i] and Continue with the next vertex

        // Get the tangent to the bottom
        While V[i] is right of D[bot]D[bot+1]
            Remove D[bot] from the bottom of D
        Insert V[i] at the bottom of D

        // Get the tangent to the top
        While V[i] is right of D[top-1]D[top]
            Pop D[top] from the top of D
        Push V[i] onto the top of D
    }

    Output: D = the ccw convex hull of W.

Source: http://softsurfer.com/Archive/algorithm_0203/algorithm_0203.htm

Joe Mitchell: Melkman’s Convex Hull Algorithm (PDF)

---

This structure is called Deque, that is a queue where elements can be added to or removed from the head or tail. See more at 1.

---

I'm not sure whether this qualifies, but you can use a double-ended priority queue to apply quicksort to a file too large to fit into memory. The idea is that in a regular quicksort, you pick an element as a pivot, then partition the elements into three groups - elements less than the pivot, elements equal to the pivot, and elements greater than the pivot. If you can't fit all of the items into memory at once, you can adapt this solution as follows. Instead of choosing a single element as the pivot, instead pick some huge number of elements (as many as you can fit into RAM, say) and insert them into a double-ended priority queue. Then, scan across the rest of the elements one at a time. If the element is less than the smallest element of the double-ended priority queue, put it into the group of elements smaller than all the pivots. If it's bigger than the largest element of the priority queue, then put it into a group of elements greater than the pivots. Otherwise, insert the element into the double-ended priority queue and then kick out either the smallest or largest element from the queue and put it into the appropriate group. Once you've finished doing this, you'll have split the elements into three pieces - a group of small elements that can then be recursively sorted, a group of elements in the middle that are now fully sorted (since if you dequeue them all from the double-ended priority queue they'll be extracted in sorted order), and a group of elements greater than the middle elements that can be sorted as well.

For more info on this algorithm and double-ended priority queues in general, consider looking into this link to a chapter on the subject.

---

We can modify Breadth First Search (that is usually used to find shortest pathes in a graph with 1-weighted edges) to work with 0-1 graphs (i.e. graph with edges of 0 and 1 weights). We can do it next way: when we used 1-edge we add the vertex to the back and when we use 0-edge we add the vertex to the begin.