当前位置: 首页 > news >正文

《Java初阶数据结构》----4.<线性表---Stack栈和Queue队列>

前言

      大家好,我目前在学习java。之前也学了一段时间,但是没有发布博客。时间过的真的很快。我会利用好这个暑假,来复习之前学过的内容,并整理好之前写过的博客进行发布。如果博客中有错误或者没有读懂的地方。热烈欢迎大家在评论区进行讨论!!!

      喜欢我文章的兄弟姐妹们可以点赞,收藏和评论我的文章。喜欢我的兄弟姐妹们以及也想复习一遍java知识的兄弟姐妹们可以关注我呦,我会持续更新滴,
     望支持!!!!!!一起加油呀!!!!

语言只是工具,不能决定你好不好找工作,决定你好不好找工作的是你的能力!!!!!

学历本科及以上就够用了!!!!!!!!!!!!!!!!!!!!!!


本篇博客主要讲解Java基础语法中的

一、栈

1. 栈的概念

2. 栈的使用

3. 栈的模拟实现

4. 栈的常见编程题

二、队列

1. 队列的概念

2. 队列的使用

3.队列的模拟实现

4.队列的循环设计

三、双端队列

一、栈(stack)

1.1 栈的概念

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

栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。

出栈:栈的删除操作叫做出栈。出数据在栈顶。 

 

Stack继承了Vector,Vector和ArrayList类似,都是动态的顺序表,不同的是Vector是线程安 全的。 

1.2 栈的使用 

代码示例:

public static void main(String[] args) {Stack<Integer> s = new Stack();s.push(1);s.push(2);s.push(3);s.push(4);System.out.println(s.size());   // 获取栈中有效元素个数---> 4System.out.println(s.peek());   // 获取栈顶元素---> 4s.pop();   // 4出栈,栈中剩余1   2   3,栈顶元素为3System.out.println(s.pop());   // 3出栈,栈中剩余1 2   栈顶元素为3if(s.empty()){System.out.println("栈空");}else{System.out.println(s.size());}
}

1.3 栈的模拟实现

 变量的定义、包含定义一个数组存储栈、记录栈中元素个数、

定义一个静态常量便于初始化栈

    private int[] elem;//定义一个数组来存储栈中元素private int useSize;//记录栈中元素private static final int DEFAULT_CAPACITY = 10;//定义一个静态常量

 获取栈的长度的方法

    public int getUseSize() {return useSize;}

栈的有参构造方法。构造一个容量为DEFAULT_CAPACITY的栈

    //构造一个容量为DEFAULT_CAPACITY的栈public MyStack(){this.elem = new int[DEFAULT_CAPACITY];}

检测栈是否满了 

    //检测栈是否满了private boolean isFull(){return this.useSize == this.elem.length;}

 入栈:将val放入栈

    //将val放入栈public void push(int val){if (isFull()){this.elem = Arrays.copyOf(this.elem,2*this.elem.length);}this.elem[useSize++] = val;}

出栈: 将栈顶元素取出并返回

    //将栈顶元素取出并返回public int pop(){if (isEmpty()){throw new EmptyException("Stack为空!");}return elem[--useSize];}

获取栈顶元素

    //获取栈顶元素public int peek(){if (isEmpty()){throw new EmptyException("Stack为空!");}return elem[useSize-1];}

检测栈是否为空

    //检测栈是否为空private boolean isEmpty(){return this.useSize == 0;}

1.4 栈的常见编程题

1.有效的括号

    public boolean isValid(String s) {Stack<Character> stack = new Stack<>(); 
//判断是否为有效的括号,具有先进后匹配的特点,因此我们用栈。首先创建一个栈int len = s.length(); //首先得到字符串长度if (len == 0) {       //如果字符串为空,则返回truereturn true;}if (len % 2 == 1) {   //括号成双成对,因此如果字符串为奇数,那么直接返回falsereturn false; } else {     //如果为偶数,符合预期则,将字符串转字符数组。遍历这个字符数组char[] chars = s.toCharArray();for (char ch : chars) {            if (ch == '(' || ch == '[' || ch == '{') { //如果为左括号,则入栈。stack.push(ch);}if (!stack.empty()) { //如果有左括号,到这里栈一定不为空。如果栈为空,则返回false,因为先得有左括号才会是有效括号//接下来判断右括号,如果遍历到右括号,那么必有栈顶元素与之配对才会是有效括号,并出栈栈顶元素。否则返回false。if (ch == '}') {if (stack.pop() != '{') {return false;}}if (ch == ']') {if (stack.pop() != '[') {return false;}}if (ch == ')') {if (stack.pop() != '(') {return false;}}} else { return false;}}} //最终判断栈是否为空,若全是左括号,那么就没有出栈。因此如果栈内有元素则为false。若匹配成功//栈为空,返回truereturn stack.empty();}

2.逆波兰表达式求值

import java.util.Stack;
//运算方法是将数字入栈,如果碰到运算符号。则出栈将第一个出栈元素放在运算符右边,第二个出栈元素放入运算符左边
//计算这个结果,并将这个计算结果入栈。重复以上操作。即可计算出逆波兰表达式的值。
public class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();int right;int left;   for (String token:tokens) {switch (token){case "+":stack.push(stack.pop()+stack.pop());break;case "-":right = stack.pop();left = stack.pop();stack.push(left-right);break;case "*":stack.push(stack.pop()*stack.pop());break;case "/":right = stack.pop();left = stack.pop();stack.push(left/right);break;default:stack.push(Integer.parseInt(token)); //注意这里放入栈的时候要将字符串转整型类型}}return stack.peek();}
}

1.运算方法是将数字入栈,如果碰到运算符号。则出栈将第一个出栈元素放在运算符右边,第二个出栈元素放入运算符左边
2.计算这个结果,并将这个计算结果入栈。重复以上操作。即可计算出逆波兰表达式的值。

3.栈的压入、弹出序列 

import java.util.Stack;
public class Solution {public boolean IsPopOrder(int [] pushA,int [] popA) {int n = pushA.length;//辅助栈Stack<Integer> s = new Stack<>();//遍历入栈的下标int j = 0;//遍历出栈的数组for(int i = 0; i < n; i++){//入栈:栈为空或者栈顶不等于出栈数组while(j < n && (s.isEmpty() || s.peek() != popA[i])){s.push(pushA[j]);j++;}//栈顶等于出栈数组if(s.peek() == popA[i])s.pop();//不匹配序列elsereturn false;}return true;}
}

4.最小栈

class MinStack {Deque<Integer> xStack;Deque<Integer> minStack;public MinStack() {xStack = new LinkedList<Integer>();minStack = new LinkedList<Integer>();minStack.push(Integer.MAX_VALUE);}public void push(int x) {xStack.push(x);minStack.push(Math.min(minStack.peek(), x));}public void pop() {xStack.pop();minStack.pop();}public int top() {return xStack.peek();}public int getMin() {return minStack.peek();}
}

1.5栈的应用场景

将递归转化为循环

比如:逆序打印链表

递归方式

// 递归方式
void printList(Node head){if(null != head){printList(head.next);System.out.print(head.val + " ");}
}

循环方式

// 循环方式
void printList(Node head){if(null == head){return;}Stack<Node> s = new Stack<>();// 将链表中的结点保存在栈中Node cur = head;while(null != cur){s.push(cur);cur = cur.next;}// 将栈中的元素出栈while(!s.empty()){System.out.print(s.pop().val + " ");}
}

二、队列 

2.1队列的概念

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)。

入队列:进行插入操作的一端称为队尾(Tail/Rear)

出队列:进行删除操作的一端称为队头 (Head/Front)

 

 

在Java中,Queue是个接口,底层是通过链表实现的。

2.2 队列的使用 

注意:Queue是个接口,在实例化时必须实例化LinkedList的对象,因为LinkedList实现了Queue接口。 

public static void main(String[] args) {Queue<Integer> q = new LinkedList<>();q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5);                  // 从队尾入队列System.out.println(q.size());System.out.println(q.peek());  // 获取队头元素q.poll();System.out.println(q.poll());  // 从队头出队列,并将删除的元素返回if(q.isEmpty()){System.out.println("队列空");}else{System.out.println(q.size());}
}

2.3 队列模拟实现

队列中既然可以存储元素,那底层肯定要有能够保存元素的空间,通过前面线性表的学习了解到常见的空间类型有 两种:顺序结构 链式结构。思考下:队列的实现使用顺序结构还是链式结构好? 

 

 定义变量、用内部类定义队列的的节点、队头、队尾、队员数

    static class ListNode{private int val;private ListNode prev;private ListNode next;public ListNode(int val){this.val = val;}private ListNode front;//队头private ListNode rear;//队尾private int useSize;//队员数}

得到队员数 

    public int getUseSize() {return useSize;}

入队

    //入队操作,相当于头插法public void offer(int x){ListNode node = new ListNode(x);if(front == null){front = rear = node;}else {node.next = front;front.prev = node;front = node;}useSize++;}

出队

    //出队操作,相当于删除尾节点public int poll(){if(rear == null){return -1;}int ret = rear.val;if(front == rear){front = null;rear = null;return ret;}rear = rear.prev;rear.next = null;useSize--;return ret;}

获取队头元素 

    //获取队头元素public int peek(){if(front == null){return -1;}return front.val;}

检测队列是否为空 

    //检测队列是否为空public boolean isEmpty(){return this.useSize == 0;}

2.4 循环队列

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解的生产者消费者模型就可以就会使用循环队列。 环形队列通常使用数组实现。

 

数组下标循环的小技巧  

1. 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length

2. 下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length  

 

如何区分空与满 

1. 通过添加 size 属性记录

2. 保留一个位置

3. 使用标记 

 

 三、双端队列 (Deque)

双端队列(deque)是指允许两端都可以进行入队和出队操作的队列,deque 是 “double ended queue” 的简称。

那就说明元素可以从队头出队和入队,也可以从队尾出队和入队。

Deque是一个接口,使用时必须创建LinkedList的对象。 

 

在实际工程中,使用Deque接口是比较多的,栈和队列均可以使用该接口。 

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

 2.5设计循环队列

class MyCircularQueue {private int front;private int rear;private int capacity;private int[] elements;public MyCircularQueue(int k) {capacity = k + 1;elements = new int[capacity];rear = front = 0;}public boolean enQueue(int value) {if (isFull()) {return false;}elements[rear] = value;rear = (rear + 1) % capacity;return true;}public boolean deQueue() {if (isEmpty()) {return false;}front = (front + 1) % capacity;return true;}public int Front() {if (isEmpty()) {return -1;}return elements[front];}public int Rear() {if (isEmpty()) {return -1;}return elements[(rear - 1 + capacity) % capacity];}public boolean isEmpty() {return rear == front;}public boolean isFull() {return ((rear + 1) % capacity) == front;}
}

四、面试题 

1.用队列实现栈

class MyStack {Queue<Integer> queue1;Queue<Integer> queue2;/** Initialize your data structure here. */public MyStack() {queue1 = new LinkedList<Integer>();queue2 = new LinkedList<Integer>();}/** Push element x onto stack. */public void push(int x) {queue2.offer(x);while (!queue1.isEmpty()) {queue2.offer(queue1.poll());}Queue<Integer> temp = queue1;queue1 = queue2;queue2 = temp;}/** Removes the element on top of the stack and returns that element. */public int pop() {return queue1.poll();}/** Get the top element. */public int top() {return queue1.peek();}/** Returns whether the stack is empty. */public boolean empty() {return queue1.isEmpty();}
}

2.用栈实现队列

 

class MyQueue {Deque<Integer> inStack;Deque<Integer> outStack;public MyQueue() {inStack = new ArrayDeque<Integer>();outStack = new ArrayDeque<Integer>();}public void push(int x) {inStack.push(x);}public int pop() {if (outStack.isEmpty()) {in2out();}return outStack.pop();}public int peek() {if (outStack.isEmpty()) {in2out();}return outStack.peek();}public boolean empty() {return inStack.isEmpty() && outStack.isEmpty();}private void in2out() {while (!inStack.isEmpty()) {outStack.push(inStack.pop());}}
}

http://www.lryc.cn/news/406167.html

相关文章:

  • Android SurfaceFlinger——关联EGL三要素(二十七)
  • Unity3D之TCP网络通信(客户端)
  • Kotlin 中 标准库函数
  • 【教学类-69-01】20240721铠甲勇士扑克牌(随机14个数字+字母)涂色(男孩篇)
  • Adobe“加速”创意人士开启设计新篇章
  • 释疑 803-(1)概述 精炼提纯版
  • 人工智能与机器学习原理精解【6】
  • JDK、JRE、JVM之间的关系
  • redis构建集群时,一直Waiting for the cluster to join
  • C++之类与对象(2)
  • 「树形结构」基于 Antd 实现一个动态增加子节点+可拖拽的树
  • ubuntu那些ppa源在哪
  • 20240724-然后用idea创建一个Java项目/配置maven环境/本地仓储配置
  • PaddleOCR-PP-OCRv4推理详解及部署实现(下)
  • 【Golang 面试基础题】每日 5 题(二)
  • 状态模式与订单状态机的实现
  • 【MSP430】MSP430是什么?与STM32对比哪个性能更佳?
  • Win11 操作(四)g502鼠标连接电脑不亮灯无反应
  • 自定义QDialog使用详解
  • Pytorch使用教学2-Tensor的维度
  • Interesting bug caused by getattr
  • 获取后端返回的图形验证码
  • 奇怪的Excel单元格字体颜色格式
  • 浅谈芯片验证中的仿真运行之 timescale (五)提防陷阱
  • uniapp 重置表单数据
  • 自学YOLO前置知识
  • Ubuntu18.04 编译报错: Could NOT find JNI
  • SQL labs-SQL注入(五,使用sqlmap进行cookie注入)
  • C语言——内存管理
  • Unity UGUI 之 Image和Rawimage