数据结构(二):数组、栈、队列

一、数组

    数组是应用最广泛的一种数据结构,常常被植入到编程语言中,作为基本数据类型使用,因此,在一些教材中,数组并没有被当做一种数据结构单独拿出来讲解(其实数组就是一段连续的内存,即使在物理内存中不是连续的,在逻辑上肯定是连续的)。其实没必要在概念上做纠缠,数组可以当做学习数据结构的敲门砖,以此为基础,了解数据结构的基本概念以及构建方法

数据结构不仅是数据的容器,还要提供对数据的操作方法,比如检索、插入、删除、排序等

1、无序数组

下面我们建立一个类,对数组的检索、插入、删除、打印操作进行封装,简便起见,我们假设数组中没有重复值(实际上数组可以包含重复值)

无序数组的优点:插入快,如果知道下标,可以很快的存取

无序数组的缺点:查找慢,删除慢,大小固定。

public class Array {
     
      private String [] strArray;
      private int length = 0;       //数组元素个数
            
      //构造方法,传入数组最大长度
      public Array(int max){
             strArray = new String [max];
      }
     
      //检测数组是否包含某个元素,如果存在返回其下标,不存在则返回-1
      public int contains(String target){
             int index = -1;
             for(int i=0;i<length;i++){
                    if(strArray[i].equals(target)){
                           index = i;
                           break;
                    }
             }
             return index;
      }
     
      //插入
      public void insert(String elem) {
             strArray[length] = elem;
             length++;
      }
     
      //删除某个指定的元素值,删除成功则返回true,否则返回false
      public boolean delete(String target){
             int index = -1;
             if((index = contains(target)) !=-1){
                    for(int i=index;i<length-1;i++){
                           //删除元素之后的所有元素前移一位
                           strArray[i] =strArray[i+1]; 
                    }
                    length--;
                    return true;
             }else{
                    return false;
             }
      }
     
      //列出所有元素
      public void display(){
             for(int i=0;i<length;i++){
                    System.out.print(strArray[i]+"\t");
             }
      }
     
}

2、有序数组

    所谓的有序数组就是指数组中的元素是按一定规则排列的,其好处就是在根据元素值查找时可以是使用二分查找,查找效率要比无序数组高很多,在数据量很大时更加明显。当然缺点也显而易见,当插入一个元素时,首先要判断该元素应该插入的下标,然后对该下标之后的所有元素后移一位,才能进行插入,这无疑增加了很大的开销。

因此,有序数组适用于查找频繁,而插入、删除操作较少的情况

有序数组的封装类如下,为了方便,我们依然假设数组中是没有重复值的,并且数据是按照由小到大的顺序排列的 

有序数组最大的优势就是可以提高查找元素的效率,在上例中,find方法使用了二分查找法,该算法的示意图如下:


这个方法在一开始设置变量lowerBound和upperBound指向数组的第一个和最后一个非空数据项。通过设置这些变量可以确定查找的范围。然后再while循环中,当前的下标curIn被设置为这个范围的中间值

如果curIn就是我们要找的数据项,则返回下标,如果不是,就要分两种情况来考虑:如果curIn指向的数据项比我们要找的数据小,则证明该元素只可能在curIn和upperBound之间,即数组后一半中(数组是从小到大排列的),下轮要从后半段检索;如果curIn指向的数据项比我们要找的数据大,则证明该元素只可能在lowerBound和curIn之间,下一轮要在前半段中检索

按照上面的方法迭代检索,直到结束

有序数组的优点:查找效率高

有序数组的缺点:删除和插入慢,大小固定

public class OrderArray {
	private int[] intArray;
	private int length = 0; // 数组元素个数

	// 构造方法,传入数组最大长度
	public OrderArray(int max) {
		intArray = new int[max];
	}

	// 用二分查找法定位某个元素,如果存在返回其下标,不存在则返回-1
	public int find(int target) {
		int lowerBound = 0; // 搜索段最小元素的小标
		int upperBound = length - 1; // 搜索段最大元素的下标
		int curIn; // 当前检测元素的下标

		if (upperBound < 0) { // 如果数组为空,直接返回-1
			return -1;
		}

		while (true) {
			curIn = (lowerBound + upperBound) / 2;

			if (target == intArray[curIn]) {
				return curIn;
			} else if (curIn == lowerBound) { // 在当前下标与搜索段的最小下标重合时,代表搜索段中只包含1个或2个元素
				// 既然走到该分支,证明上一个if分支不满足,即目标元素不等于低位元素
				if (target == intArray[upperBound]) { // 等于高位元素,返回
					return upperBound;
				} else { // 高位元素也不等于目标元素,证明数组中没有该元素,搜索结束
					return -1;
				}
			} else {// 搜索段中的元素至少有三个,且当前元素不等于目标元素
				if (intArray[curIn] < target) {
					// 如果当前元素小于目标元素,则将下一个搜索段的最小下标置为当前元素的下标
					lowerBound = curIn;
				} else {
					// 如果当前元素大于目标元素,则将下一个搜索段的最大下标置为当前元素的下标
					upperBound = curIn;
				}
			}
		}
	}

	// 插入
	public void insert(int elem) {
		int location = 0;

		// 判断应插入位置的下标
		for (; location < length; location++) {
			if (intArray[location] > elem)
				break;
		}
		// System.out.println(location);
		// 将插入下标之后的所有元素后移一位
		for (int i = length; i > location; i--) {
			intArray[i] = intArray[i - 1];
		}

		// 插入元素
		intArray[location] = elem;

		length++;
	}

	// 删除某个指定的元素值,删除成功则返回true,否则返回false
	public boolean delete(int target) {
		int index = -1;
		if ((index = find(target)) != -1) {
			for (int i = index; i < length - 1; i++) {
				// 删除元素之后的所有元素前移一位
				intArray[i] = intArray[i + 1];
			}
			length--;
			return true;
		} else {
			return false;
		}
	}

	// 列出所有元素
	public void display() {
		for (int i = 0; i < length; i++) {
			System.out.print(intArray[i] + "\t");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		OrderArray orderArray = new OrderArray(4);

		orderArray.insert(3);
		orderArray.insert(4);
		orderArray.insert(6);
		orderArray.insert(8);

		int i = orderArray.find(8);
		System.out.println("在队列中的位置是" + i);
	}
}

二、栈

    数组、链表、树等数据结构适用于存储数据库应用中的数据记录,它们常常用于记录那些现实世界的对象和活动的数据,便与数据的访问:插入、删除和查找特定数据项

而栈和队列更多的是作为程序员的工具来使用。他们主要作为构思算法的辅助工具,而不是完全的数据存储工具。这些数据结构的生命周期比那些数据库类型的结构要短很多。在程序操作执行期间它们才被创建,通常它们去执行某项特殊的任务,当任务完成后就被销毁

栈和队列的访问是受限制的,即在特定时刻只有一个数据项可以被读取或删除

栈和队列是比数组和其他数据结构更加抽象的结构,是站在更高的层面对数据进行组织和维护

栈的主要机制可用数组来实现,也可以用链表来实现。优先级队列的内部实现可以用数组或者一种特别的树——堆来实现。

 

先来了解栈的概念和实例,然后分别深入理解队列和优先级队列

栈只允许访问一个数据项:即最后插入的数据。移除这个数据项后才能访问倒数第二个插入的数据项。它是一种“后进先出”的数据结构。

栈最基本的操作是出栈(Pop)、入栈(Push),还有其他扩展操作,如查看栈顶元素,判断栈是否为空、是否已满,读取栈的大小等

下面我们就用数组来写一个栈操作的封装类

public class Stack {
      private int size;                 //栈的大小
      private int top;                  //栈顶元素的下标
      private int [] stackArray;   //栈的容器
     
      //构造函数
      public Stack(int size){
             stackArray = new int [size];
             top = -1; //初始化栈的时候,栈内无元素,栈顶下标设为-1
             this.size = size;
      }
     
      //入栈,同时,栈顶元素的下标加一
      public void push(int elem){
             stackArray[++top] = elem; //插入栈顶
      }
     
      //出栈,删除栈顶元素,同时,栈顶元素的下标减一
      public int pop(){
             return stackArray[top--];
      }
     
      //查看栈顶元素,但不删除
      public int peek(){
             return stackArray[top];
      }
     
      //判空
      public boolean isEmpty(){
             return (top == -1);
      }
     
      //判满
      public boolean isFull(){
             return (top == size-1);
      }
     
}

上例中,没有对可能的异常进行处理,需要由编程人员保证程序的正确性,比如,才出栈前需要应该保证栈中有元素,在入栈前应保证栈没有满

                                                                            入栈操作示意图


 

                                                                                                           出栈操作示意图

 

栈通常用于解析某种类型的文本串。通常,文本串是用计算机语言写的代码行,而解析它们的程序就是编译器

下面我们来用栈来实现一个经典的应用:分隔符匹配。想一下在Eclipse编程时,如果我们写的代码中如果多了一个“{”,后者少了一个“}”,或者括号的顺序错乱,都会报错。接下来我们就用栈来模拟这种分隔符匹配

分隔符匹配程序从字符串中不断地读取程序,每次读取一个字符,若发现它是左分隔符({、[、(),将它压入栈中。当读到一个右分隔符时()、]、}),弹出栈顶元素,并且查看它是否和该右分隔符匹配。如果它们不匹配,则程序报错。如果到最后一直存在着没有被匹配的分隔符,程序也报错

我们来看下面这个正确的字符串,在栈中的变化过程:

a{b(c[d]e)f}

 

所读字符                  栈中内容

      a                                 空

      {                                  {

      b                                 {

      (                                  {(

      c                                 {(

      [                                  {([

      d                                 {([

      ]                                  {(

      e                                 {(

      )                                  {

      f                                  {

      }                                  空

最后出现的左分隔符需要被最先匹配,这符合栈“后进先出”的规则

在本例中,要处理的是字符,所以需要对上面的Stack类进行修改,需要将存放元素的数组改为char类型,并把相关方法的参数类型改为char类型,其余不变

public class Stack {
      private int size;                 //栈的大小
      private int top;                  //栈顶元素的下标
      private char [] stackArray;       //栈的容器
     
      //构造函数
      public Stack(int size){
             stackArray = new char [size];
             top = -1; //初始化栈的时候,栈内无元素,栈顶下标设为-1
             this.size = size;
      }
     
      //入栈,同时,栈顶元素的下标加一
      public void push(char elem){
             stackArray[++top] = elem; //插入栈顶
      }
     
      //出栈,删除栈顶元素,同时,栈顶元素的下标减一
      public char pop(){
             return stackArray[top--];
      }
     
      //查看栈顶元素,但不删除
      public char peek(){
             return stackArray[top];
      }
     
      //判空
      public boolean isEmpty(){
             return (top == -1);
      }
     
      //判满
      public boolean isFull(){
             return (top == size-1);
      }
     
}
然后写一个类来封装分隔符匹配的操作:
public class BrecketChecker {
     
      private String input;  //存储待检查的字符串
     
      //构造方法,接受待检查的字符串
      public BrecketChecker(String in){
             this.input = in;
      }
     
      //检查分隔符匹配的方法
      public void check(){
             int strLength = input.length();
             Stack stack = new Stack(strLength);
            
             for(int i=0;i<strLength;i++){
                   
                    char ch =input.charAt(i);  //一次获取串中的单个字符
                   
                    switch(ch){
                           case '{' :
                           case '[' :
                           case '(' :
                                   //如果为左分隔符,压入栈
                                  stack.push(ch);
                                  break;
                           case '}' :
                           case ']' :
                           case ')' :
                                  //如果为右分隔符,与栈顶元素进行匹配
                                  if(!stack.isEmpty()){
                                         char ch = stack.pop();
                                        
                                         if((ch== '{' && chx != '}')||
                                            (ch == '(' && chx != ')')||
                                            (ch == '[' && chx != ']')
                                         ){
                                                System.out.println("匹配出错!字符:"+ch+",下标:"+i);
                                         }
                                  }else{
                                         System.out.println("匹配出错!字符:"+ch+",下标:"+i);
                                  }
                                 
                           default :
                                  break;
                    }
                   
             }
            
             if(!stack.isEmpty()){
                    //匹配结束时如果栈中还有元素,证明右分隔符缺失
                    System.out.println("有括号没有关闭!");
             }
      }
     
}
测试类
public static void main(String[] args) {
            
             System.out.println("输入需要检测的字符串:");
             String str = getString();
             BrecketChecker checker = newBrecketChecker(str);
             checker.check();
      }
     
      public static String getString(){
             String str = "";
             try{
                    InputStreamReader reader =new InputStreamReader(System.in);
                    BufferedReader bReader = new BufferedReader(reader);
                    str = bReader.readLine();
             }catch(IOException e){
                    e.printStackTrace();
             }
             return str;
      }
 

三、队列

    栈是“后进先出”(LIFO,Last InFirst Out)的数据结构,与之相反,队列是“先进先出”(FIFO,First InFirst Out)的数据结构

队列的作用就像售票口前的人们站成的一排一样:第一个进入队列的人将最先买到票,最后排队的人最后才能买到票

在计算机操作系统或网路中,有各种队列在安静地工作着。打印作业在打印队列中等待打印。当敲击键盘时,也有一个存储键盘键入内容的队列,如果我们敲击了一个键,而计算机又暂时在做其他事情,敲击的内容不会丢失,它会排在队列中等待,直到计算机有时间来读取它,利用队列保证了键入内容在处理时其顺序不会改变

栈的插入和删除数据项的命名方法很标准,成为push和pop,队列的方法至今也没有一个标准化的方法,插入可以称作put、add或enque等,删除可以叫作delete、get、remove或deque等

下面我们依然使用数组作为底层容器来实现一个队列的操作封装,与栈不同的是,队列的数据项并不都是从数组的第一个下标开始,因为数据项在数组的下标越小代表其在队列中的排列越靠前,移除数据项只能从队头移除,然后队头指针后移,这样数组的前几个位置就会空出来如下图所示:


这与我们的直观感觉相反,因为我们排队买票时,队列总是向前移动,当前面的人买完票离开后,其他人都向前移动,而在我们的设计中,队列并没有向前移动,因为那样做会使效率大打折扣,我们只需要使用指针来标记队头和队尾,队列发生变化时,移动指针就可以,而数据项的位置不变

但是,这样的设计还存在着一个问题,随着队头元素不断地移除,数组前面空出的位置会越来越多,当队尾指针移到最后的位置时,即使队列没有满,我们也不能再插入新的数据项了


解决这种缺点的方法是环绕式处理,即让队尾指针回到数组的第一个位置:


这就是循环队列(也成为缓冲环)。虽然在存储上是线形的,但是在逻辑上它是一个首尾衔接的环形


public class Queue {
     
      private int [] queArray;
      private int maxSize;
      public int front;   //存储队头元素的下标
      public int rear;    //存储队尾元素的下标
      private int length; //队列长度
     
      //构造方法,初始化队列
      public Queue(int maxSize){
             this.maxSize = maxSize;
             queArray = new int [maxSize];
             front = 0;
             rear = -1;
             length = 0;
      }
     
      //插入
      public void insert(int elem) throws Exception{
             if(isFull()){
                    throw new Exception("队列已满,不能进行插入操作!");
             }
             //如果队尾指针已到达数组的末端,插入到数组的第一个位置
             if(rear == maxSize-1){
                    rear = -1;
             }
             queArray[++rear] = elem;
             length++;
      }
     
      //移除
      public int remove() throws Exception{
             if(isEmpty()){
                    throw new Exception("队列为空,不能进行移除操作!");
             }
             int elem = queArray[front++];
             //如果队头指针已到达数组末端,则移到数组第一个位置
             if(front == maxSize){
                    front = 0;
             }
             length--;
             returnelem;
      }
     
      //查看队头元素
      public int peek() throws Exception{
             if(isEmpty()){
                    throw new Exception("队列内没有元素!");
             }
             return queArray[front];
      }
     
      //获取队列长度
      public int size(){
             return length;
      }
     
      //判空
      public boolean isEmpty(){
             return (length == 0);
      }
     
      //判满
      public boolean isFull(){
             return (length == maxSize);
      }
     
}

还有一种称为双端队列的数据结构,队列的每一端都可以进行插入和移除操作。

其实双端队列是队列和栈的综合体。如果限制双端队列的一段只能插入,而另一端只能移除,就变成了平常意义上的队列;如果限制双端队列只能在一端进行插入和移除,就变成了栈

优先级队列

像普通队列一样,优先级队列有一个队头和一个队尾,并且也是从队头移除数据,从队尾插入数据,不同的是,在优先级队列中,数据项按关键字的值排序,数据项插入的时候会按照顺序插入到合适的位置

除了可以快速访问优先级最高的数据项,优先级队列还应该可以实现相当快的插入,因此,优先级队列通常使用一种称为堆的数据结构来实现。在下例中,简便起见,我们仍然使用数组来实现

在数据项个数比较少,或不太关心速度的情况下,用数组实现优先级队列还可以满足要求,如果数据项很多,或对速度要求很高,采用堆是更好的选择

优先级队列的实现跟上面普通队列的实现有很大的区别。

优先级队列的插入本来就需要移动元素来找到应该插入的位置,所以循环队列那种不需要移动元素的优势就不太明显了。在下例中,没有设置队头和队尾指针,而是使数组的第一个元素永远是队尾,数组的最后一个元素永远是队头,为什么不是相反的呢?因为队头有移除操作,所以将队头放在数组的末端,便于移除,如果放在首段,每次移除队头都需要将队列向前移动

                                                                                  插入元素示意图

 

                                                                                             

                                                                                                移除元素示意图


在下例中,我们设置了一个基准点,认为元素到里基准点的距离越近则优先级越高,如设置的基准点为2,3到2的距离就是|3-2|=1,而-1到2的距离是|-1-2|=3,所以2的优先级就比-1要高

public class PriorityQueue {
     
      private int [] queArray;
      private int maxSize;
      private int length; //队列长度
      private int referencePoint;  //基准点
     
      //构造方法,初始化队列
      public PriorityQueue(int maxSize,intreferencePoint){
             this.maxSize= maxSize;
             this.referencePoint =referencePoint;
             queArray = new int [maxSize];
             length = 0;
      }
     
      //插入
      public void insert(int elem) throws Exception{
             if(isFull()){
                    throw new Exception("队列已满,不能进行插入操作!");
             }
            
             //如果队列为空,插入到数组的第一个位置
             if(length == 0){
                    queArray[length++] = elem;
             }else{
                    int i;
                    for(i=length;i>0;i--){
                          
                           int dis =Math.abs(elem-referencePoint);  //待插入元素的距离
                           int curDis =Math.abs(queArray[i-1]-referencePoint); //当前元素的距离
                          
                           //将比插入元素优先级高的元素后移一位
                           if(dis>= curDis){
                                  queArray[i] =queArray[i-1];
                           }else{
                                  break;
                           }
                    }
                    queArray[i] = elem;
                    length++;
             }
      }
     
      //移除
      public int remove() throws Exception{
             if(isEmpty()){
                    throw new Exception("队列为空,不能进行移除操作!");
             }
             int elem = queArray[--length];
             return elem;
      }
     
      //查看队头元素
      public int peek() throws Exception{
             if(isEmpty()){
                    throw new Exception("队列内没有元素!");
             }
             return queArray[length-1];
      }
     
      //返回队列长度
      public int size(){
             return length;
      }
     
      //判空
      public boolean isEmpty(){
             return (length == 0);
      }
     
      //判满
      public boolean isFull(){
             return (length == maxSize);
      }
     
}
转载:https://blog.csdn.net/column/details/datastructureinjava.html
版权声明:本文为u014231646原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/u014231646/article/details/80306791

智能推荐

JetBrains 系列开发工具,如何配置 `SCSS` `File Watcher` ,相关输出配置参数详解:webStorm phpStorm IDEA

JetBrains 系列开发工具,如何配置 SCSS File Watcher ,相关输出配置参数详解:webStorm phpStorm IDEA 前言 你目前已经了解了如何使用 SCSS 进行开发,了解了该文章的内容:『 SCSS 日常用法 』 在 JetBrains 系列开发工具中通过 FileWatcher 进行编译的 SCSS 文件都是通过 sass 这个程序进行的。『 如何添加 Fil...

C语言小函数—二进制与十六进制

测试如下 “` int main() { long int num = 15; } “`...

仿微博或微信的文章多图显示(自定义MultiImageView)

按照一般的规矩,先上张图来供大伙看看 如果大致是大伙们需要实现的功能,不烦一观 自定义MultiImageView 工具类 具体使用 app.gradle中添加依赖 implementation 'com.github.bumptech.glide:glide:4.8.0' AndroidManifest.xml中配置联网权限 <uses-permission android:name=&q...

经典进程同步和互斥问题

经典进程同步与互斥问题 前言 一、生产者-消费者问题 1.问题描述 2.问题分析 3.代码 二、读者-写者问题 1.问题描述&&分析 2.代码 三、哲学家进餐问题 1.问题描述&&分析 2.代码 四、理发师问题 1.问题描述&&分析 2.代码 前言 在多道程序设计环境中,进程同步是一个非常重要的问题,下面讨论几个经典的进程同步问题。 一、生产者-消费...

java设计模式——ThreadLocal线程单例

1、定义一个ThreadLocal线程单例,代码如下: 2、定义一个多线程类,代码如下: 3、定义一个测试类,代码如下: 4、输出结果,如下图:...

猜你喜欢

【tensorflow】线性模型实战

线性模型:y = 1.477 * x + 0.089   1. 采样数据 采样噪声eps在均值0,方差0.01的高斯分布中,而后在均匀分布U(0,1)中,区间[-10,10]进行n=100次随机采样:   2. 计算误差 循环计算每个点的预测值与真是值之间差的平方并累加,从而获得训练集上的均芳误差损失值。   3. 计算梯度   4. 梯度更新 对权重w和偏...

常见损失函数和评价指标总结(附公式&代码)

网上看到一篇很实用的帖子关于常见损失函数和评价指标,收藏下来 本文转载于https://zhuanlan.zhihu.com/p/91511706 ------------------------------------------------------------------------------------------------------------------------------...

为什么 4G/5G 的直播延时依然很高

通信技术的发展促进了视频点播和直播业务的兴起,4G 和 5G 网络技术的进步也使得流媒体技术变得越来越重要,但是网络技术并不能解决流媒体直播的高延迟问题。 本文不会介绍网络对直播业务的影响,而是会分析直播中常见的现象 — 主播和观众之间能够感觉到的明显网络延迟。除了业务上要求的延迟直播之外,有哪些因素会导致视频直播的延迟这么高呢? live-streaming  图 1 - ...

springboot 过滤器Filter vs 拦截器Interceptor 详解

1 前言       最近接触到了过滤器和拦截器,网上查了查资料,这里记录一下,这篇文章就来仔细剖析下过滤器和拦截器的区别与联系。 2 拦截器与过滤器之间的区别 从上面对拦截器与过滤器的描述来看,它俩是非常相似的,都能对客户端发来的请求进行处理,它们的区别如下: 作用域不同 过滤器依赖于servlet容器,只能在 servlet容器,web环境下使用 拦截器依赖于sp...

IDEA环境--JavaWeb项目【分页功能实现】

参考链接:https://www.jianshu.com/p/d108d0cd9acf 1、前言 最近在写一些项目,遇到要使用分页功能的地方,就简单的学习了一下,在此总结一下具体实现的过程以及遇到的问题。 分页功能:当我们写一下web项目时会遇到一个页面要显示很多数据,一下子都显示出来效率会很低,也不美观。这就要用到分页,其作用也就是将数据分割成多个页面来进行显示。 2、项目介绍 这只是一个简单的...