How to implement a priority queue using SQS(Amazon simple queue service)

I don't think there is any way to do this with a single SQS queue. You have no control over delivery of messages and, therefore, no way to impose a priority on messages. If you find a way, I would love to hear about it.

I think you could possibly use two queues (or more generally N queues where N is the number of levels of priority) but even this seems impossible if you don't actually have the message object at the time you determine that it has failed. You would need the message object so that the data could be written to the high-priority queue.

I'm not sure this actually qualifies as an answer 8^)

As far as I know AWS SQS does not provide a native way or doing a priority queue (single queue priority). If you are open to considering other options, RabbitMQ can do this. Client can specify a priority of 0-255 in the message, and the queue will prioritize a higher priority message gets to the customer first.

For more information, please look at https://www.rabbitmq.com/priority.html