数据结构之栈和队列

 我们知道，在数组中，若知道数据项的下标，便可立即访问该数据项，或者通过顺序搜索数据项，访问到数组中的各个数据项。但是栈和队列不同，它们的访问是受限制的，即在特定时刻只有一个数据项可以被读取或者被删除。众所周知，栈是先进后出，只能访问栈顶的数据，队列是先进先出，只能访问头部数据。这里不再赘述。

    栈的主要机制可以用数组来实现，也可以用链表来实现，下面用数组来实现栈的基本操作：

[java] view
plain copy

1. public class ArrayStack {  
2.     private long[] a;  
3.     private int size; //栈数组的大小  
4.     private int top; //栈顶  
5.   
6.     public ArrayStack(int maxSize) {  
7.         this.size = maxSize;  
8.         this.a = new long[size];  
9.         this.top = -1; //表示空栈  
10.     }  
11.       
12.     public void push(long value) {//入栈  
13.         if(isFull()) {  
14.             System.out.println("栈已满！");  
15.             return;  
16.         }  
17.         a[++top] = value;  
18.     }  
19.       
20.     public long peek() {//返回栈顶内容，但不删除  
21.         if(isEmpty()) {  
22.             System.out.println("栈中没有数据");  
23.             return 0;  
24.         }  
25.         return a[top];  
26.     }  
27.       
28.     public long pop() { //弹出栈顶内容，删除  
29.         if(isEmpty()) {  
30.             System.out.println("栈中没有数据！");  
31.             return 0;  
32.         }  
33.         return a[top--];          
34.     }  
35.       
36.     public int size() {  
37.         return top + 1;  
38.     }  
39.       
40.     public boolean isEmpty() {  
41.         return (top == -1);  
42.     }  
43.       
44.     public boolean isFull() {  
45.         return (top == size -1);  
46.     }  
47.       
48.     public void display() {  
49.         for(int i = top; i >= 0; i--) {  
50.             System.out.print(a[i] + " ");  
51.         }  
52.         System.out.println("");  
53.     }  
54. }  

    数据项入栈和出栈的时间复杂度均为O(1)。这也就是说，栈操作所消耗的时间不依赖于栈中数据项的个数，因此操作时间很短。栈不需要比较和移动操作。

    队列也可以用数组来实现，不过这里有个问题，当数组下标满了后就不能再添加了，但是数组前面由于已经删除队列头的数据了，导致空。所以队列我们可以用循环数组来实现，见下面的代码：

[java] view
plain copy

1. public class RoundQueue {  
2.     private long[] a;  
3.     private int size;   //数组大小  
4.     private int nItems; //实际存储数量  
5.     private int front;  //头  
6.     private int rear;   //尾  
7.   
8.     public RoundQueue(int maxSize) {  
9.         this.size = maxSize;  
10.         a = new long[size];  
11.         front = 0;  
12.         rear = -1;  
13.         nItems = 0;  
14.     }  
15.       
16.     public void insert(long value) {  
17.         if(isFull()){  
18.             System.out.println("队列已满");  
19.             return;  
20.         }  
21.         rear = ++rear % size;  
22.         a[rear] = value; //尾指针满了就循环到0处,这句相当于下面注释内容        
23.         nItems++;  
24. /*      if(rear == size-1){ 
25.             rear = -1; 
26.         } 
27.         a[++rear] = value; 
28. */  
29.     }  
30.       
31.     public long remove() {  
32.         if(isEmpty()) {  
33.             System.out.println("队列为空！");  
34.             return 0;  
35.         }  
36.         nItems--;  
37.         front = front % size;  
38.         return a[front++];  
39.     }  
40.       
41.     public void display() {  
42.         if(isEmpty()) {  
43.             System.out.println("队列为空！");  
44.             return;  
45.         }  
46.         int item = front;  
47.         for(int i = 0; i < nItems; i++) {  
48.             System.out.print(a[item++ % size] + " ");  
49.         }  
50.         System.out.println("");  
51.     }  
52.       
53.     public long peek() {  
54.         if(isEmpty()) {  
55.             System.out.println("队列为空！");  
56.             return 0;  
57.         }  
58.         return a[front];  
59.     }  
60.       
61.     public boolean isFull() {  
62.         return (nItems == size);  
63.     }  
64.       
65.     public boolean isEmpty() {  
66.         return (nItems == 0);  
67.     }  
68.       
69.     public int size() {  
70.         return nItems;  
71.     }  
72. }  

    和栈一样，队列中插入数据项和删除数据项的时间复杂度均为O(1)。

    还有个优先级队列，优先级队列是比栈和队列更专用的数据结构。优先级队列与上面普通的队列相比，主要区别在于队列中的元素是有序的，关键字最小（或者最大）的数据项总在队头。数据项插入的时候会按照顺序插入到合适的位置以确保队列的顺序。优先级队列的内部实现可以用数组或者一种特别的树——堆来实现。堆可参考第8节内容。这里用数组实现优先级队列。

[java] view
plain copy

1. public class PriorityQueue {  
2.     private long[] a;  
3.     private int size;  
4.     private int nItems;//元素个数  
5.       
6.     public PriorityQueue(int maxSize) {  
7.         size = maxSize;  
8.         nItems = 0;  
9.         a = new long[size];  
10.     }  
11.       
12.     public void insert(long value) {  
13.         if(isFull()){  
14.             System.out.println("队列已满！");  
15.             return;  
16.         }  
17.         int j;  
18.         if(nItems == 0) { //空队列直接添加  
19.             a[nItems++] = value;  
20.         }  
21.         else{//将数组中的数字依照下标按照从大到小排列  
22.             for(j = nItems-1; j >= 0; j--) {  
23.                 if(value > a[j]){  
24.                     a[j+1] = a[j];  
25.                 }  
26.                 else {  
27.                     break;  
28.                 }  
29.             }  
30.             a[j+1] = value;  
31.             nItems++;  
32.         }  
33.     }  
34.       
35.     public long remove() {  
36.         if(isEmpty()){  
37.             System.out.println("队列为空！");  
38.             return 0;  
39.         }  
40.         return a[--nItems];  
41.     }  
42.       
43.     public long peekMin() {  
44.         return a[nItems-1];  
45.     }  
46.       
47.     public boolean isFull() {  
48.         return (nItems == size);  
49.     }  
50.       
51.     public boolean isEmpty() {  
52.         return (nItems == 0);  
53.     }  
54.       
55.     public int size() {  
56.         return nItems;  
57.     }  
58.   
59.     public void display() {  
60.         for(int i = nItems-1; i >= 0; i--) {  
61.             System.out.print(a[i] + " ");  
62.         }  
63.         System.out.println(" ");  
64.     }  
65. }  

    这里实现的优先级队列中，插入操作需要O(N)的时间，而删除操作则需要O(1)的时间。在第8节里将介绍堆来改进插入操作的时间。