GET /q
200 OK
{ 'start': '/q/start', 'end': '/q/end', 'shift': '/q/shift', 'pop': '/q/pop' }
POST /q/end
x
200 OK
Location: /q/some-identifier-for-element-x
The queue now contains [x].
POST /q/start
a
200 OK
Location: /q/some-identifier-for-element-a
The queue now contains [a, x].
POST /q/pop
POST /q/shift
With obvious results. I'm not totally happy with the last 2 operations, another solution might be to GET /q/start or /q/end and DELETE the returned queue element URL. If the delete succeeds, do what you want with the data, otherwise assume that somebody got to it before you and attempt another GET-DELETE.
Neither method handles "client never got the server's response" very well, I'm not sure what a better solution would be.
Totally generic things like this are unusual, you can usually come up with a better set of resources and operations based on your problem domain.
REST is about the operations on the URLs; the URLs themselves should be totally opaque.
Without knowing anything about how the 3 urls you gave are used, what other operations are possible and how they interact with other resources it is impossible to say whether you're doing REST. The third one looks very suspicious, however (the second one too, though less so).
Is there a meaningful difference between:
GET /user/1
GET /search?user=1
GET /?method=search&user=1
Is REST about the URLs you use, or the operations on those URLs, or both?