Should I cite my own research demonstration paper? I am a researcher in the computer science / interactions field. One year ago, I published a demonstration paper at a conference presenting and using quite briefly an algorithm A.

This year, I'm submitting a journal paper to the same conference and my work uses this algorithm. I wonder whether the demo is considered as a real publication and if I should just cite this demo paper or should I re-explain in detail the algorithm (I would then go more into details).

Research demonstrations at a conference is something very specific to my field I guess.
You should always cite your own previous work on a subject just the same as if it were written by someone else. Failure to do so is Self Plagiarism, which is a real thing, oddly enough. 

However, you can also, as you suggest go in to more detail on the algorithm if it will help support the new work. 

The general rule is that when something has been published, using it should have a citation. 

The reason for the rule is that the original paper may include context that a reader in the future may want to see but can't find without the citation.