数据结构链表，栈和队列_链表、栈、队列

一、链表

• 链表是一系列的存储数据元素的单元通过指针串接起来形成的，因此每个单元至少有两个域，一个域用于数据元素的存储，另一个或两个域是指向其他单元的指针。这里具有一个数据域和多个指针域的存储单元通常称为节点（node）。
• 链表的第一个节点和最后一个节点，分别称为链表的头节点和尾节点。尾节点的特征是其 next 引用为空（null）。链表中每个节点的 next 引用都相当于一个指针，指向另一个节点，借助这些 next 引用，我们可以从链表的头节点移动到尾节点。
• 链表数据结构中主要包含单向链表、双向链表及循环链表：

介绍单向链表
　　单向链表只有一个指针域，在整个节点中数据域用来存储数据元素，指针域用于指向下一个具有相同结构的节点。
　　
　　单向链表中，每个节点的数据域都是通过一个 Object 类的对象引用来指向数据元素的，与数组类似，单向链表中的节点也具有一个线性次序，即如果节点 a1 的 next 引用指向节点 a2，则 a1 就是 a2 的直接前驱，a2 是 a1 的直接后续。只能通过前驱节点找到后续节点，而无法从后续节点找到前驱节点。
特点：
　　数据元素的存储对应的是不连续的存储空间，每个存储结点对应一个需要存储的数据元素。每个结点是由数据域和指针域组成。 元素之间的逻辑关系通过存储节点之间的链接关系反映出来。
　　逻辑上相邻的节点物理上不必相邻。
缺点：
1、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。
2、查找结点时链式存储要比顺序存储慢（每个节点地址不连续、无规律，导致按照索引查询效率低下）。
优点：
1、插入、删除灵活 (不必移动节点，只要改变节点中的指针，但是需要先定位到元素上)。
2、有元素才会分配结点空间，不会有闲置的结点。
转载自链表详解（易懂）
例题：输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

using System.Collections.Generic;
/*
public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode (int x)
    {
        val = x;
    }
}*/
class Solution
{
    // 返回从尾到头的列表值序列
    public List<int> printListFromTailToHead(ListNode listNode)
    {
        // write code here
            List<int> list = new List<int>();
            ListNode node = listNode;
            while (node != null)
            {
                list.Add(node.val);//从链表的表头开始取数
                node = node.next;
            }
            List<int> re = new List<int>();
            for (int i = list.Count - 1; i > -1; i--)
            {
                re.Add(list[i]);
            }
            return re;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

二、栈和队列

队列（Queue）：是限定只能在表的一端进行插入和另一端删除操作的线性表，单向队列只能在一端插入数据（后），另一端删除数据（前）；进行插入操作的称为队尾，进行删除操作的称为队头；队列中的数据被称为元素；没有元素的队列称为空队列。由于只能一端删除或者插入，所以只有最先进入队列的才能被删除，因此又被称为先进先出（FIFO—first in first out）线性表。

队列分为两种：双向队列和单向队列

• 单向队列：只能在一端删除数据，另一端插入数据。
• 双向队列：两端都可以进行插入数据和删除数据操作。

栈（Stack）：限定只能在表的一端进行插入和删除操作的线性表，特点是先进后出，利用pop拿出数据，push放入数据。

例题：用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
Push（进栈）的时候只需要往Stack1中放入数据，Pop（出栈）的时候，因为先进的数在Stack1的栈底，必须将Stack1中的数据Push到Stack2中，然后再Pop；

using System.Collections.Generic;
class Solution
{
    Stack<int> stack1=new Stack<int>();
    Stack<int> stack2=new Stack<int>();
    public void push(int node) 
    {
        stack1.Push(node);
    }
    public int pop() //取
    {
        int r=0;
        if(stack2.Count!=0)
        {
            r=stack2.Pop();
        }
        else
        {
            while(stack1.Count!=0)
            {
              stack2.Push(stack1.Pop());
            }
            if(stack2.Count!=0)
            {
                r=stack2.Pop();
            }
        }
        return r;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

总结：push操作就直接往stack1中push， pop操作需要分类一下：如果stack2为空，那么需要将stack1中的数据转移到stack2中，然后在对stack2进行pop，如果stack2不为空，直接pop就ok。

队列和栈的遍历数据速度
队列：基于地址指针进行遍历，而且可以从头部或者尾部进行遍历，但不能同时遍历，无需开辟空间，因为在遍历的过程中不影响数据结构，所以遍历速度要快
栈：只能从顶部取数据，也就是说最先进入栈底的，需要遍历整个栈才能取出来，遍历数据时需要微数据开辟临时空间，保持数据在遍历前的一致性