Java 栈与队列实战真题训练

目录
  • 1、实现循环队列
    • (1)数组下标实现循环
    • (2)区分队列的满与空
  • 2、队列实现栈
  • 3、栈实现队列
  • 4、实现最小栈

1、实现循环队列

【OJ链接】

循环队列一般通过数组实现。我们需要解决几个问题。

(1)数组下标实现循环

a、下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length。通俗一点,就是如果我们的数组大小为8,下标走到了7,再往后如何回到0,我们可以(index+1)%8来实现。

b、下标最前再往前的时候,我们特殊判断一下,将其置为数组大小减一即可。

(2)区分队列的满与空

我们可以给数组预留一个位置,如果rear+1=front,则表示队列已满;如果rear=front,表示队列为空。这个情况下,我们需要考虑队列大小的问题,在定义数组大小时,需要比原有的大一。

【代码如下】

class MyCircularQueue {
    public int front;
    public int rear;
    public int[] array;

    //构造方法
    public MyCircularQueue(int k) {
       //因为预留位置的缘故,数组的大小要定义为k+1
       this.array=new int[k+1];
    }
    //入队
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        this.array[this.rear]=value;
        this.rear=(this.rear+1)%this.array.length;
        return true;
    }
    //出队
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        this.front=(this.front+1)%this.array.length;
        return true;
    }
    //获取队头
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return this.array[front];
    }
    //获取队尾
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        int index=-1;
        if(this.rear==0){
            index=this.array.length-1;
        }else{
            index=this.rear-1;
        }
        return this.array[index];
    }
    //判断是否为空
    public boolean isEmpty() {
        if(this.front==this.rear){
            return true;
        }
        return false;
    }
    //判断队列是否满
    public boolean isFull() {
        if((this.rear+1)%this.array.length==this.front){
            return true;
        }
        return false;
    }
}

2、队列实现栈

【OJ链接】

因为栈的先进后出、队列的先进先出原则。我们需要两个队列来实现栈。当两个队列都为空时,栈为空。

  • 入栈(push):第一次入栈无所谓,两个队列都为空,随便选择一个队列入队即可;后面入栈时,肯定会有一个队列不为空,找到不为空的队列,进行入队操作。
  • 出栈(pop):首先栈为空时,不能进行出栈操作;栈不为空时,肯定有一个队列为空(queue1),一个队列不为空(queue2),将queue1中的size-1个元素出栈到queue2中(特别注意不能将求queue1大小的函数放进循环里,queue进行出队操作时,其大小是改变的),最后将queue1中最后一个元素进行出队最为返回值。
  • 获取栈顶元素(top):和出栈差不多,就不细说了

【代码如下】

class MyStack {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    //构造方法
    public MyStack() {
        queue1=new LinkedList<>();
        queue2=new LinkedList<>();
    }
    //入栈
    public void push(int x) {
        if(!queue2.isEmpty()){
            queue2.offer(x);
        }else{
            queue1.offer(x);
        }
    }
    //出栈
    public int pop() {
        if(empty()){
            return -1;
        }
        if(queue1.isEmpty()){
            int size=queue2.size();
            for(int i=0;i<size-1;++i){
                int x=queue2.poll();
                queue1.offer(x);
            }
            return queue2.poll();
        }else{
            int size=queue1.size();
            for(int i=0;i<size-1;++i){
                int x=queue1.poll();
                queue2.offer(x);
            }
            return queue1.poll();
        }
    }
    //获取栈顶元素
    public int top() {
        if(empty()){
            return -1;
        }
        if(queue1.isEmpty()){
            int x=-1;
            int size=queue2.size();
            for(int i=0;i<size;++i){
                x=queue2.poll();
                queue1.offer(x);
            }
           return x;
        }else{
            int size=queue1.size();
            int x=-1;
            for(int i=0;i<size;++i){
                x=queue1.poll();
                queue2.offer(x);
            }
            return x;
        }
    }
    //判断栈是否为空
    public boolean empty() {
        if(queue1.isEmpty()&&queue2.isEmpty()){
            return true;
        }
        return false;
    }
}

3、栈实现队列

【OJ链接】

还是和上面一样,需要用到两个栈(stack1、stack2)。和实现栈列不同的是,入队只能对同一个栈进行操作。如果两个栈都为空,则队列为空。

  • 入队(push):规定stack1用来入队。每次入队时,对stack1进行入栈操作即可。
  • 出队(pop):规定stack2进行出队操作。如果队列为空时,不能进行出队操作。当stack2为空时,我们需要将stack1中所有元素出栈,放入stack2中,然后对stack2进行出栈操作。如果stack2不为空,则直接对stack2进行出栈操作即可。
  • 获取队列开头元素(peek):和出栈操作相同,最后只需要获取stack2的栈顶元素即可。

【代码如下】

class MyQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    //构造方法
    public MyQueue() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }
    //入队操作
    public void push(int x) {
        stack1.push(x);
    }
    //出队操作
    public int pop() {
        if(stack2.empty()){
            int size=stack1.size();
            for(int i=0;i<size;++i){
                int x=stack1.pop();
                stack2.push(x);
            }
        }
        return stack2.pop();

    }
    //获取队列开头的元素
    public int peek() {
        if(stack2.empty()){
            int size=stack1.size();
            for(int i=0;i<size;++i){
                int x=stack1.pop();
                stack2.push(x);
            }
        }
        return stack2.peek();
    }
    //判断队列是否为空
    public boolean empty() {
        if(stack1.empty()&&stack2.empty()){
            return true;
        }
        return false;
    }
}

4、实现最小栈

【OJ链接】

其实就是要在O(1)的时间复杂度内找到栈的最小元素。需要两个栈来实现,一个栈来进行出栈、入栈操作。只需要保证不管如何操作,另一个栈的栈顶元素都是当前栈的最小元素即可。

两个栈stack1、stack2,站的操作都在stack1中:

  • 入栈:如果第一次入栈,我们需要将其也放入stack2中,之后的入栈,将入栈元素与stack2的栈顶元素进行比较,如果其小于stack2的栈顶元素,则将其放入stack2中。
  • 出栈:对stack1出栈时,将其与stack2的栈顶元素进行比较,如果其等于stack2的栈顶元素,则对stack2进行出栈操作。

这样就能保证stack2的栈顶元素总是stack1的最小元素。注意:如果stack1中入栈两个相同的最小元素,都需要对stack2进行入栈。

【代码如下】

class MinStack {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    //构造方法
    public MinStack() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }
    //入栈
    public void push(int val) {
        stack1.push(val);
        if(stack2.empty()){
            stack2.push(val);
        }else{
            if(val<=stack2.peek()){
                stack2.push(val);
            }
        }
    }
    //出栈
    public void pop() {
        int x=stack1.pop();
        if(x==stack2.peek()){
            stack2.pop();
        }
    }
    //获取栈顶元素
    public int top() {
        return stack1.peek();
    }
    //获取栈的最小元素
    public int getMin() {
        return stack2.peek();
    }
}

到此这篇关于Java 栈与队列实战真题训练的文章就介绍到这了,更多相关Java 栈与队列内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java 栈和队列的相互转换详解

    目录 用栈实现队列-力扣232题 用队列实现栈-力扣225题  1. 双队列实现栈 2.一个队列实现栈 栈和队列的本质是相同的,都只能在线性表的一端进行插入和删除.因此,栈和队列可以相互转换. 用栈实现队列-力扣232题 题目要求:仅使用两个栈实现先入先出队列.队列应当支持一般队列支持的所有操作 使用双栈来实现队列,我们就可以让一个栈储存具体元素,另一个栈做辅助  上图可以看到,新元素进栈时,要确保该栈为空.进入栈的元素按顺序存到辅助栈中,等新元素进入栈之后,再将辅助栈中的元素按顺序出到该栈中.

  • Java深入了解数据结构之栈与队列的详解

    目录 一,栈 1,概念 2,栈的操作 3,栈的实现 ①入栈 ②出栈 ③获取栈顶元素 ④判断栈是否为空 4,实现mystack 二,队列 1,概念 2,队列的实现 ①入队 ②出队 ③获取队首元素 3,实现myqueue 一,栈 1,概念 在我们软件应用 ,栈这种后进先出数据结构的应用是非常普遍的.比如你用浏 览器上网时不管什么浏览器都有 个"后退"键,你点击后可以接访问顺序的逆序加载浏览过的网页. 很多类似的软件,比如 Word Photoshop 等文档或图像编 软件中 都有撤销 )的

  • Java数据结构之栈与队列实例详解

    目录 一,栈 1,概念 2,栈的操作 3,栈的实现  4,实现mystack 二,队列 1,概念  2,队列的实现  3,实现myqueue 栈.队列与数组的区别? 总结 一,栈 1,概念 在我们软件应用 ,栈这种后进先出数据结构的应用是非常普遍的.比如你用浏 览器上网时不管什么浏览器都有 个"后退"键,你点击后可以接访问顺序的逆序加载浏览过的网页.   很多类似的软件,比如 Word Photoshop 等文档或图像编 软件中 都有撤销 )的操作,也是用栈这种方式来实现的,当然不同的

  • 一起来学习Java的栈和队列

    目录 栈 队列 阻塞队列 双端队列 总结 栈 package com.yuzhenc.collection; import java.util.Stack; /** * @author: yuzhenc * @date: 2022-03-20 15:41:36 * @desc: com.yuzhenc.collection * @version: 1.0 */ public class Test26 { public static void main(String[] args) { Stack

  • Java栈和基础队列的实现详解

    目录 栈(stack) 栈支持的三个核心操作: 栈的常见实际应用: 栈的实现 队列 无论是哪种队列,都必须支持三个核心操作: 基础队列的实现 栈和队列:都是线性表,都是基于List基础上的实现 线性表:数组,链表,字符串,栈,队列 元素按照一条“直线”排列,线性表这个结构中,一次添加单个元素 栈(stack) 一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作.进行数据插入和删除操作的一端称为栈顶,另一端称为栈底.栈中的数据元素遵守后进先出LIFO(Last In First Out)

  • Java数据结构专题解析之栈和队列的实现

    目录 1. 栈 1.1 概念 1.2 助解图题 1.3 栈的数组实现 1.4 问题 1.5 栈的单链表实现 2. 队列 2.1 概念 2.2 问题 2.3 队列的单链表实现 2.4 数组实现队列 2.5 循环队列 2.6 双端队列 3. 栈和队列练习题 3.1 有效的括号 3.2 用队列实现栈 3.3 用栈实现队列 3.4 实现一个最小栈 3.5 设计循环队列 1. 栈 1.1 概念 栈:是一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作. 特点:栈中的数据元素遵循先进后出的原则,但

  • Java 栈与队列实战真题训练

    目录 1.实现循环队列 (1)数组下标实现循环 (2)区分队列的满与空 2.队列实现栈 3.栈实现队列 4.实现最小栈 1.实现循环队列 [OJ链接] 循环队列一般通过数组实现.我们需要解决几个问题. (1)数组下标实现循环 a.下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length.通俗一点,就是如果我们的数组大小为8,下标走到了7,再往后如何回到0,我们可以(index+1)%8来实现. b.下标最前再

  • Java 链表实战真题训练

    目录 1.删除值为val的所有节点 2.反转链表 3.返回链表中间节点 4.返回链表第K个节点 5.合并有序链表 6.按值分割链表 7.判读回文链表 8.找两个链表的公共节点 9.判断成环链表 10.返回成环链表的入口 每个题目后面有放对应题目的OJ链接,大家可以先了解一下解题思路,然后自己先去做一下. 1.删除值为val的所有节点 删除链表中等于给定值val的所有节点.[OJ链接] 定义两个指针prev.cur,cur指向头节点的下一个节点,prev始终指向cur的前一个结点(方便删除节点).

  • Java数组与二维数组及替换空格实战真题讲解

    目录 数组中重复的数字 题目描述 思路详解 代码与结果 二维数组中的查找 题目描述 思路详解 代码与结果 替换空格 题目描述 思路详解 代码与结果 数组中重复的数字 题目描述 思路详解 本题的思路比较简单,首先将这个数组排序,遍历数组,找到当前的和前一个相同的直接输出就好了.没找到输出-1. 注意:这个方法要注意循环的时候下标要从1开始哦,不然会报数组下标异常滴. 代码与结果 import java.util.*; public class Solution { /** * 代码中的类名.方法名

  • C语言修炼之路函数篇真题训练上

    本文对应文章 : C语言修炼之路一朝函数思习得 模块思维世间生上篇 C语言修炼之路一朝函数思习得 模块思维世间生下篇 第壹题 A选项 C语言的函数每次只能返回一个元素,上面代码中的 return a,b 只能执行逗号表达式的最后一个语句,即返回20 B选项 C选项 D选项 全局变量在整个程序的任意地方都可以使用 第贰题 C选项 函数不可嵌套定义,但可以嵌套调用  --  “上一篇文章中提及过” 第叁题 A选项 可以 return void 不返回任何参数 B选项 正确 C选项 可以使用全局变量

  • Java 栈与队列超详细分析讲解

    目录 一.栈(Stack) 1.什么是栈? 2.栈的常见方法 3.自己实现一个栈(底层用一个数组实现) 二.队列(Queue) 1.什么是队列? 2.队列的常见方法 3.队列的实现(单链表实现) 4.循环队列 一.栈(Stack) 1.什么是栈? 栈其实就是一种数据结构 - 先进后出(先入栈的数据后出来,最先入栈的数据会被压入栈底) 什么是java虚拟机栈? java虚拟机栈只是JVM当中的一块内存,该内存一般用来存放 例如:局部变量当调用函数时,我们会为函数开辟一块内存,叫做 栈帧,在 jav

  • C语言修炼之路函数篇真题训练下

      本文的Gitee地址:文章源代码 第壹题 :字符串逆序(递归实现) 方法一,非递归实现 main主体部分 数组名是首元素的地址 首元素是char类型,对应的传参元素过去就是  char*  类型 采用两个指针不断移动,然后交换两个位置的元素来实现逆序 方法贰,递归实现 大致思路 代码实现 (推荐自己手动模拟一下) void reverse_string(char* str) { int len = strlen(str); char tmp = str[0]; str[0] = str[le

  • Java实现栈和队列面试题

    面试的时候,栈和队列经常会成对出现来考察.本文包含栈和队列的如下考试内容: (1)栈的创建 (2)队列的创建 (3)两个栈实现一个队列 (4)两个队列实现一个栈 (5)设计含最小函数min()的栈,要求min.push.pop.的时间复杂度都是O(1) (6)判断栈的push和pop序列是否一致 1.栈的创建: 我们接下来通过链表的形式来创建栈,方便扩充. 代码实现: public class Stack { public Node head; public Node current; //方法

  • Java数据结构学习之栈和队列

    一.栈 1.1 概述 Java为什么要有集合类: 临时存储数据. 链表的本质: 对象间通过持有和引用关系互相关联起来. 线性表: 普通线性表, 操作受限线性表(某些操作受到限制 --> 某一个线性表它的增删改操作受到限制) --> 栈 & 队列 1.1.1 线性表的概念 (1)线性表:n个数据元素的有序序列. ①首先,线性表中元素的个数是有限的. ②其次,线性表中元素是有序的. (2)那这个"序"指的是什么呢? ①除表头和表尾元素外,其它元素都有唯一前驱和唯一后继,

随机推荐