The gdb package is available from the Amazon Linux AMI repositories. The repositories should be configured by default. In your case I suspect that you instance cannot contact the repositories so it cannot download the package. To see what repositories you have enabled run:
sudo yum repolist
This should return something like:
Loaded plugins: priorities, update-motd, upgrade-helper repo id repo name status amzn-main/latest amzn-main-Base 5,017+2 amzn-updates/latest amzn-updates-Base 111 repolist: 5,136
If you don't have these repos listed, then make sure you instance can get to the repository (usually allow access to the internet). Also, make sure you haven't made any changes to the files in the /etc/yum.repos.d/ directory.
The pstack command is included in the gdb package, so a seperate package for pstack is not needed.
-Heath