数组是内存的实现及栈和队列的数据结构

末蓝、 2024-04-03 08:00 79阅读 0赞

**目录**

一、数组是内存的实现

二、栈和队列

栈

栈的数据结构

队列

队列的数据结构

--------------------

## 一、数组是内存的实现 ##

数组是指多个相同的数据类型在内存中连续排列的一种形式。作为数组元素的各个数据会通过下标编号来区分，这个编号也叫做索引，如此一来，就可以对指定索引的元素进行读写操作。

用char、short、long三种元素来定义数组，数组的元素用\[value\]括起来，里面的值代表的是数组的长度，就像下面的定义：

char g[100];
    short h[100];
    long i[100];

数组定义的数据类型，也表示一次能够读写的内存大小，char、short、long分别已1、2、4个字节为例进行内存的读写

数组是内存的实现，数组和内存的物理结构完全一致，尤其是在读写1个字节的时候，当字节数超过1时，只能通过逐个字节来读取，下面是内存的读写过程：

不同数据类型的数组：

![37f00c6bddbd489fb36429608e14b9e1.png][]

## 二、栈和队列 ##

数组是内存的一种实现，使用数组能够使编程更加高效，也可以通过其他数据结构进行内存的读写

### 栈 ###

栈（stack）是一种很重要的数据结构，栈采用LIFO（Last In Fist Out）即**后入先出**的方式对内存进行操作。它就像一个大的收纳箱，你可以往里面放相同类型的东西，比如书，最先放进收纳箱的书在最下面，最后放进收纳箱的书在最上面，如果你想拿书的话，必须从最上面开始取，否则是无法取出最下面的书籍的

栈的数据结构就是这样，你把书籍压入收纳箱的操作叫做 **压入（push）**，你把书籍从收纳箱取出的操作叫做 **弹出（pop）**，它的模型图大概如下：

![f81d0f34711e4e5e9fa232c61a906d47.png][]

### 栈的数据结构 ###

入栈相当于是增加操作，出栈相当于是删除操作，只不过叫法不一样。栈和内存不同，它不需要指定元素的地址。它的大概使用如下：

//压入数据
    Push(123);
    Push(456);
    Push(789);
    
    //弹出数据
    J = Pop();
    k = Pop();
    l = Pop();

在栈中，LIFO方式表示栈的数组中所保存的最后面的数据（Last In）会被最先读取出来（First On）

运行时栈的变化：

![0403ffb397a64af6bbbdef2fab573fa0.png][]

### 队列 ###

**队列**和栈很相似但又不同，相同之处在于队列也不需要指定元素的地址，不同之处在于队列是一种**先入先出（First In First Out）**的数据结构。队列在我们生活中的使用很像是我们去景区排队买票一样，第一个排队的人最先买到票，以此类推，俗话说：先到先得。它的使用如下：

//往队列中写入数据
    EnQueue(123);
    EnQueue(456);
    Enqueue(789);
    
    //从队列中读出数据
    m = DeQueue();
    n = DeQueue();
    o = DeQueue();

向队列中写入数据称为**EnQeue()**入列，从队列中读取数据称为**Deqeue()**

![7d7f2d3d2d6f49678d1feb5cdaddaf60.png][]

### 队列的数据结构 ###

与栈相对，FIFO的方式表示队列中最先保存的数据会被优先读取出来

运行时队列的变化：

![c10469969d354cad93d34d827885da28.png][]

队列的实现一般有两种：**顺序队列**和**循环队列**，上图的就是顺序队列

[37f00c6bddbd489fb36429608e14b9e1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/86595436348b44fe8ce9c148cdff3478.png
[f81d0f34711e4e5e9fa232c61a906d47.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/16fae1ba29a94dc8a91f13cb219b00a3.png
[0403ffb397a64af6bbbdef2fab573fa0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/94314ea71fa642a9b2f727de283295b0.png
[7d7f2d3d2d6f49678d1feb5cdaddaf60.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/19eb90ddc1464a5cadaa5347107a7aef.png
[c10469969d354cad93d34d827885da28.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/0cf8d6a93e634e5eb5d014c80f9285c3.png