Currently, IEEE 802.16 or WiMax is becoming increasingly popular throughout the world. The IEEE 802.16 standard defines the specification for Metropolitan Area Networks. However, it does not define the scheduling schemes for different service classes. In this paper, we propose an uplink scheduling scheme called Adaptive Deficit Priority Queue (ADPQ) for IEEE 802.16 networks. ADPQ is based on one QoS parameter called Maximum Latency defined for Real-Time Polling Service (rtPS) in the standard. Our proposed scheme improves the transmission quality of rtPS by decreasing the transmission delay of rtPS packets and enhancing the throughput for rtPS in IEEE 802.16 networks. In addition, our scheme avoids the starvation of lower priority service classes due to the protection of rtPS. Our simulation results show that ADPQ reduces the delay and improves the throughput of rtPS and avoids the starvation of lower priority service classes compared with other scheduling schemes.