栈和队列（详细版，一看就懂。包含栈和队列的定义、意义、区别，实现）

栈和队列

一、栈和队列的定义、区别，存在的意义

1.栈的定义

（1）栈：栈实际上是一种线性表，它只允许在固定的一段进行插入或者删除元素，在进行数据插入或者删除的一段称之为栈顶，剩下的一端称之为栈顶。其遵循的原则是后进先出。
（2）栈的核心操作：三大核心操作，入栈，出栈，取栈顶元素
（3）对于栈的形象理解：子弹的弹夹我们一定见过，子弹在被压入的时候就相当于是一个个元素，而弹夹就相当于是栈。先被压入的子弹是最后被打出的，先压入的元素是最后出来的，也就是后进先出。

2.队列的定义

（1）队列：首先队列也是一种特殊的线性表，它允许在一端进行插入数据，在另一端进行删除数据的。队列里边有队首，队尾，队首元素。其遵循的原则是先进先出。
（2）队列的核心操作：三大核心操作分别是入队列，出队列，取队首元素。
（3）对于队列的形象理解：火车穿越隧道，火车的头相当于是队列的首，火车的尾相当于是队列的尾部。火车在穿越隧道的时候，头部先进入隧道头部也先出隧道，尾部后进入尾部后出隧道。队列也就是先入的元素先出队列，后进入的元素后出队列。

3.栈和队列的区别

（1）栈和队列的出入方式不同：栈是后进先出、队列是先进先出。
（2）栈和队列在具体实现的时候操作的位置不同：因为栈是后进先出，它在一段进行操作；而队列是先进先出，实现的时候在两端进行。在Java标准库中实现队列时是按照链表实现的。

4.栈和队列存在的意义

上边我们提到过：栈和队列都是一种典型的线性表，都是基于线性表（顺序表和链表）来实现的，那么我们研究栈和队列的目的何在？因为在栈和队列定义后，只有那三种操作，而那三种操作都是最常用的，它支持的操作越少，我们在使用的时候关心的点也就越少，用起来就越不容易出错。在计算机中“少即是多”，少意味着功能比较少、比较呆板。多意味着功能很多，用的时候要操的心就越多，就越容易出错。综上：栈和队列存在的意义就是减少线性表的基本操作，提取常用操作，让人们使用起来更方便，更不容易出错。

二、栈的实现

1.基于顺序表来实现栈

栈的操作是在一端进行的，所以我们选择在顺序表的尾部进行操作：入栈用尾插来实现、出栈用尾删来实现、取栈顶元素就是取尾部元素。
注意：我们在用顺序表来实现栈的时候选取的是在顺序表的尾部来进行的，但这并不是说在顺序表的头部就不能实现。只是在头部实现的时候，不管是头插还是头删都要进行元素的搬运，时间复杂度太高，所以不选取。

下边是基于顺序表来实现的栈：

public class MyStackForArrayList {
    // 用顺序表来实现栈
    // 栈的特点：后进先出，所以在顺序表中入栈用尾插，出栈用尾删，取栈顶元素用[]操作
    // 创建数组用来表示顺序表,栈的容量是100，要是不够后边可以进行扩容
    private int[] data = new int[100];
    // 记录顺序表的当前值
    private int size = 0;

    // 一，栈的实现:顺序表实现
    // 1.入栈，就是顺序表中的尾插，头插也能实现，但是要进行搬运，效率太低
    public void push(int val) {
        // 特殊情况的考虑，这里也可以进行扩容
        if (size >= data.length) {
            return;
        }
        // 一般情况的处理
        data[size] = val;
        size++;// 入栈要让size++
    }
    
    // 2.出栈，是有返回值的，用Integer来接收，它可以返回null。
    public Integer pop() {
        // 特殊情况
        if (size == 0) {
            return null;
        }
        // 一般情况
        int ret = data[size-1];// 保存那个出栈的元素，后边进行返回
        size--;// 出栈要让size--
        return ret;
    }
    
    // 3.取栈顶元素
    public Integer peek() {
        // 特殊情况
        if (size == 0) {
            return null;
        }
        return data[size - 1];
    }
}

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
33
34
35
36
37
38
39
40
41
42

2.基于链表来实现栈

用链表来实现栈：在用链表实现栈的时候，我们操作的一段选取头端。用头插表示入栈，用头删来表示出栈，取栈顶元素就是取链表的head的值。
注意：选取在链表的头部实现并不是说在链表的尾部不能进行，而是在尾部进行操作的时候，因为每一次那个tail都会进行更新，所以要用一个引用来记录tail的位置，这样就占据了一块内存空间，因此不选它。

下边是基于链表实现的栈：

class Node {
    int val;
    Node next;
    public Node(int val) {
        this.val = val;
    }
}

// 链表实现栈，头插表示入栈，头删表示出栈，取栈顶元素。链表头插，头删还是为了减少内存的开销
public class MyStackForLinkedList {
    // 先搞一个链表
    private Node head = null;
    // 1.入栈,头插,不需要返回要插入的值
    public void push(int val) {
        // 将要插入的元素放在链表里边
        Node newNode = new Node(val);
        // 特殊情况的处理，空链表
        if (head == null) {// 链表本来是空的
            head = newNode;
            return;
        }
        // 处理一般情况
        newNode.next = head;
        head = head.next;
    }

    // 2.出栈，就是头删，出栈要返回一个值
    public Integer pop() {// 用Integer来为了可以返回那个null
        // 特殊情况处理，链表是空
        if (head == null) {
            return null;
        }
        // 链表之中只有一个元素，删除就没有元素了
        if (head.next == null) {
            int ret = head.val;
            head = null;
            return ret;
        }
        // 一般情况的处理
        int ret = head.val;
        head = head.next;
        return ret;
    }

    // 3.取栈顶元素
    public Integer peek() {
        // 特殊情况:要是链表是空的，没得取，返回null
        if (head == null) {
            return null;
        }
        return head.val;
    }
}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

三、队列的实现

1.基于链表来实现队列

队列的操作在两端进行，所以我们选择在链表的尾部进行插入表示入队列，头删来表示出队列，用 head.val 操作来表示取队首元素。
注意：这里的头删和尾插的顺序是可以进行交换的，头和尾只是选的两个引用罢了。咋样选取都是一样的。

下边是基于链表来实现的队列：

// 基于链表来实现队列
// 因为队列是先进先出的，所以用尾插表示入队列。头删表示出队列，.操作表示取队列元素

public class MyQueueForLinkedList {
    // 弄一个Node内部类,要带上static，为了和外部的实例无关
     static class  Node {
         int val;
         Node next;

        public Node(int val) {
            this.val = val;
        }
    }
    // 先创建一个链表，并记录其头节点和尾节点，方便后边的进行尾插
     Node newHead = null;
     Node newTail = null;

    // 1.入队列,就是尾插，为了和Java库中的队列保持一致，用boolean返回值
    public boolean offer(int val) {
        // 将要插入的值放在Node 节点里面
        Node newNode = new Node(val);
        // 情况特殊的处理
        if (newHead == null) {
            // 头节点和尾节点都是要插入的值
            newHead = newNode;
            newTail = newNode;
            return true;
        }
        // 一般情况的处理
        newTail.next = newNode;
        newTail = newTail.next;
        return true;
    }

    // 2.出队列，就是头删，注意头删也是要返回那个要删除的值
    public Integer poll() {
        // 特殊情况的处理,链表为空没得删
        if (newHead == null) {
            return null;
        }
        // 链表只要一个元素
        if (newHead.next == null) {
            int ret = newHead.val;
            // 新头节点就没有了，就是null
            newHead = null;
            return ret;
        }
        // 处理一般情况的处理
        int ret = newHead.val;
        newHead = newHead.next;
        return ret;
    }
    // 3.取队列首元素
   public Integer peek() {
        // 特殊情况的处理
       // 链表为空，没得取
       if (newHead == null) {
           return null;
       }
       // 一般情况的处理
       return newHead.val;
   }
}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

2.基于顺序表实现队列

（1）基本思想:创建两个引用head和tail表示队列的头部和尾部，开始的时候head和tail都表示null，此时head == tail表示的是队列是空的 。
（2）出现的问题：每入一次队列给tail进行++，要是tail已经满了的时候就让tail == head，此时head和tail也是相等的，所以就不能区别队列到底是空的还是满的。
（3）解决方法：
方法1：是空上让出一个内存空间，不让tail和head重合。这种方法浪费了一块内存空间，直接让那个空间是空的，也就是用这种方法后：head == tail表示空， tail == head - 1表示队列是满的。看起来非常不好看。
方法2：创建一个变量size，时刻记录队列里边元素的多少，没进行一次入队操作进行size++，每进行一次出队操作让size–，最后用size的值来区别队列是空的还是满的。

下边是基于顺序表实现的队列：

public class MyQueueForArrayList {
    // 用顺序表来实现队列
    // 基本思路：让head = 0，tail = 0;队列的长度是[head，tail),包含head不包含tail。
    // 入队：tail++,入完判断tail的值，要是 == data.length,让tail从0又开始
    // 出队列：让head++
    // 这样操作当head == tail时，有两种结果：1，是队列是空的时候    2，是队列是满的时候
    // 所以用size来记录一下顺序表的具体的大小，根据size来判断队列是否为满。
    // 创建数组
    public int[] data = new int[100];
    public int head = 0;
    private int tail = 0;
    // 这个用来判断队列到底是空的还是满的
    private int size = 0;

    // 1.入队操作，tail++，然后判断size的值
    public boolean offer(int val) {
        // 特殊情况的处理,先判断size的值的大小，每一次都是以size来判断队列是否是空的
        if (size == data.length) {// 队列已经满了
            return false;
        }
        // 一般情况的处理
        data[tail] = val;
        // 完成插入之后，判断一下tail的值的
        if (tail == data.length) {// 要是让tail从0开始
            tail = 0;
        }
        // 否则更新size的值
        size++;
        return true;
    }

    // 2.出队列，核心操作，头删，head--
    public Integer poll() {
        // 特殊情况的处理
        // 队列为空，没得取
        if (size == 0) {
            return null;
        }
        // 一般情况的处理
        int ret = data[head];
        head++;
        // 每一次要判断head的值是否到达了末尾
        // 要是到达了末尾，让head也是0
        if (head == data.length) {
            head = 0;
        }
        size--;
        return ret;
    }

    // 3.取队首元素
    public Integer peek() {
        // 特殊情况的处理
        if (size == 0) {// 为空，没得取
            return null;
        }
        return data[head];
    }
}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

好了以上就是我学完栈和队列所了解到的内容，希望对大家有所帮助，要是有错误的地方还望大家海涵并指出。