是否有任何有趣的算法同时使用堆栈和队列(deque)ADT？

Question

我们经常使用堆栈或队列在我们的算法,但在那里,我们用一个双向链表实现任何情况下都栈和算法中的队列？例如,在一个阶段,我们将()将6个项目推入堆栈,pop()2个项目,然后从双向链接列表的尾部将其余项目(4)出列().我正在寻找的是那些在这种方法中实现某些东西的模糊,有趣的算法,甚至是陌生的.伪代码,链接和解释会很好.

Answer 1

所述Melkman算法 (用于计算线性时间的简单多边形链的凸包)使用双端队列(又名双端队列)来存储增量船体已处理的顶点.

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.

资料来源:http://softsurfer.com/Archive/algorithm_0203/algorithm_0203.htm

Joe Mitchell:Melkman的凸壳算法(PDF)