Basser Seminar Series

Stacks, Queues, Deques and their Representation as Graphs

Speaker: Professor Franz J Brandenburg
University of Passau, Germany

Time: Tuesday 21 February 2012, 2:00-3:00pm
Location: The University of Sydney, School of IT Building, Lecture Theatre (Room 123), Level 1
Add seminar to my diary

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.

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.

Speaker's biography

Franz J Brandenburg reveived his PhD from the University of Bonn in 1978, and his habilitation in 1982. Since 1983 he is a full professor of Informatics at the University of Passau. His research interest is in comptatational complexity, algorihmics, and particularly in graph drawing. One of the earliest graph drawing tool (Graphed) was developed in his group; follow-ups are Graphlet and Gravisto. His ongoing work is on drawing graphs on surfaces, such as cylinders and tori.