[详解栈和队列]数据结构之栈与队列

✅作者简介：大家好,我是Philosophy7？让我们一起共同进步吧！? ?个人主页：Philosophy7的csdn博客
?系列专栏： ?哲学语录: 承认自己的无知，乃是开启智慧的大门
?如果觉得博主的文章还不错的话，请点赞?+收藏⭐️+留言?支持一下博>主哦?

栈和队列

1.物理结构和逻辑结构

再了解栈和队列之前，我们要先知道什么是逻辑结构和物理结构。

逻辑结构:

按照逻辑结构划分:数据结构可分为线性结构和非线性接口

线性结构就包括:顺序表、栈、队列

非线性结构:树、图

物理结构:

按照物理结构划分:数据结构可分为顺序存储结构、链式存储结构

顺序存储结构我们常见的就有:数组

链式存储结构:链表

举个栗子:

比如说人的精神、思想是看不见的摸不着的，为什么你能感受到他的一个精神和思想呢，肯定是通过你所能看得见的。

就比如说通过他这个人的言行举止，你就可以发现这个人确实是大佬。

所以逻辑结构是抽象的概念，它依赖于物理结构而存在。

下面我们就来介绍栈和队列，这两种是属于逻辑结构的，它们的物理结构依赖于数组或链表。

2.什么是栈

大家打过手枪的都知道，手枪的弹匣就是一种栈的结构,是一种先进后出的一种结构，例如:最先装进弹匣里的子弹是最后才能打出来的，而最后一颗装进弹匣里的是最先打出来的。

所以栈是一种线性的数据结构，栈中的元素只能先进后出。最早进入的元素存放的叫做栈底，最后进入元素存放的位置叫作栈顶。

2.1栈的基本操作

1. 入栈
   • 入栈的操作就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶。
2. 出栈
   • 出栈就是将元素从栈顶弹出，弹出之后，栈顶自然是原先栈顶元素的前一个元素了。

这里我们基于数组的方式实现

package com.philosophy7.stack;
/*
    基于数组实现栈
 */

/**
 * @author Philosophy7
 */
public class MyStack {
    public static void main(String[] args) {
        MyStack myStack = new MyStack(5);
        myStack.push(5);
        myStack.push(4);
        myStack.push(3);

        System.out.println("出来的元素是:" + myStack.pop());
        myStack.list();
    }
    private int size; //栈的大小
    private int[] stack; //数组充当栈
    private int top = -1; //栈顶 初始化-1 数组的索引是从0开始 入栈操作是从栈顶往下放入元素

    public MyStack(int size){
        this.size = size;
        stack = new int[size];
    }

    //首先判断栈是否还能存储
    public boolean isFull(){
        return top == size - 1;
    }

    //栈空
    public boolean isEmpty(){
        return top == -1;
    }

    //入栈
    public void push(int element){
        //1.首先判断栈是否满了
        if (isFull()){
            System.out.println("满了哦");
            return;
        }
        //2.否则将数据插入
        top++;
        stack[top] = element;
    }

    //出栈
    public Integer pop(){
        int value;
        //1.首先判断栈是否有元素可出
        if (isEmpty()){
            System.out.println("栈空了 出个屁啊");
            return null;
        }
        value = stack[top];
        top--;
        return value;
    }

    //遍历栈 从栈顶往栈底遍历
    public void list(){
        if (isEmpty()){
            System.out.println("栈空了 出个屁啊");
            return;
        }
        for (int i = top; i >= 0; i--){
            System.out.println(stack[i]);
        }
    }
}

3.什么是队列

就比如说这张排队买火车票的示例来说，最先排队的人最先买到票，买到票也就可以直接提桶跑路了，也就不需要继续等待了，后面的人要想买到票只能等待前面的人买完了才能轮到他自己，否则的话是要一直等待下去的。有的小伙伴看到这里就会想，我可以插队啊！！在这里我只想说小伙子路还长，大好青春可不能就此结束啊！！

所以队列也属于逻辑结构，是一种线性数据结构，它的特征当然是先进先出啦，队列的出口端叫作队头，队列的入口端叫作队尾

队列的基本操作

1. 入队
   • 入队就是将新元素放入队列中，只允许在队尾的位置放入元素，新元素的下一个位置将会成为队尾。
2. 出队
   • 出队操作就是把元素移除队列，只允许在队头的一端移出元素，出队元素的后一个元素将会成为新的队头。

package com.philosophy7.queue;

/**
 * @author Philosophy7
 */
public class MyQueue {
    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue(5);
        myQueue.enQueue(1);
        myQueue.enQueue(2);
        myQueue.enQueue(3);

        System.out.println("出队的元素是:" + myQueue.deQueue());

        myQueue.list();
    }
    private int[] queue; //基于数组充当队列
    private int front; //队头
    private int rear; //队尾 元素的入口
    private int count; //计数器

    //判断队列是否满
    public boolean isFull(){
        if (count > 0 & front == rear){
            return true;
        }else{
            return false;
        }
    }

    //判断栈是否为空
    public boolean isEmpty(){
        if (count == 0){
            return true;
        }else{
            return false;
        }
    }

    //返回队列容量
    public int size(){
        return queue.length;
    }

    public MyQueue(int capacity){
        this.queue = new int[capacity];
    }

    //入队
    public void enQueue(int element){
        //1.判断队列是否还能容纳元素
        if (isFull()){
            System.out.println("排队的人太多了 容纳不下了");
            return;
        }
        //2.入队操作
        queue[rear] = element;
        rear++;
        if (rear == queue.length)rear=0; //队尾＝队列中的容纳数后 将队尾设置为0
        count++;
    }

    //出队
    public int deQueue(){
        int value = 0;
        if (isEmpty()){
            System.out.println("队列中没有元素");
            return 0;
        }
        //2.出队操作
        value = queue[front];
        front++;
        if (front == queue.length)front=0;
        count--;
        return value;
    }

    //遍历队列
    public void list(){
        if (isEmpty()){
            return;
        }
        for (int i = 0; i < queue.length; i++){
            System.out.println(queue[i]);
        }
    }
}

小结

数据结构能够按照逻辑结构和物理结构划分

逻辑结构:线性结构和非线性结构

物理结构:顺序存储和链式存储结构

栈: 一种先入后出的数据结构，最早进入栈中的元素为栈底，最后进入栈中的元素为栈顶

队列:一种先入先出的数据结构，队列的出口叫作队头，队列的入口叫做队尾。

栈的移动只会影响到最后一个元素，不会整体的移动元素。

队列的移动同样也不会影响到整体元素，所以不管是数组还是链表它们的入栈出栈 入队出队操作的时间复杂度是O(1)

点赞?+关注?+收藏⭐