java队列

undefined

队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。 　　在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将最后被删除的元素，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。 　　队列空的条件：front=rear 　　队列满的条件： rear = MAXSIZE.

1. //通过LinkedList实现队列
   
2. package 队列和堆栈;
   
3. import java.util.*;
   
4. public class LinkedListQueueTest {
   
5. 
   
6. //字段
   
7. private LinkedList list;
   
8. 
   
9. //无参数构造
   
10. public LinkedListQueueTest()
    
11. {
    
12.   list=new LinkedList();
    
13. }
    
14. 
    
15. //队列元素的个数
    
16. public int size()
    
17. {
    
18.   return list.size();
    
19. }
    
20. 
    
21. //进入队列
    
22. public void enqueue(Object obj)
    
23. {
    
24.   list.addLast(obj);
    
25.   
    
26. }
    
27. 
    
28. 
    
29. //对头出来
    
30. public Object dequeue()
    
31. {
    
32.   return list.removeFirst();
    
33. }
    
34. 
    
35. //浏览对头元素
    
36. public Object front()
    
37. {
    
38.   //return list.getFirst();
    
39.   return list.peekFirst();
    
40. }
    
41. 
    
42. //判断队列是否为空
    
43. public boolean isEmpty()
    
44. {
    
45.   return list.isEmpty();
    
46. }
    
47. 
    
48. 
    
49. /**
    
50.   * @param args
    
51.   */
    
52. public static void main(String[] args) {
    
53.   // TODO Auto-generated method stub
    
54.   
    
55.   LinkedListQueueTest llq=new LinkedListQueueTest();
    
56.   System.out.println(llq.isEmpty());
    
57.   llq.enqueue("147");
    
58.   llq.enqueue("258");
    
59.   llq.enqueue("369");
    
60.   System.out.println(llq.size());
    
61.   System.out.println("移除队列头元素："+llq.dequeue());
    
62.   System.out.println(llq.size());
    
63.   llq.enqueue("abc");
    
64.   llq.enqueue("def");
    
65.   System.out.println(llq.size());
    
66.   System.out.println("查看队列的头元素："+llq.front());
    
67.   System.out.println(llq.size());
    
68.   System.out.println(llq.isEmpty());
    
69. 
    
70. }
    
71. 
    
72. }
    
73. 通过数组实现
    
74. package 队列和堆栈;
    
75. 
    
76. import java.util.NoSuchElementException;
    
77. 
    
78. //通过数组来实现队列
    
79. public class ArrayQueue {
    
80. //字段
    
81. public  static  Object[] data;
    
82. //队列的元素个数
    
83. protected int size ;
    
84. //队列头
    
85. protected int head;
    
86. //队列尾
    
87. public static  int tail;
    
88. /**
    
89.   *
    
90.   */
    
91. //无参数构造函数
    
92. public ArrayQueue() {
    
93.   final int INITIAL_LENGTH=3;
    
94.   data=new Object[INITIAL_LENGTH];
    
95.   size=0;
    
96.   head=0;
    
97.   tail=-1;
    
98. }
    
99. 
    
100. //队列元素个数方法
     
101. public int size()
     
102. {
     
103.   return size;
     
104.   
     
105. }
     
106. 
     
107. public boolean isEmpty()
     
108. {
     
109.   return size==0;
     
110. }
     
111. 
     
112. //得到队列头元素
     
113. public Object front()
     
114. {
     
115.   if(size==0)
     
116.    throw new NoSuchElementException();
     
117.   return data[head];
     
118.   
     
119. }
     
120. 
     
121. //进入队列enqueue()方法
     
122. public void enqueue(Object obj)
     
123. {
     
124.   //此时队列已经满
     
125.   if(size==data.length){
     
126.    Object[] oldData=data;
     
127.    data=new Object[data.length*2];
     
128.    //if(head==0)
     
129.    System.arraycopy(oldData, head, data, 0, oldData.length-head);
     
130.    if(head>0)
     
131.     System.arraycopy(oldData, 0, data, head+1, tail+1);
     
132.    head=0;
     
133.    tail=oldData.length-1;
     
134.    
     
135.   }
     
136.   tail=(tail+1)%data.length;
     
137.   size++;
     
138.   data[tail]=obj;
     
139.   
     
140. }
     
141. 
     
142. //队列的元素出队
     
143. public Object dequeue()
     
144. {
     
145.   if(size==0)
     
146.    throw new NoSuchElementException();
     
147.   Object ele=data[head];
     
148.   //循环队列
     
149.   head=(head+1)%data.length;
     
150.   size--;
     
151.   return ele;
     
152. }
     
153. 
     
154. @Override
     
155. public String toString() {
     
156.   // TODO Auto-generated method stub
     
157.   return super.toString();
     
158. }
     
159. 
     
160. }
     
161. 通过向量实现：
     
162. //通过向量实现栈
     
163. package 队列和堆栈;
     
164. import java.util.*;
     
165. public class VectorStackTest {
     
166. //字段
     
167. Vector  v;
     
168. 
     
169. //构造函数
     
170. public VectorStackTest()
     
171. {
     
172.   v=new Vector();
     
173. }
     
174. 
     
175. //元素的个数
     
176. public int size()
     
177. {
     
178.   return v.size();
     
179. }
     
180. 
     
181. //是否为空
     
182. public boolean isEmpty()
     
183. {
     
184.   return size()==0;
     
185. }
     
186. 
     
187. //进栈
     
188. public Object Push(Object obj)
     
189. {
     
190.   v.addElement(obj);
     
191.   return obj;
     
192. }
     
193. 
     
194. //出栈方法
     
195. public Object Pop()
     
196. {
     
197.   int len=size();
     
198.   Object obj=Peek();
     
199.   v.removeElementAt(len-1);
     
200.   return obj;
     
201. }
     
202. 
     
203. //查看栈顶元素
     
204. public Object Peek()
     
205. {
     
206.   int len = size();
     
207.   if (len == 0)
     
208.       throw new EmptyStackException();
     
209.   return v.elementAt(len - 1);
     
210. }
     
211. /**
     
212.   * @param args
     
213.   */
     
214. public static void main(String[] args) {
     
215.   // TODO Auto-generated method stub
     
216.   VectorStackTest vst=new VectorStackTest();
     
217.   System.out.println("大小："+vst.size());
     
218.   vst.Push("123");
     
219.   vst.Push("456");
     
220.   vst.Push("789");
     
221.   vst.Push("abc");
     
222.   System.out.println("大小："+vst.size());
     
223.   System.out.println("栈顶："+vst.Peek());
     
224.   System.out.println("出栈："+vst.Pop());
     
225.   vst.Push("def");
     
226.   vst.Push("147");
     
227.   System.out.println("大小："+vst.size());
     
228.   System.out.println("栈顶："+vst.Peek());
     
229.   System.out.println("出栈："+vst.Pop());
     
230.   System.out.println(vst.Peek());
     
231.   vst.Push("def");
     
232.   vst.Push("147");
     
233.   System.out.println(vst.Pop());
     
234.   System.out.println(vst.Pop());
     
235.   System.out.println(vst.Peek());
     
236.   System.out.println(vst.Pop());
     
237.   System.out.println(vst.Pop());
     
238.   vst.Push("1aadf");
     
239.   vst.Push("2dafad");
     
240.   vst.Push("123789");
     
241.   System.out.println(vst.Pop());
     
242.   System.out.println(vst.Peek());
     
243.   System.out.println(vst.Pop());
     
244.   System.out.println(vst.Peek());
     
245.   System.out.println("------------------end------------");
     
246.   VectorStackTest llst=new VectorStackTest();
     
247.   llst.Push("123");
     
248.   llst.Push("456");
     
249.   System.out.println("栈顶："+llst.Peek());
     
250.   System.out.println("出栈："+llst.Pop());
     
251.   System.out.println(llst.Peek());
     
252.   llst.Push("789");
     
253.   llst.Push("abc");
     
254.   System.out.println("栈顶："+llst.Peek());
     
255.   System.out.println("出栈："+llst.Pop());
     
256.   System.out.println(llst.size());
     
257.   System.out.println("栈顶："+llst.Peek());
     
258. 
     
259.   
     
260.   
     
261. 
     
262. 
     
263. 
     
264.   
     
265. 
     
266. }
     
267. 
     
268. }

复制代码