java隊(duì)列

undefined

隊(duì)列是一種特殊的線性表，它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。隊(duì)列中沒有元素時(shí)，稱為空隊(duì)列。 　　在隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)中，最先插入的元素將是最先被刪除的元素；反之最后插入的元素將最后被刪除的元素，因此隊(duì)列又稱為“先進(jìn)先出”（FIFO—first in first out）的線性表。 　　隊(duì)列空的條件：front=rear 　　隊(duì)列滿的條件： rear = MAXSIZE.

1. //通過LinkedList實(shí)現(xiàn)隊(duì)列
   
2. package 隊(duì)列和堆棧;
   
3. import java.util.*;
   
4. public class LinkedListQueueTest {
   
5. 
   
6. //字段
   
7. private LinkedList list;
   
8. 
   
9. //無參數(shù)構(gòu)造
   
10. public LinkedListQueueTest()
    
11. {
    
12.   list=new LinkedList();
    
13. }
    
14. 
    
15. //隊(duì)列元素的個(gè)數(shù)
    
16. public int size()
    
17. {
    
18.   return list.size();
    
19. }
    
20. 
    
21. //進(jìn)入隊(duì)列
    
22. public void enqueue(Object obj)
    
23. {
    
24.   list.addLast(obj);
    
25.   
    
26. }
    
27. 
    
28. 
    
29. //對(duì)頭出來
    
30. public Object dequeue()
    
31. {
    
32.   return list.removeFirst();
    
33. }
    
34. 
    
35. //瀏覽對(duì)頭元素
    
36. public Object front()
    
37. {
    
38.   //return list.getFirst();
    
39.   return list.peekFirst();
    
40. }
    
41. 
    
42. //判斷隊(duì)列是否為空
    
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("移除隊(duì)列頭元素："+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("查看隊(duì)列的頭元素："+llq.front());
    
67.   System.out.println(llq.size());
    
68.   System.out.println(llq.isEmpty());
    
69. 
    
70. }
    
71. 
    
72. }
    
73. 通過數(shù)組實(shí)現(xiàn)
    
74. package 隊(duì)列和堆棧;
    
75. 
    
76. import java.util.NoSuchElementException;
    
77. 
    
78. //通過數(shù)組來實(shí)現(xiàn)隊(duì)列
    
79. public class ArrayQueue {
    
80. //字段
    
81. public  static  Object[] data;
    
82. //隊(duì)列的元素個(gè)數(shù)
    
83. protected int size ;
    
84. //隊(duì)列頭
    
85. protected int head;
    
86. //隊(duì)列尾
    
87. public static  int tail;
    
88. /**
    
89.   *
    
90.   */
    
91. //無參數(shù)構(gòu)造函數(shù)
    
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. //隊(duì)列元素個(gè)數(shù)方法
     
101. public int size()
     
102. {
     
103.   return size;
     
104.   
     
105. }
     
106. 
     
107. public boolean isEmpty()
     
108. {
     
109.   return size==0;
     
110. }
     
111. 
     
112. //得到隊(duì)列頭元素
     
113. public Object front()
     
114. {
     
115.   if(size==0)
     
116.    throw new NoSuchElementException();
     
117.   return data[head];
     
118.   
     
119. }
     
120. 
     
121. //進(jìn)入隊(duì)列enqueue()方法
     
122. public void enqueue(Object obj)
     
123. {
     
124.   //此時(shí)隊(duì)列已經(jīng)滿
     
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. //隊(duì)列的元素出隊(duì)
     
143. public Object dequeue()
     
144. {
     
145.   if(size==0)
     
146.    throw new NoSuchElementException();
     
147.   Object ele=data[head];
     
148.   //循環(huán)隊(duì)列
     
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. 通過向量實(shí)現(xiàn)：
     
162. //通過向量實(shí)現(xiàn)棧
     
163. package 隊(duì)列和堆棧;
     
164. import java.util.*;
     
165. public class VectorStackTest {
     
166. //字段
     
167. Vector  v;
     
168. 
     
169. //構(gòu)造函數(shù)
     
170. public VectorStackTest()
     
171. {
     
172.   v=new Vector();
     
173. }
     
174. 
     
175. //元素的個(gè)數(shù)
     
176. public int size()
     
177. {
     
178.   return v.size();
     
179. }
     
180. 
     
181. //是否為空
     
182. public boolean isEmpty()
     
183. {
     
184.   return size()==0;
     
185. }
     
186. 
     
187. //進(jìn)棧
     
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. }

復(fù)制代碼