Storage I have no idea. (for that matter, I have little idea how we store non-linguistic thoughts)
Communication is primarily via posture, secondarily via sound. No "grammar" is involved, intensification is via intensification of signal, not addition of symbols. (that said, much human-animal communication is by means of arbitrary symbols, just that each symbol is serving as a sign because combinations of symbols and even their ordering doesn't really matter)
Animals certainly get order: they'll easily learn sequences of actions, but if you're getting different behaviour from AB than BA, I currently believe that's because the animal has learnt, and is perceiving, those as two different gestalts.
Imperative and Vocative are the basic cases. (and to what extent the latter belongs to the former I can't really say: when the stock greets in the morning, are they saying "good morning, 0823", as we'd like to believe, or are they really saying "Hey, you, thumb-monkey, feed us!"?)
Interrogative exists, but barely: "where is everyone?" "fren?" (or, if wondering about more* than friendship: "gotta light?")
An example of linear use of order in equines: a young equid has what my wife calls "filly rights" and generally gets to do what it wants. As it gets either older, or too obnoxious, though, the other members of the herd will start to socialise it. This usually occurs via an ascending scale of pressure, from the subtle (eye contact - "are you sure that's an acceptable behaviour?") through the clear (coming up alongside — "all right, what's all this then?") to behaviours reserved for outlaws (full-power kick with both hinds — "what we've got here is failure to communicate").
[the biggest problem I see novice humans have is they attempt to bargain with animals; offer-consideration-acceptance is, for me, far too human-abstract a framework. That's not to say you can't come to consensus on a modus vivendi, but you're not going to get there through a contract approach, calibrated to the capabilities of two-legged mammals.]
My stock all know index finger up is a non-linguistic way humans ask "are you sure?" (and their name may be a linguistic escalation), but I have no clue if they understand it as a sign of potential aggression (being generally produced as a sharp movement), or as a symbol of potential displeasure?
Cattle (both mobs and individuals) can be steered by use of their fight-or-flight in response to posture. You don't directly tell them "go left" ("haw" for a carriage horse) or "go right" ("gee" for a carriage horse) but instead either confirm the pressure (if they're already pointed the right direction) or change the pressure (reduce-intensify if you wish them to flip towards you, intensify-reduce if you wish them to flip away from you) to get them going in the desired direction.
[as you all can tell, feudalism (or IR) is basically what you get when you think politics should be entirely based on this level of communication; however even in democracies use of the bovine principle to manufacture consensus in an electorate occurs, for my sensitivities, way too often]
If anyone can think of experiments that would clarify some of these situations, I'm all ears!
* I understand these days you all mediate all your flirting via text, which seems like a very difficult thing to calibrate; in my day we had analogue signals that (to me alone?) are much easier to dial up or down:
We laugh just a little too loud
Stand just a little too close
We stare just a little too long
WTF are kids doing these days? "we put just a little too many 'e's in our heeeeys?"