文档章节

数据结构与算法02 之栈与队列

乐在克里特
 乐在克里特
发布于 2017/02/23 14:57
字数 1028
阅读 2
收藏 0

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

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

 

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

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

 

  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节内容。这里用数组实现优先级队列。

 

  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节里将介绍堆来改进插入操作的时间。

 

http://blog.csdn.net/eson_15/article/details/51126638

© 著作权归作者所有

共有 人打赏支持
乐在克里特
粉丝 16
博文 268
码字总数 394729
作品 0
杭州
程序员
私信 提问
用js来实现那些数据结构及算法—目录

  首先,有一点要声明,下面所有文章的所有内容的代码,都不是我一个人独立完成的,它们来自于一本叫做《学习JavaScript数据结构和算法》(第二版),人民邮电出版社出版的这本书。github代...

zaking
2018/05/10
0
0
LeetCode算法题-Implement Queue Using Stacks(Java实现)

这是悦乐书的第195次更新,第201篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第57题(顺位题号是232)。使用栈实现队列的以下操作。 push(x) - 将元素x推送到队列的后面。...

小川94
2018/12/08
0
0
LeetCode算法题-Implement Stack Using Queues

这是悦乐书的第193次更新,第198篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第54题(顺位题号是225)。使用队列实现栈的以下操作: push(x) - 将元素x推入栈。 pop() ...

小川94
2018/12/06
0
0
LeetCode算法题-Min Stack(Java实现)

这是悦乐书的第177次更新,第179篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第36题(顺位题号是155)。设计一个支持push,pop,top和在恒定时间内检索最小元素的堆栈。 pu...

小川94
2018/11/20
0
0
数据结构课程主页-2016级

  新学期,再度起程!   翻转的数据结构课程再度迎来新的一批同学。   前两年,资源建设基本完备,课堂方案逐渐完善,同学们对新型的学习方式设计给予了肯定(参见2014级问卷调查和201...

sxhelijian
2017/08/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

如何在React工程中使用JavaScript Barcode SDK创建Web条形码应用

基于WebAssembly构建的Dynamsoft JavaScript Barcode SDK让Web开发者能够创建适用于浏览器的高性能条码应用。这篇文章分享下如何使用React快速创建一个简单的Web条形码扫描应用。 下载 Node...

yushulx
29分钟前
1
0
java lambda笔记

c#中的lambda表达式简直不要太爽,但是感觉java的lambda和c#比有待继续提高。 先搞个筛选List集合的东西,我们先搞个集合玩玩。 List<Person> person = new ArrayList<Person>();Person p...

朝如青丝暮成雪
29分钟前
0
0
最严新规发布 网络短视频平台该如何降低违规风险?

1月9日中国网络视听节目服务协会对外正式发布了多项规范,对版权视频保护及违规内容,都进行了更加详细的标准制定,整体政策更加严格。 规范规定,网络短视频平台应当履行版权保护责任,不得...

阿里云官方博客
37分钟前
1
0
深入解读阿里云数据库POLARDB核心功能物理复制技术

日志是数据库的重要组成部份,按顺序以增量的方式记录了数据库上所有的操作,日志模块的设计对于数据库的可靠性、稳定性和性能都非常重要。 可靠性方面,在有一个数据文件的基础全量备份后,...

zhaowei121
43分钟前
1
0
CentOS 非root 用户 使用sudo 命令免密码

1. 使用su/su - 命令进入root权限下; 2. 给/etc/sudoers文件添加写权限 chmod u+w /etc/sudoers 3.找到“root ALL=(ALL) ALL ”,在后面添加:"dba ALL=(ALL) NOPASSWD: ALL" 4.保存退出,并......

驛路梨花醉美
43分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部