写点什么

数据结构的栈和队列 (这不进来看一看),计算机 java 语言入门

用户头像
极客good
关注
发布于: 刚刚

public int pop() throws RuntimeException{


if (empty()){


//如果栈为空则抛出异常


throw new RuntimeException("栈空了");


}


//返回栈顶元素并从栈中删除栈顶元素


return this.elem[--this.usedSize];


}


public int peek() {


if (empty()){


//如果栈为空则抛出异常


throw new RuntimeException("栈空了");


}


//返回栈顶元素但不从栈中删除栈顶元素


return this.elem[this.usedSize-1];


}


}


注意:在 java 程序中,可以直接使用栈


格式:


Stack 变量名=new Stack<>()


| 方法 | 解释 |


| --- | --- |


| E push(E item) | 压栈 |


| E pop() | 出栈 |


| E peek() | 查看栈顶元素 |


| boolean empty() | 判断栈是否为空 |

[](

)栈的面试题

[](

)括号匹配



题解:


该题考查对栈掌握程度,为了匹配有效括号,我们可以使用使用一个栈,将遇到的左括号都放入栈中,遇到右括号就取出栈顶元素进行比较,如果匹配则删除栈顶,如果不匹配则返回 false;循环结束后再判断栈是否为空如果为空则返回 true,相反则返回 false;


class Solution {


public boolean isValid(String s) {


Stack<Character> stack=new Stack<>();


char[] ch=s.toCharArray();


for(char ch1:ch){


switch(ch1){


case '(':


case '{':


case '[':


stack.push(ch1);


break;


case ')':


if(!stack.isEmpty()&&stack.peek()=='('){


stack.pop();


}


else{


return false;


}


break;


case ']':


if(!stack.isEmpty()&&stack.peek()=='['){


stack.pop();


}


else{


return false;


}


break;


case '}':


if(!stack.isEmpty()&&stack.peek()=='{'){


stack.pop();


}


else{


return false;


}


break;


}


}


if(stack.isEmpty()){


return true;


}


return false;


}


}


[](

)逆波兰表达式求值



该题考查我们对前缀算法和中缀算法的熟悉程度,使用一个栈,将数字放入其中当遇到‘+’,‘-’,‘*’,‘/’,则取出栈顶的两个元素,与相应的运算符进行操作


再将新获得的数放入栈中。


class Solution {


public int evalRPN(String[] tokens) {


Stack<Integer> stack = new Stack<>();


int n = tokens.length;


for (String token:tokens) {


if (isNumber(token)) {


stack.push(Integer.parseInt(token));


} else {


int num2 = stack.pop();


int num1 = stack.pop();


switch (token) {


case "+


【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开:qq.cn.hn/FTf 免费领取
复制代码


":


stack.push(num1 + num2);


break;


case "-":


stack.push(num1 - num2);


break;


case "*":


stack.push(num1 * num2);


break;


case "/":


stack.push(num1 / num2);


break;


default:


break;


}


}


}


return stack.pop();


}


public boolean isNumber(String token) {


return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));


}


}



[](


)队列



[](

)队列的概念


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


如图:



为了实现队列,可以采用数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。


class Node {


public int data;


public Node next;


public Node(int data) {


this.data = data;


}


}


public class MyQueueLinked {


private Node front;


private Node rear;


private int usedSize;


//插入元素进入队列中


public void offer(int val) {


Node node=new Node(val);


if (front==null){


this.front=node;


this.rear=node;


}


else {


this.rear.next=node;


this.rear=node;


}


this.usedSize++;


}


public int size() {


return this.usedSize;


}


public boolean isEmpty() {


return this.usedSize == 0;


}


//返回栈头元素,并从队列中删除


public int poll() {


if (isEmpty()) {


throw new RuntimeException("队列为空!");


}


int val=this.front.data;


if(this.front.next == null) {


this.front = null;


this.rear = null;


}


else {


this.front=this.front.next;


}


this.usedSize--;


return val;


}


//返回栈头元素,但不从队列中删除


public int peek(){


if (isEmpty()) {


throw new RuntimeException("队列为空!");


}


return this.front.data;


}


}

[](

)循环队列


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



循环队列和普通队列一样:队尾加元素,队头输出元素

[](

)如何区分循环队列的空与满


循环队列一般会保留一个位置以便于判断是否满了


如图:



用户头像

极客good

关注

还未添加个人签名 2021.03.18 加入

还未添加个人简介

评论

发布
暂无评论
数据结构的栈和队列(这不进来看一看),计算机java语言入门