It shouldn't be possible to delete it, as QueenNewt implied, though you can disable it. This issue arises a lot, but it should be there somewhere.
Have a look in General - Applications Manager - All or Running or Disabled / Turned off.
If you have any app folders/trays in the app drawer / list I think it was in the Google apps folder originally.
Just download the play store apk file. Do a Google search for play store apk file, which is the installation file for the play store; get the file and put it anywhere on your device. Now run the file and you will have the play store on your phone once again.
Look at application Manager, look for turned off applications, - This you can get it after sliding the all applications tab
You will find play store there, Turn on Again