--- title: "Petrol pump queue simulation" subject: "Data Structure and Algorithm" chapter: 2 key: "semester_4/data_structure_and_algorithm:petrol-pump-simulation" source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/petrol-pump-simulation site: BCT Engineering --- # Petrol pump queue simulation Data Structure and Algorithm · Chapter 2: The Stack and Queue - Asked in: 2068 Bhadra, 4 marks - Video: [Lec-46: Introduction to Queue Data structure with real life example | Data Structure #queue](https://www.youtube.com/watch?v=YMzZTTO2MpE) — Gate Smashers - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/petrol-pump-simulation - Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-2 ## Question Suppose you are asked to simulate people waiting in a petrol pump, which data structure would you use? Discuss suitable algorithm required for your simulation. ## Short answer Use a queue. Enqueue arriving vehicles; when pump free, dequeue, start = max(arrival, pump_free), wait = start−arrival, update pump_free. For the given arrival and service times, total wait is 11 minutes; average wait = 11/5 = 2.2 minutes. ## Answer #### Data structure A **queue** is the suitable data structure. Vehicles are served in the order they arrive (**FIFO**): a new vehicle joins at the **rear**, and the vehicle at the **front** is served and leaves. A circular array or a linked queue can be used; a linked queue is better because the number of waiting vehicles is not known beforehand. ```text arrive -> [ rear ... ... front ] -> pump -> leave ``` #### Algorithm Assume the pump serves one vehicle at a time. Each vehicle has an arrival time and a service time. Clock `t` runs in minutes. ```text 1. Create an empty queue Q; pump_free_at = 0; total_wait = 0 2. Repeat for each vehicle in order of arrival time: a. ENQUEUE(Q, vehicle) /* vehicle arrives */ 3. While Q is not empty: a. v = DEQUEUE(Q) /* front vehicle goes to the pump */ b. start = max(v.arrival, pump_free_at) c. wait = start - v.arrival d. finish = start + v.service e. pump_free_at = finish f. total_wait = total_wait + wait g. print v, wait, finish 4. average wait = total_wait / number of vehicles ``` In a real-time simulation, step 2 is carried out whenever the clock reaches an arrival time (random arrivals), and QUEUE EMPTY is checked before every dequeue. Underflow means the pump is idle. #### Example Arrival times 0, 1, 2, 6, 7; service times 3, 2, 4, 1, 2 minutes. | Vehicle | Arrival | Service | Start | Wait | Finish | |---|---|---|---|---|---| | C1 | 0 | 3 | 0 | 0 | 3 | | C2 | 1 | 2 | 3 | 2 | 5 | | C3 | 2 | 4 | 5 | 3 | 9 | | C4 | 6 | 1 | 9 | 3 | 10 | | C5 | 7 | 2 | 10 | 3 | 12 | Total wait = 0 + 2 + 3 + 3 + 3 = 11 minutes; **average wait = 11 / 5 = 2.2 minutes**. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Which data structure suits simulating vehicles waiting at a petrol pump? A. Stack B. Queue C. Tree D. Graph Answer: B. Vehicles are served in order of arrival, which is FIFO. (Key point: Choice of structure) 2. In the queue, where does a new vehicle join and which one is served? A. Joins front, served from rear B. Joins rear, served from front C. Joins and served at the top D. Joins the middle Answer: B. Arrivals are enqueued at the rear and the front vehicle is served. (Key point: Where vehicles join) 3. How is a vehicle's service start time computed? A. arrival + service B. max(arrival, pump_free_at) C. pump_free_at only D. min(arrival, pump_free_at) Answer: B. It cannot start before it arrives nor before the pump is free. (Key point: Start time) 4. In the example, what is the average wait? A. 11 minutes B. 2.2 minutes C. 5 minutes D. 3 minutes Answer: B. Total wait 0+2+3+3+3 = 11 over 5 vehicles is 2.2. (Key point: Average wait) ## Related in Data Structure and Algorithm - [Circular queue algorithm with conditions](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Acircular-queue-algorithm-conditions) — Data Structure and Algorithm, chapter 2 - [Unfair service centre simulation](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aunfair-service-centre-simulation) — Data Structure and Algorithm, chapter 2 - [Data structure types and operations](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adata-structure-types-operations) — Data Structure and Algorithm, chapter 1 - [Queue overflow and underflow errors](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aqueue-overflow-underflow) — Data Structure and Algorithm, chapter 2 - [Define data structure and its importance](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adata-structure-importance) — Data Structure and Algorithm, chapter 1 - [Data structure and basic operations](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adata-structure-basic-operations) — Data Structure and Algorithm, chapter 1 ## Related in other subjects - [Java simulation of single server queue](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Ajava-simulation-single-server) — Simulation and Modeling, chapter 9, asked 5× - [Estimating, purpose and data required](https://www.bctengineer.com/question.md?key=semester_7%2Festimating_and_costing%3Aestimating-purpose-data-required) — Estimating and Costing, chapter 1, asked 6× - [Estimated cost never actual; data required](https://www.bctengineer.com/question.md?key=semester_7%2Festimating_and_costing%3Aest-cost-never-actual-data) — Estimating and Costing, chapter 1 - [Data required for detailed estimate](https://www.bctengineer.com/question.md?key=semester_7%2Festimating_and_costing%3Adata-for-detailed-estimate) — Estimating and Costing, chapter 1