专栏首页向治洪数据结构之栈和队列

数据结构之栈和队列

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

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

 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)。这也就是说,栈操作所消耗的时间不依赖于栈中数据项的个数,因此操作时间很短。栈不需要比较和移动操作。

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

 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 < nItems; i++) {  
             System.out.print(a[item++ % size] + " ");  
         }  
         System.out.println("");  
     }  
  
  public long peek() {  
  if(isEmpty()) {  
             System.out.println("队列为空!");  
  return 0;  
         }  
  return a[front];  
     }  
  
  public boolean isFull() {  
  return (nItems == size);  
     }  
  
  public boolean isEmpty() {  
  return (nItems == 0);  
     }  
  
  public int size() {  
  return nItems;  
     }  
 }  

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

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

 public class PriorityQueue {  
  private long[] a;  
  private int size;  
  private int nItems;//元素个数 
  
  public PriorityQueue(int maxSize) {  
         size = maxSize;  
         nItems = 0;  
         a = new long[size];  
     }  
  
  public void insert(long value) {  
  if(isFull()){  
             System.out.println("队列已满!");  
  return;  
         }  
  int j;  
  if(nItems == 0) { //空队列直接添加 
             a[nItems++] = value;  
         }  
  else{//将数组中的数字依照下标按照从大到小排列 
  for(j = nItems-1; j >= 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节里将介绍堆来改进插入操作的时间。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构之队列

    概述 在java5中新增加了java.util.Queue接口,用以支持队列的常见操作。Queue接口与List、Set同一级别,都是继承了Collection...

    xiangzhihong
  • Android系统服务之WindowManager整理

    概述 WindowManager是Android中一个重要的服务(Service )。WindowManager Service 是全局的,是唯一的。它将用户的...

    xiangzhihong
  • Android WindowManager详解

    概述 WindowManager是Android中一个重要的服务(Service )。WindowManager Service 是全局的,是唯一的。它将用户的...

    xiangzhihong
  • 数据结构之栈和队列

     栈或者队列是经典的数据结构,虽然平时都在用,但是都是别人封装好的集合,我们不用手写了,但是这些内功,作为开发人员来说是必须要掌握的。

    Kevin_Zhang
  • 数据结构之队列

    概述 在java5中新增加了java.util.Queue接口,用以支持队列的常见操作。Queue接口与List、Set同一级别,都是继承了Collection...

    xiangzhihong
  • 如果让你手写个栈和队列,你还会写吗?

    昨天跟一个CSDN上的朋友聊天,他说现在如果让他自己手写一个栈或者队列,估计都要写蛮久的,平时虽然都在用,但是都是别人封装好的集合。

    Java团长
  • Java 集合深入理解(6):AbstractList

    今天心情比天蓝,来学学 AbstractList 吧! ? 什么是 AbstractList ? AbstractList 继承自 AbstractCollec...

    张拭心 shixinzhang
  • AbstractList源码解析1 实现的方法2 两种内部迭代器3 两种内部类3 SubList 源码分析4 RandomAccessSubList 源码:AbstractList 作为 Lis

    它实现了 List 的一些位置相关操作(比如 get,set,add,remove),是第一个实现随机访问方法的集合类,但不支持添加和替换

    JavaEdge
  • JDK源码分析-ArrayList分析

    花了两个晚上的时间研究了一下ArrayList的源码, ArrayList 继承自AbstractList 并且实现了List, RandomAccess,...

    汤高
  • 面试官,求求你不要问我这么简单但又刁难的算法题了

    版权声明:本文为苦逼的码农原创。未经同意禁止任何形式转载,特别是那些复制粘贴到别的平台的,否则,必定追究。欢迎大家多多转发,谢谢。

    帅地

扫码关注云+社区

领取腾讯云代金券