线性表链表结构堆栈 1 顺序栈2 链式栈 队列 1 顺序队列2 链式队列 总结

线性表、链表以及队列是在coding中最为常见的数据结构，在平时编程时，我们会有意识或无意识的进行选择。

1. 线性表

---

线性表本质上是一种顺序存储结构，所有需要存储的内容是可以被索引的，说起来，在编程时常用的数组就是线性表的一种。 线性表的数据结构表示：

class LinearList { private: int MaxSize; //线性表的最大尺寸 int length; //线性表的实际长度 int *element; //存储线性表的数组 //一般使用模板来代替int定义，这里为了方便，使用int public: //线性表的构造函数，默认最大尺寸为10 LinearList(int MaxSize = 10); ~LinearList() { delete[] element; } bool IsEmpty()const { return length == 0; } bool IsFull()const { return length == MaxSize; } int Length()const { return length; } //线性表的存取函数，其中k表示索引号，item表示存取的数据值 bool Find(int k, int &item)const; int Search(const int &item)const; void Delete(int k, int &item)const; void Insert(int k, const int &item); }

不难看出，线性表的优势在于随机访问的效率高，速度快（因为可以进行索引），而且实现起来较为简单，但是由于先行表的最大长度固定，所以想要增加线性表的长度并不容易，如果需要进行线性表的长度变化，可以创建一个新的线性表，并且将原始的线性表中的内容完全复制到新的线性表中，删除原始线性表即可。

2. 链表结构

---

链表弥补了线性表的缺点，但是又增加了新的问题。看如下例程：

class Node { private: int data; //数据域，一般为模板类 Node *next; //指向下一个结点 public: Node(Node *nextNode = NULL) { next = nextNode; } Node(const int& item, Node *nextNode = NULL) { data = item; next = nextNode; } void setData(int data); int Data() { return data; } }; class LinkedList { private: Node *head; //头指针 public: LinkedList() { head = new Node(); } LinkedList(int &item); ~LinkedList(); bool IsEmpty()const { return head->next == NULL; } int Length()const; //返回链表长度 //这里的实现多种多样，此下几个函数为其中一种 //通过遍历链表找到第k个元素，将该元素赋值给item bool Find(int k, int &item)const; int Search(int k, int &item)const; void Delete(int k, int &item)const; void Insert(int k, const int &item); }

该程序结点只是链表的一种，单向链表。还有其他如，循环链表，双向链表，十字链表等等。 循环链表中最后的一个元素的后继结点为表头结点，双向链表中每个元素有两个指针，分别指向其前驱结点与后继结点。

Tip： 前驱结点：对于某一个结点来说，所有指向该结点的结点，就是该结点的前驱结点。 后继结点：对于某一个结点来说，该结点所指向的下一个结点，就是该节点的后继结点。

3. 堆栈

---

堆栈这一概念应该是分开的，堆是堆，栈是栈，两种不同的东西。 栈的基本组成为栈顶指针，压栈，弹栈动作，并且只能对栈顶元素进行读写操作，。其逻辑结构是先进栈的元素后读出，后进入的元素先读出，我们可以称之为后来居上的原则（LIFO）。栈也仅仅是一种概念，其实现是由其他基本数据结构完成的。

在这里只讲栈，不讲堆。

3.1 顺序栈

顺序栈，其实就是用线性表来实现的栈。 顺序栈的主要思想是：创建一个线性表，栈顶指针为索引号，其值为当前栈顶的索引号，压栈和弹栈的动作仅仅是对栈顶指针的值进行赋值和清除。

class AStack { private: int size; //线性表的长度 int *stackArray; //存放栈顶元素的数组 int top; //栈顶指针 public: AStack(int MaxStackSize = 10) { size = MaxStackSize; stackArray = new int[MaxStackSize]; top = -1; } ~AStack() { delete[] stackArray; } bool Push(const int &item); //压栈 bool Pop(int &item); //弹栈 bool Peek(int &item)const; //读取栈顶元素 int IsEmpty()const { return top == -1; } int IsFull()const { return top == size - 1; } void clear() { top = -1; }

顺序栈的优势与线性表的优势相同，都是实现简单，效率高，缺点也是不易对栈进行扩充。

3.2 链式栈

听名字就知道了，这种栈是以链表存储结构实现的。

class LStack { private: Node *top; //指向栈顶指针 public: LStack() { top = NULL; } ~LStack() { clear(); } void clear(); //清空栈 bool Push(const int &item); bool Pop(int &item); bool Peek(int &item); int IsEmpty()const { return top == NULL; } }

链式栈的优缺点可以与链表结构相似。

4. 队列

---

队列和堆栈的性质较为类似，只是队列采取的原则是，先进先出原则（FIFO）。在队列中所有的操作均只能对队首与队尾进行，而在实现上，也分为顺序队列以及链式队列。

这种原则和日常排队相像，先到先得。

4.1 顺序队列

使用顺序存储的方式实现，其主要思想为： 创建一个线性表，增加两个指针，分别命名为队首指针，指向队列最开始的位置，并且元素由此出队，队尾指针，指向当前插入队列的位置，并且只能向后插入。

其实队列还可以增加一个指针，用于遍历队列中的元素，但是这样做就破坏了队列操作的原则，使队列退化成了一个简单的线性表。

class AQueue { private: int front; //队首 int rear; //队尾 int count; //队列元素个数 int *QArray; //队列数组 int size; //队列大小 public: AQueue(int MaxQueueSize = 10); ~AQueue() { delete[] QArray; } bool QInsert(const int &item); //向队尾插入元素 bool QDelete(int &item); //删除队首元素 void QClear() { front = rear = count = 0; } int QFront()const; //读取队首元素 bool IsEmpty()const { return count == 0; } bool IsFull()const { return count == size; } }

4.2 链式队列

思想和顺序队列类似，实现如下：

class LQueue { private: Node *front, *rear; public: LQueue() { front = rear = NULL; } ~LQueue() { QClear(); } void QInsert(const int &item); bool QDelete(int &item); bool QFront(int &item); int IsEmpty()const { return front == NULL; } void QClear();

无论是堆栈还是队列，上述几种都是较为基础的形式，关于堆栈和队列，还有其相应的扩展，如双端队列，双栈，超队列，超栈等等。

5. 总结

---

数据结构是计算机开发中最为重要的一门知识，可以说，只要是编程，就会用到数据结构。 本文仅仅是数据结构的冰山一角，但是随着编程的深入，你会发现，这冰山一角却是冰山最重要的基础。

数据结构的定义很广，包括使用C语言或是其他语言编写一个小的struct结构体，都可以被视为一中数据结构。 还是那句话，所有复杂的事物，都是由简单的符号所组成的。