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

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

文章目录

• • 栈和队列
  • • 1.物理结构和逻辑结构
    • 2.什么是栈
    • 2.1栈的基本操作
    • 3.什么是队列
    • 队列的基本操作
    • 小结

栈和队列

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)

点赞👍+关注💖+收藏⭐