Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit7f523ff

Browse files
authored
Merge pull requestTheAlgorithms#712 from AnkitAtBrillio/local
Adding Linked List based General queue implementation
2 parents3551433 +481be62 commit7f523ff

File tree

4 files changed

+283
-0
lines changed

4 files changed

+283
-0
lines changed
Lines changed: 136 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,136 @@
1+
packagesrc.main.java.com.dataStructures;
2+
3+
importsrc.main.java.com.types.Queue;
4+
5+
importjava.util.Iterator;
6+
importjava.util.LinkedList;
7+
importjava.util.NoSuchElementException;
8+
9+
/**
10+
* linkedList based implementation of queue.
11+
* This implementation is not thread safe and need exclusive thread safety measures from the client.
12+
*
13+
* @param <T>
14+
*/
15+
publicclassGeneralQueue<T>implementsQueue<T> {
16+
17+
privateLinkedList<T>queue;
18+
privateIterator<T>itr;
19+
20+
/**
21+
* Overloaded constructor to create queue of specific size
22+
*/
23+
publicGeneralQueue() {
24+
queue =newLinkedList<>();
25+
}
26+
27+
@Override
28+
publicbooleanadd(Tt) {
29+
30+
if (queue ==null) {
31+
thrownewIllegalStateException();
32+
}
33+
if (t ==null) {
34+
thrownewNullPointerException();
35+
}
36+
queue.add(t);
37+
returntrue;
38+
}
39+
40+
@Override
41+
publicbooleanremove(Tt) {
42+
if (null ==queue) {
43+
thrownewNullPointerException();
44+
}
45+
if (queue.isEmpty()) {
46+
thrownewNoSuchElementException();
47+
}
48+
queue.remove(t);
49+
returntrue;
50+
}
51+
52+
@Override
53+
publicbooleanisEmpty() {
54+
returnnull ==queue ||queue.size() ==0;
55+
}
56+
57+
@Override
58+
publicIterator<T>iterator() {
59+
if (queue ==null) {
60+
returnnull;
61+
}
62+
itr =queue.iterator();
63+
returnitr;
64+
}
65+
66+
@Override
67+
publicbooleanoffer(Tt) {
68+
if (null ==queue) {
69+
returnfalse;
70+
}
71+
if (t ==null) {
72+
thrownewNullPointerException();
73+
}
74+
queue.add(t);
75+
returntrue;
76+
}
77+
78+
@Override
79+
publicTpoll() {
80+
if (queue ==null ||queue.isEmpty()) {
81+
returnnull;
82+
}
83+
84+
returnqueue.pollFirst();
85+
}
86+
87+
@Override
88+
publicTelement() {
89+
if (queue ==null ||queue.isEmpty()) {
90+
thrownewNoSuchElementException();
91+
}
92+
93+
returnqueue.peekFirst();
94+
}
95+
96+
@Override
97+
publicTpeek() {
98+
if (null ==queue ||queue.size() ==0) {
99+
returnnull;
100+
}
101+
102+
returnqueue.peekFirst();
103+
}
104+
105+
@Override
106+
publicbooleanhasNext() {
107+
returnitr.hasNext();
108+
}
109+
110+
@Override
111+
publicTnext() {
112+
returnitr.next();
113+
}
114+
115+
@Override
116+
publicObject[]toArray() {
117+
Object[]elements = {};
118+
if (null ==queue ||queue.isEmpty()) {
119+
returnelements;
120+
}
121+
elements =newObject[queue.size()];
122+
for (inti =0;i <queue.size();i++) {
123+
elements[i] =queue.get(i);
124+
}
125+
126+
returnelements;
127+
}
128+
129+
@Override
130+
publicintsize() {
131+
if (null ==queue ||queue.isEmpty()) {
132+
return0;
133+
}
134+
returnqueue.size();
135+
}
136+
}
Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
packagesrc.main.java.com.types;
2+
3+
importjava.util.Iterator;
4+
5+
/**
6+
* This interface is to define bacis functionality expected out of any implementation class
7+
* Since this is a data structure it should have the flexibility to contain any kind of object hence it has been made generic
8+
* Any implementation class need not to be thread safe or it could be depending on the implementation class how does it want to behave.
9+
*
10+
* @param <T>
11+
*/
12+
publicinterfaceDataStructure<T>extendsIterator<T> {
13+
14+
/**
15+
* Method to add element in the structure
16+
*
17+
* @param t element
18+
* @return boolean
19+
*/
20+
booleanadd(Tt);
21+
22+
/**
23+
* Method to remove the given object from structure
24+
*
25+
* @param o element
26+
* @return boolean
27+
*/
28+
booleanremove(To);
29+
30+
/**
31+
* Method to get Iterator to parse on the given structure
32+
*
33+
* @return iterator
34+
*/
35+
Iterator<T>iterator();
36+
37+
/**
38+
* Method to check if structure is empty
39+
*
40+
* @return boolean
41+
*/
42+
booleanisEmpty();
43+
44+
/**
45+
* Method to get all the elements of data structure in array
46+
*
47+
* @return arr
48+
*/
49+
Object[]toArray();
50+
51+
/**
52+
* Method to get the size or number of elements in structure
53+
*
54+
* @return size
55+
*/
56+
intsize();
57+
}

‎src/main/java/com/types/Queue.java

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
packagesrc.main.java.com.types;
2+
3+
4+
importjava.util.NoSuchElementException;
5+
6+
/**
7+
* Interface to provide queue specific functionality to the implementing class
8+
* This interface only defines the functionality which the queue implementing classes require.
9+
* Any class having queue behaviour should implement this interface and override all of its methods
10+
*
11+
* @param <T>
12+
*/
13+
publicinterfaceQueue<T>extendsDataStructure<T> {
14+
15+
/**
16+
* Method to add element
17+
*
18+
* @param t element
19+
* @return boolean
20+
* @throws NullPointerException
21+
*/
22+
booleanoffer(Tt)throwsNullPointerException;
23+
24+
/**
25+
* Method to remove element
26+
*
27+
* @return element
28+
*/
29+
Tpoll();
30+
31+
/**
32+
* Method to check element on head
33+
*
34+
* @return element
35+
*/
36+
Tpeek();
37+
38+
/**
39+
* Method to check element on head. This throws exception on runtime if the queue is empty
40+
*
41+
* @return element
42+
* @throws NoSuchElementException
43+
*/
44+
Telement()throwsNoSuchElementException;
45+
}
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
packagesrc.test.java.com.dataStructures;
2+
3+
4+
importorg.junit.Assert;
5+
importorg.junit.Test;
6+
importsrc.main.java.com.dataStructures.GeneralQueue;
7+
importsrc.main.java.com.types.Queue;
8+
9+
publicclassGeneralQueueTest {
10+
11+
@Test
12+
publicvoidtestGeneralQueue() {
13+
14+
Queue<Integer>myQueue =newGeneralQueue<>();
15+
myQueue.add(10);
16+
myQueue.add(20);
17+
myQueue.add(30);
18+
myQueue.add(40);
19+
myQueue.add(50);
20+
21+
22+
Object[]myArray =myQueue.toArray();
23+
Assert.assertEquals(myArray.length,myQueue.size());
24+
25+
myQueue.remove(20);
26+
Assert.assertEquals(myQueue.size(),4);
27+
28+
BooleanisEmpty =myQueue.isEmpty();
29+
Assert.assertEquals(Boolean.valueOf("false"),Boolean.valueOf(isEmpty));
30+
31+
myQueue.offer(60);
32+
Assert.assertEquals(5,myQueue.size());
33+
34+
intpolledElement =myQueue.poll();
35+
Assert.assertEquals(10,polledElement);
36+
37+
intelement =myQueue.element();
38+
Assert.assertEquals(30,element);
39+
40+
myQueue.poll();
41+
intpeekedElement =myQueue.peek();
42+
Assert.assertEquals(40,peekedElement);
43+
44+
}
45+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp