Java------数据结构之栈与队列（简单讲解）

本篇碎碎念：时隔n个月，继续写博客，假期落下的进度，在开学后努力追赶，假期不努力，开学徒伤悲啊，此时此刻真想对自己说一句，活该啊~~~~

欠下的链表练习题讲解会在下次更新~~~~

今日份励志文案: 万物皆有裂痕，那是光照进来的地方

一.栈

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

栈中的元素遵守后进先出LIFO原则

栈的相关使用方法

        Stack<Integer> stack=new Stack<>();//入栈stack.push(1);stack.push(2);stack.push(3);System.out.println(stack);//弹出并获取栈顶元素int a=stack.pop();System.out.println(a);//获取栈顶元素int b=stack.peek();System.out.println(b);System.out.println(stack);//判断栈是否为空boolean c=stack.isEmpty();System.out.println(c);//判断栈的大小int d=stack.size();System.out.println(d);

练习题：

1. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）

A: 1,4,3,2 B: 2,3,4,1 C : 3,1,4,2 D: 3,4,2,1

20. 有效的括号 - 力扣（LeetCode）

这两道题的答案与讲解会在末尾公布

二.队列

队列:只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表

队列具有先进先出FIFO原则

入队列：进行插入操作的一端称为队尾（Tail/Rear） \

出队列：进行删除操作的一端称为队头

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("队列中的元素个数为:");System.out.println(q.size());System.out.println("队列中队头元素为:");System.out.println(q.peek()); // 获取队头元素// 从队头出队列，并将删除的元素返回q.poll();System.out.println("经过一个p.poll()剩下的元素为:");System.out.println(q);if(q.isEmpty()){System.out.println("队列空");}else{System.out.println(q.size());}}

练习题：

1. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（C）

A: 1,4,3,2 B: 2,3,4,1 C : 3,1,4,2 D: 3,4,2,1

20. 有效的括号 - 力扣（LeetCode）

填空题

编程题

class Solution {public boolean isValid(String s) {Stack<Character> stack=new Stack<>();for(int i=0;i<s.length();i++){char count=s.charAt(i);if(count=='('||count=='{'||count=='['){stack.push(count);}else{if(stack.empty()){return false;}char count1=stack.peek();if(count==')'&&count1=='('||count=='}'&&count1=='{'||count==']'&&count1=='['){stack.pop();}else{return false;}}}return stack.empty();}
}

题目要求

1.左括号必须用相同类型的右括号闭合。

2.左括号必须以正确的顺序闭合。

3每个右括号都有一个对应的相同类型的左括号。

问题1：我们如何遍历字符串？

问题2：如何判断是相同类型的括号？

解1：可以用for循环或者while循环（我用的是for循环）

解2：创建一个栈（先进后出原则），如果为左括号就进栈

如果为右括号就与刚进栈的左括号“配对”

“配对”方式，设置两个char变量，count与count1

if(count==')'&&count1=='('||count=='}'&&count1=='{'||count==']'&&count1=='[')

“配对”成功，左括号出栈，继续走循环,“配对失败”返回false