School Seminars and Colloquia

Stacks, Queues, Deques and their Representation as Graphs

Discrete Structures and Algorithms (Seminar)

by Prof. Franz Brandenburg


Institution: University of Passau, Germany
Date: Wed 25th January 2012
Time: 10:00 AM
Location: Room 215, Richard Berry Building

Abstract: Stacks and queues are fundamental data structures. They express the LIFO (last-in, first out) and FIFO (first-in, first-out) principles and are the basis for depth first and breadth first search. Stacks and queues are a specialization of a deque, which allows the insertion and removal of objects on its left and right ends. In Java 6 the class Arraydeque implements a deque and is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue. We consider classes of graphs which represent the input-ouput behaviour of these data structures, and call them stack, queue, or deque graphs. Then the input-output actions on a stack are correct if and only if the stack graph is planer. Accordingly, queue graphs have a planar representation on a cylinder and the deque graphs are characterized by planar graphs on the cylinder with additional arches. Hence, we can state: correct if and only if planar. We study properties of the classes of stack, queue and deque graphs, which are subclasses of planar graphs. By Yannakakis result every planar graphs can be represented by four stacks. In particular, one stack graphs are two queue graphs, and one queue graphs are two stack graphs. Our latest result states that in terms of graphs a deque dominates two stacks exactly by the difference between a Hamilton cycle and a Hamilton path in planar graphs. We close with challenging open problems that are related to stacks and queues.