1

Railway Reservation
System
using Stack \ Queue
3
4

CHAPTER 01
Introduction to the Railway
Reservation System Project
This project focuses on simulating a simplified railway
ticket reservation system, demonstrating the practical application of
two core data structures: the Stack and the Queue.

Role in the
Data Structure Key Operation
System

Used to manage passengers who could not

get a confirmed seat. Since tickets are
Waiting List allotted on a First-Come, First-Served (FCFS)
Queue
Management basis when a confirmed ticket is canceled,
the queue ensures fairness and chronological
processing.

Can be used to manage the history of recent

actions (e.g., ticket bookings, cancellations).
Transaction This allows for easy implementation of an
Stack
History/Undo "undo" feature for the last operation or for
quickly reviewing the most recent successful
bookings.

A simple list or array is typically used to hold

Other Passenger
the confirmed passenger records and to
(List/Array/Hash Records/Seat
track the status of available seats on the
Map) Inventory
train.
5

2. System Functionalities
The system will perform the following critical
operations:

 Book Tickets (Primary Function):

o Check for seat availability.

o If a seat is available, the passenger is added

to the confirmed Passenger Records.

o If no seats are available, the passenger is

added to the Waiting List Queue.

 Cancel Tickets (Managing Flow):

o The confirmed passenger is removed from

the Passenger Records.

o The seat is marked as available.

o Crucially, the first passenger (DEQUEUE)

from the Waiting List Queue is immediately
confirmed and moved to the Passenger
Records.

 Manage Waiting List (Automation):

o The Queue handles all waiting passengers

automatically. When a cancellation occurs,
the person waiting the longest (the front of
the queue) gets the seat next.

 Maintain Passenger Records:

6

o A list or array holds the confirmed passenger

details (PNR, Name, Seat Number).

3. Benefits of Using Stacks and Queues

 Fairness (Queue): The queue inherently
enforces the FCFS principle for the waiting list,
which is essential for any fair reservation
system.

 Orderly Management (Stack): The stack's Last-

In, First-Out (LIFO) nature is perfect for
tracking recent activities, making debugging and
history tracking straightforward.

 Simplicity: For an academic project, these

structures provide a clear and elegant way to
model real-world processes.

 Solving Railway
Reservation
Challenges with Data
Structures
This project is a robust C-implementation of a railway reservation
system designed to eliminate the inherent inefficiencies, errors, and
unfairness associated with manual or poorly managed booking
processes. We leverage the fundamental properties of the Queue and
7

the Stack to automate and manage core operations with accuracy and
transparency.

1. The Core Problem Statement

The central challenge in any booking system is managing limited
inventory (seats) and ensuring fair and orderly processing of overflow
demand.

Manual System Problem Data Structure Solution

Confusion: Manually tracking Confirmed List (Queue): Provides

who is confirmed and who is an orderly, sequential list of
waiting. reserved passengers.

Unfairness/Delays:
Waiting List (Queue): Ensures strict
Inefficiently promoting the
First-Come, First-Served (FCFS)
next waiting passenger upon
promotion.
cancellation.

Undo Operation (Stack): Provides a

Mistakes: No way to quickly simple Last-In, First-Out (LIFO)
reverse a cancellation error. mechanism for transaction
reversal.

Data Loss: Difficulty in saving

File Storage: Persists all Queue and
and loading records properly
Stack data for system reload.
for continuity.
8

2. Solution 1: Automated Waiting List Management

using a Queue
The Queue is the primary structure used for managing the flow of
passengers, ensuring fairness and automating the promotion process.
A. Waiting List $\rightarrow$ Queue (FCFS Principle)
When all available seats are filled, new passengers are ENQUEUED
(added to the rear) into the Waiting List Queue. This action strictly
adheres to the First-Come, First-Served (FCFS) principle, which is non-
negotiable for a fair reservation system.
B. Automatic Promotion on Cancellation
This is the most critical function solved by the Queue:
1. A confirmed passenger cancels their ticket.
2. The system immediately DEQUEUES (removes from the front) the
passenger who has been waiting the longest.
3. This promoted passenger is then moved to the Confirmed List.
This automated process guarantees that there are no delays and no
human bias in allocating newly available seats.
Key Benefit: The Queue solves the problem of "Who should be
promoted on cancellation?" by making it a guaranteed, sequential, and
automatic operation.

3. Solution 2: Transaction Reversal using a Stack

The Stack is used to manage transient operations, specifically to provide
a mechanism for reversing an erroneous action, such as a mistake
during ticket cancellation.
A. Tracking Cancellations
9

When a legitimate cancellation occurs, the details of the cancelled

ticket (e.g., PNR, Name, Seat Number) are PUSHED onto the Undo
Stack.
B. The Undo Operation (LIFO Principle)
If an operator realizes they canceled the wrong ticket, the Undo feature
executes a single POP operation:
 The most recently cancelled passenger record (the one at the top
of the Stack) is retrieved.
 The system uses this retrieved data to restore the ticket, effectively
reversing the cancellation.
Key Benefit: The Stack solves the problem of "How to undo a wrong
cancellation?" by isolating the most recent change, which is the only
change that needs to be reversed in a typical transaction-based system.

4. Solution 3: The Confirmed List (Queue/Array

Combination)
The Confirmed List, while often implemented as a simple array or linked
list for fast random access (e.g., searching by PNR), maintains the
booking order, reflecting the FCFS nature.
 Booking: Passengers are added to this list in the order they secure
a seat.
 Tracking: This list provides a direct answer to the question "Who is
confirmed?"

5. File Storage for Persistence

The system achieves long-term reliability and continuity through File
Storage.
10

 All passenger data from the Confirmed List and the Waiting List
Queue are serialized (converted into a string format) and saved into
a plain text file, such as [Link].
 Upon restarting the application, the system reads from [Link],
re-constructs the Queue and the Confirmed List exactly as they
were, ensuring no data loss between sessions.
This final step solves the problem of "How to save all records properly?"
by making the system state persistent.

Project Impact Summary

Your project provides a system that is:

Data Structure
Metric Achievement
Responsible

Eliminates manual errors in Queue (for strict

Accuracy
tracking and promotion. FCFS)

Guarantees the longest-waiting

Queue (for
Fairness passenger gets the next
promotion order)
available seat.

Allows for reversal of the last Stack (for

Accountability
operational mistake. Undo/Redo)

Ensures all records persist

Reliability File Storage
between system shut-downs.

Project Goal :---

11

The overall goal of this project is to design and implement a

comprehensive Railway Reservation System in the C programming
language that leverages sophisticated, yet fundamental, data structures
—the Queue and the Stack—to ensure maximum efficiency, fairness,
and reliability in managing passenger bookings.
This project specifically aims to eliminate the common pitfalls
associated with manual or simplistic computerized booking methods,
providing a model that is robust, automated, and easy to audit.
Detailed Objectives and Their Strategic Importance:
1. To Implement a Robust Queue for Waiting List
Management (Fairness and Automation):
o Objective: Develop a fully functional Queue data structure
(likely implemented using an array or a linked list) dedicated
exclusively to holding passengers who could not secure a
confirmed seat.
o Strategic Importance: This structure enforces the First-Come,
First-Served (FCFS) principle. By using the ENQUEUE operation
to add new waiting passengers to the rear and the DEQUEUE
operation to promote the passenger at the front, we automate
the critical process of moving passengers from the waiting list
to confirmed status the instant a seat becomes available. This
removes human judgment, ensures impartiality, and prevents
delays.
2. To Implement a Reliable Stack for Transaction
Reversal (Accountability and Error Correction):
o Objective: Construct a Stack data structure to record the
details of recently performed cancellation operations.
12

o Strategic Importance: The Stack operates on the Last-In, First-

Out (LIFO) principle, which is ideal for an "Undo" feature. If an
operator accidentally cancels a confirmed ticket, the system
can execute a POP operation on the Stack. This retrieves the
most recent cancellation record and automatically uses that
data to restore the passenger's booking. This provides a crucial
layer of accountability and error recovery, which is often
missing in basic systems.
3. To Establish and Maintain Accurate Passenger
Records (Core Functionality):
o Objective: Create a primary list or array (the Confirmed List) to
store the PNR, name, seat number, and other vital details of all
passengers with confirmed tickets.
o Strategic Importance: This list is the system's single source of
truth for seat occupancy. Its integrity is maintained by strict
interaction with the Queue (when promoting a waiting
passenger) and the Stack (when reversing a cancellation).
4. To Ensure System Data Persistence (Reliability and
Continuity):
o Objective: Integrate file handling capabilities (using C's file I/O)
to save the current state of both the Confirmed List and the
Waiting List Queue to an external file (e.g., [Link]) before
system shutdown.
o Strategic Importance: This critical step ensures that the system
is reliable. Upon startup, the application will read the file and
dynamically reconstruct the Queue and the Confirmed List
exactly as they were, preventing any loss of passenger data or
sequence order.
13

Project Scope: Coverage and

Limitations
The scope of this Railway Reservation System project is strategically
defined to focus on the effective demonstration of the Queue and Stack
data structures in a practical, problem-solving context.
Coverage (What the Project Includes)
The project successfully models and automates the core logic required
for a small-scale, internal reservation system:
 Ticket Booking and Cancellation: The system handles the basic life
cycle of a ticket, from initial confirmation to cancellation.
 Automated Waiting List Management: The project fully
implements and demonstrates the Queue data structure to
maintain a fair, sequential waiting list and automatically promote
the next passenger upon cancellation.
 Transaction Reversal (Undo): The project incorporates the Stack
data structure to provide a limited, yet crucial, Undo functionality
for the last cancellation transaction, allowing for immediate error
correction.
 Passenger Record Persistence: The system utilizes file I/O to save
and load all passenger data (Confirmed and Waiting List) between
program executions, ensuring continuity and reliability.
 In-Memory Data Structures: All critical operations (booking,
cancellation, promotion) are performed efficiently on data
structures held entirely within the computer's memory while the
program is running.
Limitations (What the Project Does NOT Cover)
14

To maintain focus and complexity appropriate for a data structures

demonstration project, the system has the following limitations:
 Single Train/Route Focus: The system is limited to managing
reservations for a single train or route with a fixed, predefined
number of seats. It does not handle multiple trains, dynamic
routing, or complex fare structures.
 No Concurrent Users: This is a single-user, local application. It does
not include database connectivity, networking, or the necessary
concurrency controls (like locks or semaphores) required to handle
multiple simultaneous booking requests from different users (e.g.,
an online website).
 Simplified Search and Reporting: Search functionality is minimal,
typically limited to finding a passenger by PNR or name. Advanced
features like graphical reports, occupancy statistics, or detailed
financial summaries are outside the scope.
 Fixed Seat Allocation: Seats are allocated sequentially as booked
(e.g., Seat 1, Seat 2, etc.). It does not include complex seat
selection options (e.g., choosing window/aisle, upper/lower berth).
 Limited Undo Functionality: The Stack is used only to reverse the
immediately preceding cancellation operation. It does not support
multi-level undo, re-do, or complex transaction logging across
various system functions.

CHAPTER 02
15

System Requirement
Analysis

⚙️Functional Requirements
The following features define the mandatory functionalities that the
Railway Reservation System, built using the Stack and Queue data
structures, must implement to solve the stated problem and meet the
project goals.
1. Booking and Seat Allocation
 FR1.1: Seat Availability Check: The system must check if confirmed
seats are available on the train.
 FR1.2: Confirmed Booking: If seats are available, the system must
book the ticket, generate a unique PNR, allocate a sequential seat
number, and add the passenger to the Confirmed List.
 FR1.3: Waiting List Addition: If no confirmed seats are available,
the system must add the passenger to the Waiting List Queue
using the ENQUEUE operation, assigning a Waiting List (WL)
number.

2. Cancellation and Promotion

 FR2.1: Ticket Cancellation: The user must be able to cancel a ticket
using its PNR. The system must remove the passenger from the
Confirmed List and mark the seat as available.
 FR2.2: Stack Logging: Upon a successful cancellation, the details of
the cancelled ticket must be immediately recorded onto the Undo
Stack using the PUSH operation.
16

 FR2.3: Automated Promotion: After a cancellation, the system

must check the Waiting List Queue. If the queue is not empty, it
must automatically promote the passenger at the front using the
DEQUEUE operation and move them to the Confirmed List,
assigning them the newly available seat.

3. Error Correction (Undo)

 FR3.1: Undo Last Cancellation: The system must provide a specific
function to perform an Undo operation. This operation must use
the Stack's POP function to retrieve the most recent cancellation
record.
 FR3.2: Restore Booking: The system must use the data retrieved
from the POP operation to restore the passenger's ticket status
back to confirmed, effectively reversing the mistake.

4. Data Management and Persistence

 FR4.1: Display Status: The system must display the current status
of:
o The Confirmed Passenger List (PNR, Name, Seat Number).
o The Waiting List Queue (PNR, Name, WL Number).
 FR4.2: Save State: The system must have a function to save the
complete contents of both the Confirmed List and the Waiting List
Queue to an external file (e.g., [Link]).
 FR4.3: Load State: Upon startup, the system must automatically
read data from the file and reconstruct the Confirmed List and the
Waiting List Queue data structures, restoring the system to its last
saved state.

5. Utilities
17

 FR5.1: Passenger Search: The user must be able to search for a

passenger's status using their PNR or name.
 FR5.2: Display Seat Count: The system must display the current
number of available confirmed seats and the count of passengers in
the Waiting List Queue.

Non-functional Requirements (NFRs)

Non-functional requirements specify the criteria that judge the
operation of the system, rather than specific behaviors (which are
covered by functional requirements). These define the quality and
constraints of your Railway Reservation System.
1. Performance
 NFR1.1: Response Time: All core operations (Booking, Cancellation,
Promotion) must have a near-instantaneous response time, ideally
completing within 200 milliseconds under standard load. This is
critical because the use of the Queue (for promotion) and Stack (for
undo) operations are $O(1)$ complexity, ensuring speed.
 NFR1.2: Efficiency (Space): The system must efficiently manage
memory usage. The choice of implementation (e.g., using a linked
list for the Queue/Stack vs. a static array) should be optimized to
avoid unnecessary memory overhead.
 NFR1.3: Scalability (Wait List): The Waiting List Queue must be
able to handle a large volume of passengers (e.g., up to 10 times
the capacity of the confirmed seats) without significant
performance degradation.
2. Usability
18

 NFR2.1: Ease of Use: The system interface (command-line menu)

must be intuitive and easy for an operator to navigate, requiring
minimal training.
 NFR2.2: Clarity of Output: Status displays (Confirmed List, Waiting
List) must be clear, well-formatted, and provide all necessary
information (PNR, Name, Seat/WL Number) at a glance.
 NFR2.3: Error Handling: The system must provide clear, human-
readable error messages (e.g., "PNR not found," "Waiting List is
Empty," "No seats available") rather than crashing or displaying raw
system errors.
3. Reliability and Availability
 NFR3.1: Data Integrity: The system must ensure that the Queue's
FCFS order is never violated and the Stack's LIFO order is always
maintained, even during file loading/saving.
 NFR3.2: Persistence: The system must reliably save all confirmed
and waiting list data to the file before exiting and reload it correctly
upon startup (as per FR4.2 and FR4.3).
 NFR3.3: System Stability: The application must be robust and not
crash or enter an infinite loop when faced with invalid inputs (e.g.,
non-numeric input when expecting a PNR).
4. Security (Limited Scope)
 NFR4.1: Data Access: Since this is a local C application, passenger
records ([Link]) must be stored locally. Access to the physical
file should be restricted to authorized users/operators.
 NFR4.2: Input Validation: All user inputs (PNR, name, choice
selections) must be validated to prevent buffer overflows or
unexpected system behavior due to malicious or improperly
formatted data.
19

5. Portability
 NFR5.1: Platform Compatibility: As a standard C program, the
compiled system should be easily portable and runnable across
different operating systems (Windows, Linux, macOS) without
requiring external libraries or dependencies.
20