首页 > 其他分享 >八大常见的数据结构(一)数组、链表、栈、队列

八大常见的数据结构(一)数组、链表、栈、队列

时间:2023-05-18 12:44:07浏览次数:56  
标签:arr 删除 队列 元素 链表 myStack 数据结构 public

1、数组

  • 数组是用于储存有限个相同类型数据的集合。
  • 数组中的各元素的存储是有先后顺序的,它们在内存中按照这个先后顺序连续存放在一起。
  • 可通过数组名和下标进行数据的访问和更新。下标从0开始。

2、链表

  • 链表是一种物理存储单元上非连续、非顺序的存储结构
  • 链表相较于数组,除了数据域,还增加了指针域。链表中每一个节点都包含此节点的数据和指向下一节点地址的指针。
  • 对节点进行增加和删除时,只需要对涉及到的节点的指针地址进行修改,而无需变动其它的节点。
  数组 链表
内存地址 连续 不连续
数据长度 固定 可以动态变化
查询效率 高,随机访问 低,顺序访问
增删效率 低,需要移动被修改元素之后的元素 高,只需要修改涉及到的节点的指针

3、栈

  • 限定仅在栈顶进行插入和删除操作的线性表。插入一般称为进栈(PUSH),删除则称为退栈(POP)。
  • 后进先出
  • 栈可以用来在函数调用的时候存储断点,做递归时要用到栈。

java中,对栈的操作:

  • 向栈中存放元素:stack.push();
  • 获取栈顶元素:stack.peek();
  • 删除栈顶元素:stack.pop();

栈分顺序栈和链式栈,顺序栈的实现如下:

 1 public class MyStack {
 2     public int[] arr;// 开辟一个栈的空间
 3     public int arrSize;// 栈实际用的长度
 4 
 5     public MyStack() {
 6         this.arr = new int[10];// 设置栈的空间为10个元素的空间
 7     }
 8 
 9     // 栈中存放元素要判断栈是否为满
10     public boolean isFull() {
11         // 数据个数=长度
12         if (this.arrSize == this.arr.length) {
13             return true;
14         }
15         return false;
16     }
17 
18     public void push(int item) {
19         // 如果栈满,扩容
20         if (isFull()) {
21             this.arr = Arrays.copyOf(this.arr, 3 * arr.length);
22         }
23         // 没满,存放到数组的最后位置
24         this.arr[this.arrSize] = item;
25         this.arrSize++;
26     }
27 
28     // pop删除栈顶元素要判断栈是否为空
29     public boolean empty() {
30         // 数据个数为空时
31         return this.arrSize == 0;
32     }
33 
34     public int pop() throws RuntimeException {
35         if (empty()) {
36             throw new RuntimeException("栈空");
37         }
38         int val = this.arr[this.arrSize - 1];
39         this.arrSize--;
40         return val;
41     }
42 
43     // 获取栈顶元素
44     public int peek() {
45         if (empty()) {
46             throw new RuntimeException("栈空");
47         }
48         return this.arr[this.arrSize - 1];
49     }
50 
51     public static void main(String[] args) {
52         // TODO Auto-generated method stub
53         MyStack myStack = new MyStack();
54         System.out.println(myStack.arrSize);// 栈实际长度
55         System.out.println(myStack.arr.length);// 数组长度
56         myStack.push(1);
57         myStack.push(2);
58         myStack.push(3);
59         System.out.println(myStack.peek());// 获取栈顶元素 但是不删除 结果为3
60         System.out.println(myStack.pop());// 弹出栈顶元素 删除 结果为3
61         System.out.println(myStack.peek());// 获取栈顶元素 但是不删除 结果为2
62         System.out.println(myStack.empty());// 结果为false
63         System.out.println(myStack.pop());// 2
64         System.out.println(myStack.pop());// 1
65         System.out.println(myStack.pop());// 证明为空报异常
66     }
67 
68 }

4、队列

  • 一个先入先出(FIFO)的数据结构
  • 只允许在队尾插入数据,在队头删除数据

 4.1顺序队列

  • 静态分配或动态申请一片连续的存储空间,并设置两个指针进行管理。一个是队头指针front,它指向队头元素;另一个是队尾指针rear,它指向下一个入队元素的存储位置
  • 每次在队尾插入一个元素是,rear增1;每次在队头删除一个元素时,front增1。随着插入和删除操作的进行,队列所占的存储空间也在为队列结构所分配的连续空间中移动。
  • 当rear增加到指向分配的连续空间之外时,队列无法再插入新元素,但这时往往还有大量可用空间未被占用。

4.2循环队列

 为了使队列空间能重复使用,往往对顺序队列稍加改进:无论插入或删除,一旦rear指针增1或front指针增1 时超出了所分配的队列空间,就让它指向这片连续空间的起始位置。

可用取余运算rear%MaxSize和front%MaxSize来实现。

在循环队列中,当队列为空时,有front=rear,而当所有队列空间全占满时,也有front=rear。为了区别这两种情况,规定循环队列最多只能有MaxSize-1个元素,当循环队列中只剩下一个空存储单元时,队列就已经满了。因此,队列判空的条件时front=rear,而队列判满的条件时front=(rear+1)%MaxSize。

Java对队列的操作:

Queue是java中实现队列的接口,它总共只有6个方法,如下:

1)压入元素(添加):add()、offer()
相同:未超出容量,从队尾压入元素,返回压入的那个元素。
区别:在超出容量时,add()方法会对抛出异常,offer()返回false

2)弹出元素(删除):remove()、poll()
相同:容量大于0的时候,删除并返回队头被删除的那个元素。
区别:在容量为0的时候,remove()会抛出异常,poll()返回false

3)获取队头元素(不删除):element()、peek()
相同:容量大于0的时候,都返回队头元素。但是不删除。
区别:容量为0的时候,element()会抛出异常,peek()返回null。

 

 

标签:arr,删除,队列,元素,链表,myStack,数据结构,public
From: https://www.cnblogs.com/coooookie/p/17411477.html

相关文章

  • 单调队列优化dp
    单调队列优化dp对于一些比较简单的题目,我们可以直接凭借经验进行优化。但是对于类似\(max(f[j-kw]+kv)\)(多重背包)我们就很难凭借经验找到优化方式了这个时候,我们就可以尝试一下下面的方法:我们观察一些简单的,可以单调队列优化的方程,他们都有这样的形式:\(max/min(g[i-k])(L\l......
  • #yyds干货盘点# LeetCode程序员面试金典:相交链表
    1.简述:给你两个单链表的头节点 headA和headB,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回null。图示两个链表在节点c1开始相交:题目数据保证整个链式结构中不存在环。注意,函数返回结果后,链表必须保持其原始结构。自定义评测:评测系统的输入......
  • 消息队列篇
    本文章学习资源黑马程序员Kafka视频教程及资料,黑马程序员YYDS一、简介1.消息队列简介消息队列,英文名:MessageQueue,经常缩写为MQ。从字面上来理解,消息队列是一种用来存储消息的队列。我们可以简单理解消息队列就是将需要传输的数据存放在队列中。很多时候消息队列不是一个永久性......
  • 数据结构
    数据结构1线性表1.1顺序表1.1.1比较数组大小题目:设A=(a1,a2,am)和B=(b1,b2,...,bn)均为顺序表,A'和B'分别是除去最大公共前缀后的子表。例如,A=(b,e,i,j,i,n,g),B=(b,e,i,f,a,n,g),则两者的最大公共前缀为b、e、i,在两个顺序表中除去最大公共前缀后的......
  • STM32环形串口队列程序 大数据串口收发 实时不丢包 串口程序平常产品开发中编写或移
    STM32环形串口队列程序大数据串口收发实时不丢包串口程序平常产品开发中编写或移植的程序并亲自测试通过,均为工程文件格式,可直接编译使用。注:毫无基础的请勿拍,程序文件不接受退货。该程序为大数据量吞吐的串口收发例程,中断接收,边收边发,采用大数据环形队列,处理过程超快不丢包,接......
  • 7935: 最大值问题 单调队列
    描述 给定n个正整数,crq先选了第1~k个数,要求yuyu求出最大值,yuyu轻松完成,crq直接甩出一堆,要求第2~k+1个,3~k+2个,...,n-k+1~n个,全部都求出来,之后便轻松休息了。  输入 第一行两个整数 n和k(1≤k≤n≤106)。第二行 n个整数,表示编号1~n方格中的数字ai(1≤ai≤3×107)。......
  • 数据结构
    数据结构堆1.插入一个元素:h[++size]=x;up(size);2.求集合中当前最小值:h[1];3.删除最小值:h[1]=h[size];size--;down(1);4.删除任意一个元素:h[k]=h[size];size--;up(k)ordown(k);5.修改任意一个元素:h[k]=x;up(k)ordown(k);[NOIP2004提高组]合并果子/[USA......
  • 重新排序链表
     /** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode() : val(0), next(nullptr) {} *     ListNode(int x) : val(x), next(nullptr) {} *     ......
  • 优秀课件笔记之什么是数据结构
    1、本文所以内容来自著名高校课件和学生笔记(校园里面经常见到有人高价买笔记)2、任课教师不会提供参考文献,所以只能对作者表示感谢,如果引用了您的作品,可以用回复方式补充参考文献。3、我不对文章无关问题进行解答,文章内容也比较难,我也很难解答您遇到的问题,如果发现BUG可以用回复方......
  • 数据结构之栈
    Stack类型定义栈是限定仅在表尾进行插入和删除操作的线性表,又称为后进先出(lastinfirstout)的线性表(LIFO结构),表尾称为栈顶,表头称为栈底,不含元素则称为空栈;抽象数据类型:InitStack(&S)//构造空栈SDestoryStack(&S)//销毁栈SClearStack(&S)......