There is only one CG with any services in Yellowstone and that's Fishing Bridge. I doubt that you will find it easy to get last minute reservations there. But you could always check for cancellations if you stop at the office.
Yellowstone is big, we have been there a number of times. The last time for 8 days and we just got to visit every major part of the park. You could spent a month there and still have plenty to do. It would probably take 6 to 8 hours to drive all the way across-west to east. Mainly because of the traffic and rubbernecker blockades.
