Stack layouts and queue layouts of undirected graphs have been used to model problems in fault-tolerant computing and in parallel process scheduling. However, problems in parallel process scheduling are more accurately modeled by stack and queue layouts of directed acyclic graphs (dags). A stack layout of a dag is similar to a stack layout of an undirected graph, with the additional requirement that the nodes of the dag be in some topological order. A queue layout is defined in an analogous manner. The stacknumber ( queuenumber) of a dag is the smallest number of stacks (queues) required for its stack layout (queue layout). In this paper, bounds are established on the stacknumber and queuenumber of two classes of dags: tree dags and unicyclic dags. In particular, any tree dag can be laid out in 1 stack and in at most 2 queues; and any unicyclic dag can be laid out in at most 2 stacks and in at most 2 queues. Forbidden subgraph characterizations of 1-queue tree dags and 1-queue cycle dags are also presented. Part II of this paper presents algorithmic results---in particular, linear time algorithms for recognizing 1-stack dags and 1-queue dags and proof of NP-completeness for the problem of recognizing a 4-queue dag and the problem of recognizing a 9-stack dag.

In this paper we extend the notion of a ranking of elements in a weak order to a ranking of elements in general ordered sets. The weakness of an ordered set P = (X,\prec) (denoted wk(P)) is the minimum integer k for which there exists an integer-valued function lev: X \to Z satisfying: (i) if x \prec y, then lev(x) < lev(y); and (ii) if x || y, then |lev(x) - lev(y)| \le k (where "||" denotes incomparability). A forcing cycleL in P is a sequence of elements L: x=v 0 , v 1 , . . ., v m = x of P so that for each i \in {0,1, . . ., m-1} either v i \prec v i +1 or v i || v i +1. Our main result relates these two concepts; we prove wk(P) = max L \llceil\frac{up(L)}{side(L)}\rrceil$, where up(L) = #{i : v i \prec v i +1}, side(L) = #{i : v i || v i +1} and the maximum is taken over all forcing cycles L in P. We also discuss algorithms for computing wk(P) and prove that wk(P) is a comparability invariant.