-
Notifications
You must be signed in to change notification settings - Fork 10
/
Merge Two Queue
113 lines (84 loc) · 2.23 KB
/
Merge Two Queue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
public class QueueImpl implements IntQueue {
protected int capacity;
public static final int CAPACITY = 100;
protected int Q[];
protected int f = 0, r = 0;
public QueueImpl() {
this(CAPACITY);
}
public QueueImpl(int cap) {
capacity = cap;
Q = new int[capacity];
}
public void enqueue(int value) throws Exception {
if (getSize() == capacity - 1) {
throw new Exception("Full"); //To change body of generated methods, choose Tools | Templates.
}
Q[r] = value;
r = (r + 1) % capacity;
}
public int dequeue() throws Exception {
int element;
if (isEmpty()) {
throw new Exception("Empty"); //To change body of generated methods, choose Tools | Templates.
}
element = Q[f];
f = (f + 1) % capacity;
return element;
}
public int getSize() {
return (capacity - f + r) % capacity;
}
public boolean isEmpty() {
return (f == r);
}
public String toString() {
int z = f;
String s;
s = "f[";
if (getSize() >= 1) {
s += Q[0];
for (int i = 1; i <= getSize() - 1; i++) {
s += " " + Q[z + 1];
z = (z + 1) % capacity;
}
}
return s + "]b";
}
}
My solution: public class Assign2Problem3Solution {
public static IntQueue merge(IntQueue q1, IntQueue q2) throws Exception {
IntQueue merged = new QueueImpl();
int a, b, k, t, m;
if (a < b) {
k = a;
t = b - a;
} else {
k = b;
t = a - b;
}
for (int i = 0; i < k; i++) {
a = q1.dequeue();
b = q2.dequeue();
if (a < b) {
merged.enqueue(a);
merged.enqueue(b);
} else if (b < a) {
merged.enqueue(b);
merged.enqueue(a);
}
}
if (q1.getSize() > q2.getSize()) {
for (int i = 0; i < t; i++) {
m = q1.dequeue();
merged.enqueue(m);
}
} else if (q1.getSize() < q2.getSize()) {
for (int i = 0; i < t; i++) {
m = q2.dequeue();
merged.enqueue(m);
}
}
return merged;
}
}