Skip to main content
3 of 3
edited tags
YCor
  • 63.9k
  • 5
  • 187
  • 286

Notation/definition for the state of a FIFO queue

A first-in first-out queue is filled up by tokens $t \in T$. The state of the queue $q \in Q$ is being changed by two operations, \begin{equation} \mathrm{push} : Q \times T \rightarrow Q \end{equation} which pushes a token to the end of the queue and \begin{equation} \mathrm{pop} : Q \rightarrow Q \times T \end{equation} which pops a token from the beginning of the queue. Let's suppose $T = \lbrace 2, 3, 5, 7, 13\rbrace$ Let's suppose $q = [2, 3, 5]$ is the initial token state and a token being pushed to a queue is $t = 3$. Then \begin{equation} q' = \mathrm{push}(q, t) = [2,3,5,3] \end{equation} Suppose that afterwards a token is being popped from the queue. Then \begin{equation} (q'', t') = \mathrm{pop}(q') \end{equation} where \begin{align} &q'' = [3, 5, 3]\\ &t' = 2 \end{align} I have a problem saying what the set of queue states $Q$ is. It is a set of lists which contain the elements from a set $T$. The closest I get is the abuse of notation of a power set, i.e. $Q = \mathcal{P}(T)$. There exists a power set of a multi-set which allows repetition of elements, but it requires a further disclaimer that $T$ is a "proper" set and only its "power set" is a multi-set. Furthermore, the elements of this power set can be repeated unknown number of times.

Can you, please, help me with notation. If you have a reference to an existing work this would be great, but any suggestions are appreciated.