数据结构之栈和队列

xiangzhihong8 发布时间：2016-06-12 21:00:21 ，浏览量：0

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

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

 
   [java] 
   view plain
    copy 
    
   
 public class ArrayStack {  
     private long[] a;  
     private int size; //栈数组的大小  
     private int top; //栈顶  
   
     public ArrayStack(int maxSize) {  
         this.size = maxSize;  
         this.a = new long[size];  
         this.top = -1; //表示空栈  
     }  
       
     public void push(long value) {//入栈  
         if(isFull()) {  
             System.out.println("栈已满！");  
             return;  
         }  
         a[++top] = value;  
     }  
       
     public long peek() {//返回栈顶内容，但不删除  
         if(isEmpty()) {  
             System.out.println("栈中没有数据");  
             return 0;  
         }  
         return a[top];  
     }  
       
     public long pop() { //弹出栈顶内容，删除  
         if(isEmpty()) {  
             System.out.println("栈中没有数据！");  
             return 0;  
         }  
         return a[top--];          
     }  
       
     public int size() {  
         return top + 1;  
     }  
       
     public boolean isEmpty() {  
         return (top == -1);  
     }  
       
     public boolean isFull() {  
         return (top == size -1);  
     }  
       
     public void display() {  
         for(int i = top; i >= 0; i--) {  
             System.out.print(a[i] + " ");  
         }  
         System.out.println("");  
     }  
 }  

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

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

 
   [java] 
   view plain
    copy 
    
   
 public class RoundQueue {  
     private long[] a;  
     private int size;   //数组大小  
     private int nItems; //实际存储数量  
     private int front;  //头  
     private int rear;   //尾  
   
     public RoundQueue(int maxSize) {  
         this.size = maxSize;  
         a = new long[size];  
         front = 0;  
         rear = -1;  
         nItems = 0;  
     }  
       
     public void insert(long value) {  
         if(isFull()){  
             System.out.println("队列已满");  
             return;  
         }  
         rear = ++rear % size;  
         a[rear] = value; //尾指针满了就循环到0处,这句相当于下面注释内容        
         nItems++;  
 /*      if(rear == size-1){ 
             rear = -1; 
         } 
         a[++rear] = value; 
 */  
     }  
       
     public long remove() {  
         if(isEmpty()) {  
             System.out.println("队列为空！");  
             return 0;  
         }  
         nItems--;  
         front = front % size;  
         return a[front++];  
     }  
       
     public void display() {  
         if(isEmpty()) {  
             System.out.println("队列为空！");  
             return;  
         }  
         int item = front;  
         for(int i = 0; i = 0; j--) {  
                 if(value > a[j]){  
                     a[j+1] = a[j];  
                 }  
                 else {  
                     break;  
                 }  
             }  
             a[j+1] = value;  
             nItems++;  
         }  
     }  
       
     public long remove() {  
         if(isEmpty()){  
             System.out.println("队列为空！");  
             return 0;  
         }  
         return a[--nItems];  
     }  
       
     public long peekMin() {  
         return a[nItems-1];  
     }  
       
     public boolean isFull() {  
         return (nItems == size);  
     }  
       
     public boolean isEmpty() {  
         return (nItems == 0);  
     }  
       
     public int size() {  
         return nItems;  
     }  
   
     public void display() {  
         for(int i = nItems-1; i >= 0; i--) {  
             System.out.print(a[i] + " ");  
         }  
         System.out.println(" ");  
     }  
 }  

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

关注

打赏

1482932726

查看更多评论

数据结构之栈和队列

最近更新

热门博客

[ 申请 ]友情链接：