起航学习网

我是一个栈，先来跟你介绍一下我的家族，我的家族是一个很古老的家族，家族成员很多，外界称呼我们这个家族为数据结构。我们是计算机世界中存储和组织数据的。数据结构家族在计算机世界中是至关重要的，因为我们家族功能的强大，现代编程语言及其API中都有我们家族成员的身影。

我的家族是一个庞大的家族。家族中也有几大分支，比如说树、图、堆、散列表等。各个分支都有不同的能力，所以很多人选择适当的数据结构是一项很重要的工作。我们家族和算法家族是世交，基本上所有重要场合两家都会一起出现。

我叫栈，我的爸爸叫数组，我的妈妈叫链表，我的双胞胎弟弟叫队列。我们这个家庭是整个数据结构家族中比较重要的家庭。

和你说过了，我们数据结构家族是计算机世界中储存和组织数据的。我的家族之所以这么强大，就是因为我们要应付各种需求，提供不同的数据存储方式。我的四个家庭成员分别可以解决不同的数据存取需求。

数组

说起我的爸爸——数组，他是数据结构家族的族长，人们都说他是数据结构大家族的根基。很多编程语言都内置数组。

数组爸爸是个很富有的人，他有很多土地。每当有人找他来存储数据的时候，他都会预先划分出一块连续的土地(连续的内存)，然后把别人交给他的数据按顺序存储在这些连续的土地中，当别人来取这些数据的时候，需要提供给数组要取哪块土地中的数据(数组的位置索引)，然后数组就可以直接去那块土地中把数据取出来，交给需要读取这个数据的人。并不是所有数据数组都能帮忙存储的，父亲只会帮别人存储相同类型的数据。

数组数据结构是由相同类型的元素(element)的集合所组成的数据结构，分配一块连续的内存来存储。利用元素的索引(index)可以计算出该元素对应的存储地址。

我的家族的所有人都支持几个基本的操作：插入、删除、读取。

因为数组爸爸在存储数据的时候，是按照顺序保存的，他保存数据的土地是一块一块相连的。那么，他的特点就是寻址读取数据比较容易，但是插入和删除比较困难。这个其实比较好理解。读取容易的原因是只要你告诉数组你要从哪块土地读取数据，他就会直接去那块土地中把数据取出来给你。插入和删除比较麻烦，主要是因为这些存储数据的空间都是连着的，比如编号为0-1-2-3-4这五块土地中都保存了数据，但是现在你要往1中插入一块数据，那就意味着从1开始，后面的所有土地中的数据都要往后移一个位置。这是很大的工作量啊。

链表

人们都说，男女搭配，干活不累。由于数组爸爸有寻址容易，插入和删除困难的问题，他在找老婆的时候特意找了一个和自己互补的姑娘——链表。链表妈妈的特点正好是寻址困难，插入和删除容易。

在帮助别人存储数据这件事上，链表的方式和数组有很大不同。数组是提前划分了一大片连续的土地，用来存储数据。但是链表不是这么做的，因为链表妈妈家里并没有数组爸爸家里那么富有。他的数据存储并不是连续的，能这么做的原因是妈妈存储数据的土地中有两块区域，一块用来保存数据，一块用来记录下一个数据保存在哪块土地中(指针)。这样，别人找他存储数据的时候，她就要根据指示先找到下一块空余的土地，然后把数据保存在里面。链表这样的数据存储方式可以把一些碎片空间利用起来。

链表是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里保存着下一个节点的指针。

通过上面的这种保存数据的方式，链表在插入和删除数据的时候比较容易，比如编号为0-1-2-3-4这五块土地中都保存了数据，但是现在你要往1中插入一块数据，那么只需要依次更改0号土地和1号土地中记录下一块土地地址的值就行了。对于其他的数据存储没有任何影响。但是，如果你想从数据中取出一块数据那可就麻烦了，因为这意味着链表妈妈要帮你从第一块土地开始挨个帮你找。一直找到你要的数据为止。

我和我的胞弟

栈，也就是我，一个英俊潇洒的数据结构。我和队列是一堆孪生兄弟。我们两个都可以用数组和链表来实现。虽然是双胞胎，但是我们两个都是有性格的，我们要求别人存储数据和取出数据的顺序要按照我们的规矩来。

我的原则是：先进后出(栈)

弟弟的原则是：先进先出(队列)

我给你举个例子你就明白了，我和弟弟每个人都有一个管子，用来帮你们保存数据，当然这个管子可能是用数组爸爸是实现的也可能是链表妈妈实现的。我们握住管子的两头，我的这个管子只能通过管子左面的口子放入东西，也只能从左面的口子取出东西。右面的口子是不开的。而弟弟队列呢，他的管子的左面的口子放东西，管子的右面的口子取东西。

爸爸妈妈是如何生出我和弟弟的

上面说过了，栈和队列都是可以通过数组或者链表实现的。当然了，父母创造孩子，天经地义嘛。那么，先来看看我是如何实现的。作为一种数据结构，我接口有isEmpty()、size()、push()、pop()、peek()以及迭代。

先来看看如何通过数组实现栈：

再来看看如何使用链表实现栈：

同样作为数据结构的弟弟，也有些接口需要实现：isEmpty()、size()、enqueue()、dequeue()、peek()以及迭代。队列和栈不同的是，入列和出列是在两个地方，所以需要维护两个变量来表示队头和队尾。

使用数组实现队列：

public class Queue implements Iterable { private Item[] q; private int N; // 队列中元素的数量 private int first; // 队头元素的下标 private int last; // 队尾元素的后一个位置的下标，也就是元素入列时可以放置的位置 /** * 初始化队列，此时头尾下标重合 */ public Queue() { q = (Item[]) new Object[2]; N = 0; first = 0; last = 0; } /** * 依旧用N判断队列是否为空 */ public boolean isEmpty() { return N == 0; } /** * 队列中元素数量 */ public int size() { return N; } // 调整数组大小 private void resize(int max) { assert max >= N; Item[] temp = (Item[]) new Object[max]; //注意这里：把N个元素放入总大小为max的队列(max>=N) //因为循环使用数组，从first开始的第i个元素可能保存在了first //前面(即last在first前面)。 for (int i = 0; i < N; i++) { temp[i] = q[(first + i) % q.length]; } q = temp; //把小队列按顺序复制到大队列后重置队头和队尾 first = 0; last = N; } /** * 元素入列 */ public void enqueue(Item item) { if (N == q.length) resize(2*q.length); q[last++] = item; // 元素入列 if (last == q.length) last = 0; // 如果last超出数组下标，把last置零，循环利用数组 N++; } /** * 元素出列 */ public Item dequeue() { if (isEmpty()) throw new NoSuchElementException("Queue underflow"); Item item = q[first]; q[first] = ull; // 防止对象游离 N--; first++; if (first == q.length) first = 0; // 循环利用数组，下一个队头在下标为0的地方 if (N > 0 && N == q.length/4) resize(q.length/2); return item; } /** * 返回队头元素但不出列 */ public Item peek() { if (isEmpty()) throw new NoSuchElementException("Queue underflow"); return q[first]; } /** * 实现Iterable接口 */ public Iterator iterator() { return new ArrayIterator(); } //实现迭代器 private class ArrayIterator implements Iterator { //维护一个i用于迭代 private int i = 0; public boolean hasNext() { return i < N; } public void remove() { throw new UnsupportedOperationException(); } //直接利用first进行遍历，注意可能存在数组的循环利用 public Item next() { if (!hasNext()) throw new NoSuchElementException(); Item item = q[(i + first) % q.length]; i++; return item; } } /** * 测试 */ public static void main(String[] args) { Queue q = ew Queue (); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) q.enqueue(item); else if (!q.isEmpty()) StdOut.print(q.dequeue() + " "); } StdOut.println("(" + q.size() + " left on queue)"); }}

使用链表实现队列：

public class Queue implements Iterable { private Node first; // 队头节点 private Node last; // 队尾节点(注意和上面的last区分，last并不是队尾元素的下标) private int N; // 队列元素的数量 // 辅助类Node private static class Node { private Item item; private Node next; } /** * 初始化队列 */ public Queue() { first = ull; last = null; N = 0; } public boolean isEmpty() { return first == null; } public int size() { return N; } /** * 返回但不删除头元素 */ public Item peek() { if (isEmpty()) throw new NoSuchElementException("Queue underflow"); return first.item; } /** * 元素入列 */ public void enqueue(Item item) { //记录尾节点 Node oldlast = last; //创建新的尾节点 last = new Node(); last.item = item; last.next = ull; //如果队列是空的，将first置为last，因为这时候队列中只有一个元素 if (isEmpty()) first = last; //否则执行正常的在尾节点插入新节点的操作 else oldlast.next = last; N++; } /** *元素出列 */ public Item dequeue() { if (isEmpty()) throw new NoSuchElementException("Queue underflow"); //队头元素出列 Item item = first.item; first = first.next; N--; //如果这时候队列为空，表示原来只有一个元素，这时候也将last置为null if (isEmpty()) last = null; return item; } public String toString() { StringBuilder s = new StringBuilder(); for (Item item : this) s.append(item + " "); return s.toString(); } public Iterator iterator() { return new ListIterator(first); } // 实现迭代 private class ListIterator implements Iterator { private Node current; //要实现迭代，我们只需要维护一个节点，并在开始的时候将它置为first public ListIterator(Node first) { current = first; } public boolean hasNext() { return current != null;} public void remove() { throw new UnsupportedOperationException(); } public Item next() { if (!hasNext()) throw new NoSuchElementException(); Item item = current.item; current = current.next; return item; } } /** * 测试 */ public static void main(String[] args) { Queue q = new Queue(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) q.enqueue(item); else if (!q.isEmpty()) StdOut.print(q.dequeue() + " "); } StdOut.println("(" + q.size() + " left on queue)"); }}

我是一个栈，我的双胞胎弟弟叫队列。我的爸爸是数组，我的妈妈是链表。 你们可以使用数组和链表来实现栈和队列。

好了，今天关于我和我的家族的故事就先给你介绍到这里了。偷偷告诉你一个秘密，其实我和弟弟之间是可以互相转换的。也就是说可以使用栈来实现队列，同样也可以使用队列来实现栈。关于这个小秘密，我下次再给你介绍哦。

感谢大家阅读由Java开发教程分享的“关于栈、数组、链表、队列的形象解释”希望对大家有所帮助，更多精彩内容请关注Java开发培训官网

免责声明：本站文章部分为会员发布或者转载自网络，旨在分享提供阅读，版权归原作者所有，侵必删！

文章出自：http://qh.itpxw.cn/peixun/software/202191002.html

文章标题：关于栈、数组、链表、队列的形象解释

免责声明：本站文章均由入驻起航学习网的会员所发或者网络转载，所述观点仅代表作者本人，不代表起航学习网立场。如有侵权或者其他问题，请联系举报，必删。侵权投诉