文档章节

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

乐在克里特
 乐在克里特
发布于 2017/02/23 14:57
字数 1028
阅读 1
收藏 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

© 著作权归作者所有

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

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

zaking
05/10
0
0
数据结构课程主页-2016级

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

sxhelijian
2017/08/30
0
0
Java数据结构与算法(第四章栈和队列)

本章涉及的三种数据存储类型:栈、队列和优先级队列。 不同类型的结构 程序员的工具 数组是已经介绍过的数据存储结构,和其他结构(链表、树等等)一样,都适用于数据应用中作数据记录。 然而...

小风89
2015/10/24
250
0
零基础自学数据挖掘工程师必知的四大阶段 第三阶段是重点

  本文介绍的学习路线使用的是当下主流数据分析挖掘编程语言Python来掌握数据挖掘的实际工作能力与认识水平。按照 1)基础理论→2)编程能力→3)挖掘应用→4)大数据实践 的学习流程来设置...

蓝胖子讲大数据
2017/11/07
0
0
《编程之美》-取队列中的最大值(读书分享)

题目:设计一种数据结构和算法,让取队列最大值的操作的事件复杂度降到最低。对队列操作后依然能够简便取出最大值。 对于栈来讲,Push和Pop均是在栈顶完成的,所以很容维护最大值,而且他的时...

吟啸_徐行
2013/03/15
0
4

没有更多内容

加载失败,请刷新页面

加载更多

sed命令

10月17日任务 9.4/9.5 sed 1.sed(上)(下) 1.sed 匹配功能 #sed -n ‘/root/’ p test.txt 将带有root的内容打印出来 同时支持 . * 还有 + 不过需要脱译,或者在前面选项加r。 支持{ } 支...

hhpuppy
33分钟前
1
0
day120-20181018-英语流利阅读-待学习

千禧一代注意了:一大波公司正向你的钱包袭来 Daniel 2018-10-18 1.今日导读 这几年,你有没有发现,不管是在微信公众号还是在抖音,有越来越多的商家和品牌开始玩起了网络用语和表情包,从卖...

飞鱼说编程
41分钟前
1
0
IOasd

能够使用FileUtils常用方法操作文件 字符流体系介绍 : 在 IO 开发中, 我们传输最频繁的数据为字符, 而以字节的方式来传输字符数据会使程序员丧失对数据内容的判断.因为程序员只认识字符, 不认...

码农屌丝
今天
0
0
创建第一个react项目

sudo npm i -g create-react-app@1.5.2 create-react-app react-app cd react-apprm -rf package-lock.jsonrm -rf node_modules #主要是为了避免报错npm installnpm start......

lilugirl
今天
3
0
在浏览器中进行深度学习:TensorFlow.js (八)生成对抗网络 (GAN)

Generative Adversarial Network 是深度学习中非常有趣的一种方法。GAN最早源自Ian Goodfellow的这篇论文。LeCun对GAN给出了极高的评价: “There are many interesting recent development...

naughty
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部