栈和队列就是这么简单

本是古典何须时尚 2021-09-30 19:38 205阅读 0赞

# 一、前言 #

上一篇已经讲过了链表【[Java实现单向链表][Java]】了，它跟数组都是线性结构的基础，本文主要讲解线性结构的应用：**栈**和**队列**

如果写错的地方希望大家能够多多体谅并指正哦，如果有更好的理解的方式也希望能够在评论下留言，让大家学习学习～

# 二、数据结构【栈】就是这么简单 #

## 2.1数据结构【栈】介绍 ##

数据结构的栈长的是这个样子：

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

其实非常好理解，我们将栈可以**看成一个箱子**

说到栈的特性，肯定会有一句经典的言语来概括：**先进后出(LIFO, Last In First Out)**

## 2.2数据结构【栈】 代码实现 ##

栈的分类有两种：

从上一篇写链表我就认知到我的算法是有多渣了，普通的单链表操作也能把我绕得晕晕的。

由于我的链表还不是很熟，栈又不是很难，那么我就用链表来创建动态栈了！

既然是用链表，我们还是把上一篇节点的代码拿过来吧：

public class Node {    //数据域    public int data;    //指针域，指向下一个节点    public Node next;    public Node() {    }    public Node(int data) {        this.data = data;    }    public Node(int data, Node next) {        this.data = data;        this.next = next;    }}class Node {
        
    
        //数据域
        public int data;
    
        //指针域，指向下一个节点
        public Node next;
    
        public Node() {
        
        }
    
        public Node(int data) {
        
            this.data = data;
        }
    
        public Node(int data, Node next) {
        
            this.data = data;
            this.next = next;
        }
    
    }

要链表用来表示栈，这次会有两个指针：

public class Stack {    public Node stackTop;    public Node stackBottom;    public Stack(Node stackTop, Node stackBottom) {        this.stackTop = stackTop;        this.stackBottom = stackBottom;    }    public Stack() {    }}class Stack {
        
    
        public Node stackTop;
        public Node stackBottom;
    
        public Stack(Node stackTop, Node stackBottom) {
        
            this.stackTop = stackTop;
            this.stackBottom = stackBottom;
        }
    
        public Stack() {
        
        }
    
    
    }

### 2.2.1进栈 ###

**将原本栈顶指向的节点交由新节点来指向，栈顶指向新加入的节点**

/**     * 进栈     *     * @param stack 栈     * @param value 要进栈的元素     */    public static void pushStack(Stack stack, int value) {        // 封装数据成节点        Node newNode = new Node(value);        // 栈顶本来指向的节点交由新节点来指向        newNode.next = stack.stackTop;        // 栈顶指针指向新节点        stack.stackTop = newNode;    }
        public static void pushStack(Stack stack, int value) {
        
    
            // 封装数据成节点
            Node newNode = new Node(value);
    
    
            // 栈顶本来指向的节点交由新节点来指向
            newNode.next = stack.stackTop;
    
            // 栈顶指针指向新节点
            stack.stackTop = newNode;
    
        }

### 2.2.2遍历栈 ###

**只要栈顶元素的指针不指向栈底**，那么就一直输出遍历结果：

/**     * 遍历栈(只要栈顶指针不指向栈底指针，就一直输出)     *     * @param stack     */    public static void traverse(Stack stack) {        Node stackTop = stack.stackTop;        while (stackTop != stack.stackBottom) {            System.out.println("关注公众号：Java3y：" + stackTop.data);            stackTop = stackTop.next;        }    }
        public static void traverse(Stack stack) {
        
            Node stackTop = stack.stackTop;
    
            while (stackTop != stack.stackBottom) {
        
    
                System.out.println("关注公众号：Java3y：" + stackTop.data);
    
                stackTop = stackTop.next;
            }
    
    
        }

测试：

public static void main(String[] args) {        //初始化栈(无元素)        Stack stack = new Stack(new Node(), new Node());        //栈顶和栈尾是同一指向        stack.stackBottom = stack.stackTop;        //指向null        stack.stackTop.next = null;        //进栈        pushStack(stack, 3);        pushStack(stack, 4);        pushStack(stack, 5);        traverse(stack);    }
    
            //初始化栈(无元素)
            Stack stack = new Stack(new Node(), new Node());
    
            //栈顶和栈尾是同一指向
            stack.stackBottom = stack.stackTop;
    
            //指向null
            stack.stackTop.next = null;
    
    
            //进栈
            pushStack(stack, 3);
            pushStack(stack, 4);
            pushStack(stack, 5);
    
            traverse(stack);
    
        }

结果：

![640?wx\_fmt=png][640_wx_fmt_png]

这就符合了先进后出的特性了～

### 2.2.3判断该栈是否为空 ###

很简单，只要栈顶和栈底是同一指向，那么该栈就为空

/**     * 判断该栈是否为空     *     * @param stack     */    public static void isEmpty(Stack stack) {        if (stack.stackTop == stack.stackBottom) {            System.out.println("关注公众号：Java3y---->该栈为空");        } else {            System.out.println("关注公众号：Java3y---->该栈不为空");        }    }
        public static void isEmpty(Stack stack) {
        
            if (stack.stackTop == stack.stackBottom) {
        
    
                System.out.println("关注公众号：Java3y---->该栈为空");
            } else {
        
    
                System.out.println("关注公众号：Java3y---->该栈不为空");
    
            }
    
        }

### 2.2.4出栈 ###

1.  在出栈之前看看该栈是否为空，不为空才出栈…
2.  将栈顶的元素的指针(指向下一个节点)赋值给栈顶指针(完成出栈)

/**     * 出栈(将栈顶的指针指向下一个节点)     * @param stack     */    public static void popStack(Stack stack) {        // 栈不为空才能出栈        if (!isEmpty(stack)) {            //栈顶元素            Node top = stack.stackTop;            // 栈顶指针指向下一个节点            stack.stackTop = top.next;            System.out.println("关注公众号：Java3y---->出栈的元素是：" + top.data);        }    }
        public static void popStack(Stack stack) {
        
    
            // 栈不为空才能出栈
            if (!isEmpty(stack)) {
        
    
                //栈顶元素
                Node top = stack.stackTop;
    
                // 栈顶指针指向下一个节点
                stack.stackTop = top.next;
    
                System.out.println("关注公众号：Java3y---->出栈的元素是：" + top.data);
    
            }
        }

测试出栈：

![640?wx\_fmt=png][640_wx_fmt_png 1]

多次出栈：

![640?wx\_fmt=png][640_wx_fmt_png 2]

### 2.2.5清空栈 ###

当时学C的时候需要释放内存资源，可是Java不用呀，所以栈顶指向栈底，就清空栈了

/**     * 清空栈     * @param stack     */    public static void clearStack(Stack stack) {        stack.stackTop = null;        stack.stackBottom = stack.stackTop;    }
        public static void clearStack(Stack stack) {
        
    
            stack.stackTop = null;
            stack.stackBottom = stack.stackTop;
        }

# 三、数据结构【队列】就是这么简单 #

数据结构的队列长的是这个样子：

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

其实队列非常好理解，我们将队列可以**看成小朋友排队**

相对于栈而言，队列的特性是：先进先出

队列也分成两种：

这次我就使用数组来实现静态队列了。值得注意的是：**往往实现静态队列，我们都是做成循环队列**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2]

做成循环队列的**好处是不浪费内存资源**！

## 3.1数据结构【队列】 代码实现 ##

这次我们使用的是数组来实现静态队列，因此我们可以这样设计：

public class Queue {    //数组    public int [] arrays;    //指向第一个有效的元素    public int front;    //指向有效数据的下一个元素(即指向无效的数据)    public int rear;}class Queue {
        
    
    
        //数组
        public int [] arrays;
    
        //指向第一个有效的元素
        public int front;
    
        //指向有效数据的下一个元素(即指向无效的数据)
        public int rear;
    
    }

从上面的设计我们可以发现：**rear并不指向最后一个有效的元素，在循环队列中这样设计是非常方便的**！因为这样设计可以**让我们分得清队头和队尾**(不然循环队列不断入队或出队，位置是变化很快的)

由于我们是循环队列，所以`front`和`rear`值会经常变动，我们得把`front`和`rear`的值限定在一个范围内，不然会超出队列的长度的。

有这么一个算法：`rear=（rear+1)%数组长度`

### 3.1.2初始化队列 ###

**此时队列为空，分配了6个长度给数组(只能装5个实际的数字，rear指向的是无效的位置的)**

public static void main(String[] args) {        //初始化队列        Queue queue = new Queue();        queue.front = 0;        queue.rear = 0;        queue.arrays = new int[6];    }
    
            //初始化队列
            Queue queue = new Queue();
    
            queue.front = 0;
            queue.rear = 0;
            queue.arrays = new int[6];
    
        }

### 3.1.3判断队列是否满了 ###

如果rear指针和front指针紧挨着，那么说明队列就满了

/**     * 判断队列是否满了，front和rear指针紧挨着，就是满了     * @param queue     * @return     */    public static boolean isFull(Queue queue) {        if ((queue.rear + 1) % queue.arrays.length == queue.front) {            System.out.println("关注公众号：Java3y--->此时队列满了！");            return true;        } else {            System.out.println("关注公众号：Java3y--->此时队列没满了！");            return false;        }    }
        public static boolean isFull(Queue queue) {
        
            if ((queue.rear + 1) % queue.arrays.length == queue.front) {
        
    
                System.out.println("关注公众号：Java3y--->此时队列满了！");
                return true;
            } else {
        
                System.out.println("关注公众号：Java3y--->此时队列没满了！");
                return false;
            }
        }

### 3.1.4入队 ###

1.  判断该队列是否满了
2.  入队的值插入到队尾中(具体的位置就是rear指针的位置【再次声明：rear指向的是无效元素的位置】
3.  rear指针移动(再次指向无效的元素位置)

/**     * 入队     *     * @param queue     */    public static void enQueue(Queue queue,int value) {        // 不是满的队列才能入队        if (!isFull(queue)) {            // 将新的元素插入到队尾中            queue.arrays[queue.rear] = value;            // rear节点移动到新的无效元素位置上            queue.rear = (queue.rear + 1) % queue.arrays.length;        }    }
        public static void enQueue(Queue queue,int value) {
        
    
            // 不是满的队列才能入队
            if (!isFull(queue)) {
        
    
                // 将新的元素插入到队尾中
                queue.arrays[queue.rear] = value;
    
                // rear节点移动到新的无效元素位置上
                queue.rear = (queue.rear + 1) % queue.arrays.length;
            }
        }

### 3.1.5遍历 ###

**只要front节点不指向rear节点，那么就可以一直输出**

/**     * 遍历队列     * @param queue     *     */    public static void traverseQueue(Queue queue) {        // front的位置        int i = queue.front;        while (i != queue.rear) {            System.out.println("关注公众号：Java3y--->" + queue.arrays[i]);            //移动front            i = (i + 1) % queue.arrays.length;        }    }
        public static void traverseQueue(Queue queue) {
        
    
            // front的位置
            int i = queue.front;
    
            while (i != queue.rear) {
        
    
                System.out.println("关注公众号：Java3y--->" + queue.arrays[i]);
    
                //移动front
                i = (i + 1) % queue.arrays.length;
            }
    
        }

队列没满时：

![640?wx\_fmt=png][640_wx_fmt_png 3]

队列已满了就插入不了了(验证上面的方法是否正确)：

![640?wx\_fmt=png][640_wx_fmt_png 4]

### 3.1.6判断该队列是否为空 ###

只要`rear`和`front`指针指向同一个位置，那该队列就是空的了

/**     * 判断队列是否空，front和rear指针相等，就是空了     * @param queue     * @return     */    public static boolean isEmpty(Queue queue) {        if (queue.rear  == queue.front) {            System.out.println("关注公众号：Java3y--->此时队列空的！");            return true;        } else {            System.out.println("关注公众号：Java3y--->此时队列非空！");            return false;        }    }
        public static boolean isEmpty(Queue queue) {
        
            if (queue.rear  == queue.front) {
        
                System.out.println("关注公众号：Java3y--->此时队列空的！");
                return true;
            } else {
        
                System.out.println("关注公众号：Java3y--->此时队列非空！");
                return false;
            }
        }

### 3.1.7出队 ###

出队的逻辑也非常简单：

1.  判断该队列是否为null
2.  如果不为null，则出队，**只要front指针往后面移就是出队了**!

/**     * 出队     *     * @param queue     */    public static void outQueue(Queue queue) {        //判断该队列是否为null        if (!isEmpty(queue)) {            //不为空才出队            int value = queue.arrays[queue.front];            System.out.println("关注公众号：Java3y--->出队的元素是：" + value);            // front指针往后面移            queue.front = (queue.front + 1) % queue.arrays.length;        }    }
        public static void outQueue(Queue queue) {
        
    
            //判断该队列是否为null
            if (!isEmpty(queue)) {
        
    
    
                //不为空才出队
                int value = queue.arrays[queue.front];
                System.out.println("关注公众号：Java3y--->出队的元素是：" + value);
    
                // front指针往后面移
                queue.front = (queue.front + 1) % queue.arrays.length;
    
            }
    
    
        }

结果：

![640?wx\_fmt=png][640_wx_fmt_png 5]

# 四、总结 #

数据结构的栈和队列的应用非常非常的多，这里也只是最简单的入门，理解起来也不困难。

关于数据结构这方面我就到暂时到这里为止了，都简单的入个门，以后遇到更加复杂的再继续开新的文章来写～毕竟现在水平不够，也无法理解更深层次的东西～数据结构这东西是必备的，等到研究集合的时候还会来回顾它，或者遇到新的、复杂的也会继续学习….

想要更加深入数据结构的同学就得去翻阅相关的书籍咯～这仅仅是冰山一角

> 如果文章有错的地方欢迎指正，大家互相交流。习惯在微信看技术文章，想要获取更多的Java资源的同学，可以**关注微信公众号:Java3y**

[Java]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484086&idx=1&sn=24127ceb5e0fed7f832f82579c4fbc19&chksm=ebd743b7dca0caa1dce912d47251548225aa59b4b48742a963ac52b05e13ec923a738ebcb836&scene=21#wechat_redirect
[640_wx_fmt_jpeg]: /images/20210827/680b03f4c451440bba5ac5a456505db0.png?wx_fmt=jpeg
[640_wx_fmt_png]: /images/20210827/ea953500707c4b0a97ce1bc8f1da9c24.png?wx_fmt=png
[640_wx_fmt_png 1]: /images/20210827/34c30d5d66cc4034b46ffb29087da142.png?wx_fmt=png
[640_wx_fmt_png 2]: /images/20210827/1e609cf3959545399765dbbafa85f08d.png?wx_fmt=png
[640_wx_fmt_jpeg 1]: /images/20210827/79fdca9f5a2f44ba8d002c0a6b7bdaaf.png?wx_fmt=jpeg
[640_wx_fmt_jpeg 2]: /images/20210827/fd78965bcd494c95bfb86d25ecb87ddc.png?wx_fmt=jpeg
[640_wx_fmt_png 3]: /images/20210827/94f405c8f59241a793e04c3d0e6ffd53.png?wx_fmt=png
[640_wx_fmt_png 4]: /images/20210827/561f31d2bb964c5abe1e4a851ca09bb3.png?wx_fmt=png
[640_wx_fmt_png 5]: /images/20210827/376e258da65347e69b1fcd32c05180df.png?wx_fmt=png