Maintaining the product of a queue of semigroup elements I have a queue $Q$ where elements can be popped from the left and added to the right in $O(1)$ time.  The elements are members of a fixed semigroup $S$ with $O(1)$ time multiplication.  Let the current state of the $Q$ be the sequence $(s_1,\ldots,s_n)$.  I am interested in the product

$$\prod Q = s_1 \cdots s_n.$$

Question: Is it possible to maintain this product in amortized constant time as elements are added and removed?
A queue can be represented as two stacks and be maintained in amortized constant time. It's then easy to maintain product of all elements of a stack. 

See Purely Functional Data Structures by Chris Okasaki. (More specifically, figure 3.2 on pp. 18. )



About how to maintain on stacks: 

Suppose the stack is $s_1, s_2,\ldots, s_n$ from bottom to top. For one stack, we need to maintain $s_1 s_2 \ldots s_n$; for the other, we need to maintain $s_n\ldots s_2 s_1$. We only consider the first case. 

Let $p_k=s_1\ldots s_k$, then $p_n$ is the answer we need. 

When pop, simply delete $p_n$ and $s_n$. 

When push, $p_{n+1}=p_n s_{n+1}$.