数据结构奇妙旅程之栈和队列

这篇具有很好参考价值的文章主要介绍了数据结构奇妙旅程之栈和队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱
ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客
本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶
个人主页:xiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客
系列专栏:xiaoxie的JAVA系列专栏——CSDN博客●'ᴗ'σσணღ*
我的目标:"团团等我💪( ◡̀_◡́ ҂)" 

( ⸝⸝⸝›ᴥ‹⸝⸝⸝ )欢迎各位→点赞👍 + 收藏⭐️ + 留言📝​+关注(互三必回)!

数据结构奇妙旅程之栈和队列,Java,数据结构,java

 一.栈(Stack)

1.概念

:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈

顶,另一端称为栈底。栈中的数据元素遵守后进先出 LIFO Last In First Out )的原则。
压栈:栈的插入操作叫做进栈 / 压栈 / 入栈, 入数据在栈顶
出栈:栈的删除操作叫做出栈。 出数据在栈顶

2.栈的模拟实现

数据结构奇妙旅程之栈和队列,Java,数据结构,java

可以看出栈Stack 是继承与Vector的, Vector和ArrayList类似,我们可以得到以下的栈的模拟实现,帮助我们更好的理解栈的使用。

//这是栈内存储Integer的模拟,当然栈是泛型,这里只是Integer的模拟
class MyStack {
    public int[] arr;
    public int size;
    public MyStack() {
     arr = new int[10];
    }
    //入栈
    public int push(int e) {
        ensureCapacity();
        arr[size++] = e;
        return e;
    }
    //判断栈是否满
    private void ensureCapacity() {
        if (size == arr.length) {
            arr = Arrays.copyOf(arr, size * 2);
        }
    }
    //栈顶元素
    public int peek() {
        if(empty()) {
            System.out.println("栈为空,无元素");
            return -1;
        }
        return arr[size-1];
    }
    //出栈
    public int pop() {
        int tmp = peek();
        size--;
        return tmp;
    }
    //判断栈是否为空
    public boolean empty() {
        return this.size == 0;
    }

}

3.栈、虚拟机栈、栈帧有什么区别呢

栈、虚拟机栈和栈帧是计算机科学中的概念,它们之间有以下区别:

  1. 栈:栈是一种具有后进先出(Last-In-First-Out,LIFO)特性的数据结构,可以存储和检索数据。在计算机中,栈通常用于管理函数调用和局部变量的分配。栈在内存中是连续存储的一块区域,主要用于存储函数调用的上下文信息以及局部变量。

  2. 虚拟机栈:虚拟机栈是Java虚拟机(JVM)为每个线程分配的内存区域,用于存储方法的调用和执行信息。每个线程在执行方法时,都会在虚拟机栈中创建一个栈帧,栈帧中包含了方法的局部变量、操作数栈、方法返回地址等信息。

  3. 栈帧:栈帧是方法在虚拟机栈中的表示,用于存储方法的局部变量、操作数栈、方法返回地址等信息。每个方法在执行时,都会在虚拟机栈中创建一个对应的栈帧,方法的参数、局部变量以及中间计算结果都存储在栈帧中。当方法执行完毕后,对应的栈帧就会被销毁。

总结来说,栈是一种数据结构,用于存储和检索数据;虚拟机栈是Java虚拟机为每个线程分配的内存区域,用于存储方法的调用和执行信息;栈帧是方法在虚拟机栈中的表示,用于存储方法的局部变量、操作数栈、方法返回地址等信息。

 4.栈的应用

155.最小栈

 数据结构奇妙旅程之栈和队列,Java,数据结构,java

题目分析:

我们都知道栈是一个先进后出的数据结构,所以我们只使用一个普通栈是无法实现最小栈,应该要用两个栈来模拟实现最小栈。

数据结构奇妙旅程之栈和队列,Java,数据结构,java

如果两个栈都为空就先将元素入栈

数据结构奇妙旅程之栈和队列,Java,数据结构,java

然后下一个元素先入stack 栈 之后和minstack 比较如果 < minstack的栈顶元素,就入 minstack 否则就不入,

数据结构奇妙旅程之栈和队列,Java,数据结构,java

这样就通过用两个普通栈模拟最小栈了

class MinStack {
     Stack<Integer> stack;
     Stack<Integer> minstack;
    public MinStack() {
        stack = new Stack<>();
        minstack = new Stack<>();
    }
    public void push(int val) {
        stack.push(val);
        if(minstack.empty()) {
            minstack.push(val);
        }else {
            if(minstack.peek() >= val) {
                minstack.push(val);
            }
        }
    }
    
    public void pop() {
        int tmp = stack.pop();
        if(tmp == minstack.peek()) {
            minstack.pop();
        }
    }
    
    public int top() {
      return stack.peek();
    }
    
    public int getMin() {
       return minstack.peek();
    }
}

 1.面试进阶

是否可以不用辅助栈呢

 栈中每个元素代表的是要压入元素与当前栈中最小值的差值 有个很重要问题: 在弹出时如何维护min? 因为每次压入新的元素时,压入的都是与当前栈中最小值的差值(还未压入当前元素),故在弹出元素时,若弹出了当前最小值,因为栈中记录了当前元素与【之前】最小值的差值,故根据这个记录可以更新弹出元素后的最小值。 接下来看代码吧

class MinStack {
    // 记录每个元素与【未压入】该元素时栈中最小元素的差值
    LinkedList<Long> stack;
    // 当前【已压入】栈中元素的最小值
    private long min;
    public MinStack() {
        stack = new LinkedList();
    }
    
    public void push(int val) {
        // 压入第一个元素
        if(stack.isEmpty()){
            min = val;
            stack.addFirst(0L);
            return;
        }
        // 栈不为空时,每次压入计算与min的差值后压入结果
        stack.push((long)val-min);
        // 更新min
        min = Math.min((long)val,min);
        // 上面两个语句是不能颠倒的!一定是先压入,在更新,因为min一定是当前栈中的最小值
    }
    
    public void pop() {
        long pop = stack.removeFirst();
        // 当弹出元素小于0时,说明弹出元素是当前栈中的最小值,要更新最小值
        if(pop<0){
            // 因为对于当前弹出的元素而言,计算压入栈中的值时,计算的是该元素与【未压入】该元素时
            // 栈中元素的最小值的差值,故弹出该元素后栈中的最小值就是未压入该元素时的最小值
            // 即当前元素的值(min)减去两者的差值
            long lastMin = min;
            min = lastMin - pop;
        }
        // 若大于等于0,不会对min有影响
    }
    
    public int top() {
        long peek = stack.peek();
        // 若当前栈顶小于等于0,说明最小值就是栈顶元素
        if(peek<=0) return (int)min;
        // 否则就是min+peek
        return (int)(min+peek);
    }
    
    public int getMin() {
        return (int)min;
    }
}

二.队列

1.概念

队列 :只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 FIFO(First
In First Out) 入队列:进行插入操作的一端称为 队尾( Tail/Rear 出队列:进行删除操作的一端称为 队头 Head/Front

2.队列的模拟实现

public class Queue {

    private int maxSize;
    private int[] queueArray;
    private int front;
    private int rear;
    private int nItems;

    public Queue(int size) {
        maxSize = size;
        queueArray = new int[maxSize];
        front = 0;
        rear = -1;
        nItems = 0;
    }

    public void insert(int value) {
        if (rear == maxSize - 1) {
            rear = -1;
        }
        queueArray[++rear] = value;
        nItems++;
    }

    public int remove() {
        int temp = queueArray[front++];
        if (front == maxSize) {
            front = 0;
        }
        nItems--;
        return temp;
    }

    public int peek() {
        return queueArray[front];
    }

    public boolean isEmpty() {
        return (nItems == 0);
    }

    public boolean isFull() {
        return (nItems == maxSize);
    }

    public int size() {
        return nItems;
    }

}
 

  三.面试题

 用队列实现栈

大家都清楚栈是先进后出,队列是先进先出的数据结构,如果要用队列模拟实现栈,仅靠一个队列是无法实现,需要用到两个队列,来模拟模拟实现栈

数据结构奇妙旅程之栈和队列,Java,数据结构,java                                                                                                                                  

如果两个队列都为空 就入q1 的队

数据结构奇妙旅程之栈和队列,Java,数据结构,java

谁不为空就入队那个队列,如果要出栈的话,就把除了要出栈的那个元素之外的元素,入到另一个 队列中。

数据结构奇妙旅程之栈和队列,Java,数据结构,java

 代码如下

class MyStack {
   Queue<Integer> q1;
   Queue<Integer> q2;
    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public void push(int x) {
        if(empty()) {
            q1.add(x);
            return;
        }if( ! q1.isEmpty()) {
            q1.add(x);
        }else {
            q2.add(x);
        }
    }

    public int pop() {
        if(empty()) return -1;
        if(!q1.isEmpty()) {
            int size1 = q1.size();
            for (int i = 0;i < size1-1;i++) {
                q2.add(q1.poll());
            }
            return q1.poll();
        }else {
            int size2 = q2.size();
            for (int i = 0; i < size2-1; i++) {
                q1.add(q2.poll());
            }
            return q2.poll();
        }
    }

    public int top() {
        if(empty()) {
            return -1;
        }int temp = -1;
        if(!q1.isEmpty()) {
            int size2 = q1.size();
            for(int i = 0; i < size2;i++) {
                temp = q1.poll();
                q2.offer(temp);
            }
            return temp;
        }else {
                 int size2 = q2.size();
                for(int i = 0;i < size2; i++) {
                   temp = q2.poll();
                   q1.offer(temp);
                }
            return temp;
        }
    }
    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }
}

用栈实现队列

栈实现队列的出队操作效率低下:栈底元素(对应队首元素)无法直接删除,需要将上方所有元素出栈。

两个栈可实现将列表倒序:设有含三个元素的栈 A = [1,2,3] 和空栈 B = [] 。若循环执行 A 元素出栈并添加入栈 B ,直到栈 A 为空,则 A = [] , B = [3,2,1] ,即栈 B 元素为栈 A 元素倒序。

利用栈 B 删除队首元素:倒序后,B 执行出栈则相当于删除了 A 的栈底元素,即对应队首元素。

因此,可以设计栈 A 用于加入队尾操作,栈 B 用于将元素倒序,从而实现删除队首元素。

数据结构奇妙旅程之栈和队列,Java,数据结构,java

代码如下

class MyQueue {
    Stack<Integer> s1;
    Stack<Integer> s2;
    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }
    public void push(int x) {
        s1.push(x);
    }
    public int pop() {
        if(s2.empty()) {
            while(!s1.empty()) {
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    public int peek() {
        if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
    public boolean empty() {
        return s1.empty() && s2.empty();
    }
}

以上就是栈和队列的所有内容了,在这里博主还是要说一句,要想理解栈和队列还是要多多刷类似的题目,一定可以更好的理解他们的使用文章来源地址https://www.toymoban.com/news/detail-761154.html

到了这里,关于数据结构奇妙旅程之栈和队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 高效学习数据结构之栈和队列篇(五千字超详细教程)

    大家好呀我是小生🙉🙊🙈今天我们来学习 数据结构的栈和队列 ,小生为了方便大家理解特意附上了 许多图片和源码 一起加油吧 🥳🥳🥳   下面是我们今天要学习的内容 🥳🥳🥳  一.栈          1.🏠栈的基本概念 ​2.🏠栈的结构选择 🚀顺序表和链表的优缺点对比:

    2023年04月08日
    浏览(69)
  • 数据结构之栈和队列 - 超详细的教程,手把手教你认识并运用栈和队列

    栈:后进先出 队列:先进先出 栈:是一种特殊的 线性表 , 只允许在固定的一端插入或者删除元素 ,一个栈包含了栈顶和栈底。只能在栈顶插入或者删除元素。 栈的底层 是由 数组 实现的。 栈遵循先入后出原则,也就是先插入的元素得到后面才能删除,后面插入的元素比

    2024年02月07日
    浏览(83)
  • 数据结构奇妙旅程之冒泡排序

    冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。 这个算法的名字由来是因为越小的元素会经由交换慢

    2024年03月26日
    浏览(41)
  • 数据结构奇妙旅程之红黑树

    ꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶ 个人主页:xiaoxieʕ̯

    2024年03月21日
    浏览(46)
  • 数据结构奇妙旅程之二叉树初阶

    ꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶ 个人主页:xiaoxieʕ̯

    2024年01月19日
    浏览(64)
  • 数据结构奇妙旅程之顺序表和链表

    ꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶ 个人主页:xiaoxieʕ̯

    2024年02月05日
    浏览(67)
  • 数据结构奇妙旅程之二叉平衡树

    ꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶ 个人主页:xiaoxieʕ̯

    2024年03月11日
    浏览(58)
  • 《数据结构》之栈和堆结构及JVM简析

    在数据结构中,我们第一了解到了栈或堆栈,它的结构特点是什么呢?先进后出,它的特点有什么用呢?我们在哪里可以使用到栈结构,栈结构那么简单,使用这么久了为什么不用其它结构替代? 作为一个程序猿,我们应该会常常跟代码打交道,那么我们所编写的程序或代码

    2024年02月07日
    浏览(51)
  • 数据结构奇妙旅程之二叉平衡树进阶---AVL树

    ꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶ 个人主页:xiaoxieʕ̯

    2024年03月13日
    浏览(83)
  • 【数据结构】线性表之栈、队列

    前面两篇文章讲述了关于线性表中的顺序表与链表,这篇文章继续讲述线性表中的 栈和队列。 这里讲述的两种线性表与前面的线性表不同,只允许在一端入数据,一段出数据,详细内容请看下面的文章。 顺序表与链表两篇文章的链接: 线性表之顺序表 线性表之链表 注意:

    2024年02月06日
    浏览(62)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包