A data stream generating apparatus for a recording/replaying apparatus includes a storage unit and a control module. The control module generates a video elementary stream and an audio elementary stream from inputted video data and audio data to store in the storage unit, and generates and stores a navigation pack in the storage unit. The control module determines an output order of the navigation pack, a plurality of video packs generated from the video elementary stream and a plurality of audio packs generated from the audio elementary stream based on a unit size of an output data stream, a data quantity of the video elementary stream and a data quantity of the audio elementary stream, while updating the navigation pack. Then, the control module outputs the navigation pack, the plurality of video packs, and the plurality of audio packs as an output data stream based on the output order.