/*
 * queues.cpp
 *
 *  Created on: 29.10.2013
 *      Author: trifon
 */

#include "lqueue.cpp"
#include "squeue.cpp"
#include <iostream>
using namespace std;

typedef SQueue<int> TestQueue;

template <typename T>
void copyQueue(Queue<T>& dest, Queue<T>& src,
				T const& sentinel) {
	T x;
	src.push(sentinel);
	while(src.pop(x) && x != sentinel) {
		dest.push(x);
		src.push(x);
	}
}

void printQueue(TestQueue q) {
	int x;
	while (q.pop(x))
		cout << x << endl;
}

void copyQueueTest() {
	TestQueue q1, q2;
	for(int i = 1; i<= 10; i++) {
		q1.push(i);
	}
	copyQueue(q2, q1, 5);
	cout << "Copied queue:" << endl;
	printQueue(q2);
	cout << "Original queue:" << endl;
	printQueue(q1);
}

void print235(int n) {
	LQueue<int> q2, q3, q5;
	int r2, r3, r5;
	q2.push(2);
	q3.push(3);
	q5.push(5);
	cout << 1 << endl;
	for(int i = 1; i < n; i++) {
		q2.head(r2);
		q3.head(r3);
		q5.head(r5);
		int min = r2;
		if (r3 < min)
			min = r3;
		if (r5 < min)
			min = r5;
		cout << min << endl;
		q2.push(min * 2);
		q3.push(min * 3);
		q5.push(min * 5);
		if (min == r2)
			q2.pop(r2);
		if (min == r3)
			q3.pop(r3);
		if (min == r5)
			q5.pop(r5);
	}
}

template <typename T>
T minQueue(Queue<T>& q, T const& sentinel) {
	// искаме да получим q без най-малкия елемент
	q.push(sentinel);
	T min, x;
	q.pop(min);
	while (q.pop(x) && x != sentinel) {
		if (x < min) {
			q.push(min);
			min = x;
		} else
			q.push(x);
	}
	return min;
}

template <typename T>
void readQueue(Queue<T>& q) {
	cout << "Колко? ";
	int n; cin >> n;
	T x;
	for(int i = 0; i < n; i++) {
		cin >> x;
		q.push(x);
	}
}

template <typename T>
void selectionSortQueue(Queue<T>& q, Queue<T>& result, T const& sentinel) {
	while(!q.empty())
		result.push(minQueue(q, sentinel));
}

template <typename T>
void mergeQueues(Queue<T>& q1, Queue<T>& q2, Queue<T>& result) {
	T x1, x2;
	while(q1.head(x1) && q2.head(x2)) {
		if (x1 < x2) {
			result.push(x1);
			q1.pop(x1);
		}
		else {
			result.push(x2);
			q2.pop(x2);
		}
	}
	while (q1.pop(x1))
		result.push(x1);
	while (q2.pop(x2))
		result.push(x2);
}

int main() {
	// copyQueueTest();
	// print235(20);
	TestQueue q,q2;
	readQueue(q);
	readQueue(q2);
	// cout << minQueue(q, 0) << endl;
	// printQueue(q);
	TestQueue r;
	// selectionSortQueue(q, r, 0);
	mergeQueues(q,q2,r);
	printQueue(r);
	return 0;
}