Data structure for Parking

What data structure to use for finding free parking spot in Parking Lot program? Assume there are million of parkings.
Alternatively,
Suppose We want to design a Car-parking system. where car can be parked in FCFS basis, But there are some Spacial person ,say P1,P2,p3..having a priority of x1<x2<x3. can be access car according to their Priority.
Give the Data-structure to implement this. Derive Algo and Find Complexity.
[Hints- Heap +Queue OR Multilevel Feedback Priority Queue OR Multiple Heap Structure ]
How to ensure that starvation will not occurs ? How will you integrate with previous Data Structure ?
[Hints -Ageing Technique OR use Time Stamp ]