-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathQueueAr.java
More file actions
148 lines (129 loc) · 4.1 KB
/
Copy pathQueueAr.java
File metadata and controls
148 lines (129 loc) · 4.1 KB
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
package DataStructures.Queue;
import DataStructures.MyInteger;
import DataStructures.Overflow;
// QueueAr class
//
// CONSTRUCTION: with or without a capacity; default is 10
//
// ******************PUBLIC OPERATIONS*********************
// void enqueue( x ) --> Insert x
// Object getFront( ) --> Return least recently inserted item
// Object dequeue( ) --> Return and remove least recent item
// boolean isEmpty( ) --> Return true if empty; else false
// boolean isFull( ) --> Return true if capacity reached
// void makeEmpty( ) --> Remove all items
// ******************ERRORS********************************
// Overflow thrown for enqueue on full queue
/**
* Array-based implementation of the queue.
* @author Mark Allen Weiss
*/
public class QueueAr
{
/**
* Construct the queue.
*/
public QueueAr( )
{
this( DEFAULT_CAPACITY );
}
/**
* Construct the queue.
*/
public QueueAr( int capacity )
{
theArray = new Object[ capacity ];
makeEmpty( );
}
/**
* Test if the queue is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return currentSize == 0;
}
/**
* Test if the queue is logically full.
* @return true if full, false otherwise.
*/
public boolean isFull( )
{
return currentSize == theArray.length;
}
/**
* Make the queue logically empty.
*/
public void makeEmpty( )
{
currentSize = 0;
front = 0;
back = -1;
}
/**
* Get the least recently inserted item in the queue.
* Does not alter the queue.
* @return the least recently inserted item in the queue, or null, if empty.
*/
public Object getFront( )
{
if( isEmpty( ) )
return null;
return theArray[ front ];
}
/**
* Return and remove the least recently inserted item from the queue.
* @return the least recently inserted item in the queue, or null, if empty.
*/
public Object dequeue( )
{
if( isEmpty( ) )
return null;
currentSize--;
Object frontItem = theArray[ front ];
theArray[ front ] = null;
front = increment( front );
return frontItem;
}
/**
* Insert a new item into the queue.
* @param x the item to insert.
* @exception Overflow if queue is full.
*/
public void enqueue( Object x ) throws Overflow
{
if( isFull( ) )
throw new Overflow( );
back = increment( back );
theArray[ back ] = x;
currentSize++;
}
/**
* Internal method to increment with wraparound.
* @param x any index in theArray's range.
* @return x+1, or 0, if x is at the end of theArray.
*/
private int increment( int x )
{
if( ++x == theArray.length )
x = 0;
return x;
}
private Object [ ] theArray;
private int currentSize;
private int front;
private int back;
static final int DEFAULT_CAPACITY = 10;
public static void main( String [ ] args )
{
QueueAr q = new QueueAr( );
try
{
for( int i = 0; i < 10; i++ )
q.enqueue( new MyInteger( i ) );
}
catch( Overflow e ) { System.out.println( "Unexpected overflow" ); }
while( !q.isEmpty( ) )
System.out.println( q.dequeue( ) );
}
}