- 顶: 2919踩: 212
看到这句话的时候证明：此刻你我都在努力
加油陌生人
个人主页：Gu Gu Study
专栏：用Java学习数据结构系列
喜欢的一句话： 常常会回顾努力的自己，所以要为自己的努力留下足迹
喜欢的话可以点个赞谢谢了。
作者：小闭前言
前面已经给大家讲述了顺序表和链表，那么下面就到了，栈和队列，如果我们对顺序表和链表已经熟悉的话，那么我们学习栈和队列是非常轻松的。废话不多说，我们直接进入正题。
栈
这里数据结构的栈和我们常说储存数据的栈区可不是同一个东西。那么这里的栈的具体概念是什么呢？
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除 操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out） 的原则。只要读懂“后进先出”就可以了解我们的栈了。我们看一下图就懂了
从图中我们很明显就看出了，我们想要从栈中取东西，那么就要从栈顶取出，而且每次只能取出最顶的数据。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
简单描述栈的特点：栈数据的增删都是在一头进行，即在栈顶
栈的主要方法
- Push：向栈中添加一个元素。
- Pop：移除栈顶的元素。
- Peek或 Top：返回栈顶元素但不移除它。
- IsEmpty： 检查栈是否为空。
- Size：返回栈中元素的数量。
这么一看可能已经大致了解了栈的概念和方法了，那么我们现在就用代码使用一下栈。
import java.util.Stack;public class T { public static void main(String[] args) { Stack<Integer> stack=new Stack<>(); Stack<Integer> stack2=new Stack<>(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack2.push(4); stack2.push(5); stack2.push(6); stack2.push(7); System.out.println(stack.peek());//查看栈顶的数据 //依次进行数据出栈 System.out.print(stack.pop()+" "); System.out.print(stack.pop()+" "); System.out.print(stack.pop()+" "); System.out.print(stack.pop()+" "); stack.addAll(stack2); System.out.println(); System.out.print(stack.pop()+" "); System.out.print(stack.pop()+" "); System.out.print(stack.pop()+" "); System.out.print(stack.pop()+" "); }}
在上面代码中给大家演示了，push，pop，peek，addall等方法，效果也是如图所示了。
重点提一下addall这个方法吧：
addall在链表和顺序表，栈，队列都是存在的，他们也是可以互相直接添加数据的。
import java.util.ArrayList;import java.util.Stack;public class T { public static void main(String[] args) { Stack<Integer> stack=new Stack<>(); Stack<Integer> stack2=new Stack<>(); ArrayList<Integer> arrayList=new ArrayList<>(); arrayList.add(11); arrayList.add(12); arrayList.add(13); arrayList.add(14); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack2.push(4); stack2.push(5); stack2.push(6); stack2.push(7); System.out.println(stack.peek());//查看栈顶的数据 //依次进行数据出栈 System.out.print(stack.pop()+" "); System.out.print(stack.pop()+" "); System.out.print(stack.pop()+" "); System.out.print(stack.pop()+" "); stack.addAll(arrayList); System.out.println(); System.out.print(stack.pop()+" "); System.out.print(stack.pop()+" "); System.out.print(stack.pop()+" "); System.out.print(stack.pop()+" "); }}如上代码：在35行，我将顺序表中的数据直接添加到栈中，最后的打印结果显示表明这是可行的。
栈练习（小试牛刀）
力扣题目：给定一个只包括
'('，')'，'{ '，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
这是一道面试题呢，大家伙可以先自己想一下解题唔。ps：既然在栈的文章出现当然可以用栈解决了。
好了下面展示答案：
class Solution { public boolean isValid(String s) { Stack<Character> stack=new Stack<>(); char cc; for (int i = 0; i < s.length(); i++) { char c=s.charAt(i); switch (c){ case '[': stack.push(c); break; case '(': stack.push(c); break; case '{ ': stack.push(c); break; case ']': if(stack.empty()){ return false; } cc=stack.pop(); if(cc!='['){ return false; } break; case '}': if(stack.empty()){ return false; } cc=stack.pop(); if(cc!='{ '){ return false; } break; case ')': if(stack.empty()){ return false; } cc=stack.pop(); if(cc!='('){ return false; } break; default: break; } } if(stack.empty()){ return true; }else { return false; } }}先讲思路：
我们首先要运用一个存储字符数据的栈，然后我们遍历字符串，然后如果当前字符串为左括号类型则直接入栈，如果为右括号类型，那么我们直接从出栈取栈顶的一个左括号做匹配，如果右括号和这个左括号匹配，那么继续遍历，直至字符串遍历完毕。如果过程中发现右括号和出栈的左括号不匹配那么直接返回false，最后查看我们的栈是否为空，如果为空说明字符串里的字符确实是匹配的，否则说明字符串中的左括号多余出来了，这样的也是括号不匹配。
代码：代码中我用了switch语句，当然也可以用if else语句，我觉得switch比较明了。
然后跟思路所说左括号入栈，右括号则出一个左括号进行匹配。
队列
在Java中，队列（Queue）是一种常用的数据结构，它遵循先进先出（FIFO，First In First Out）的原则。这意味着最早添加到队列的元素将是第一个被移除的元素。队列在多种场景下都非常有用，比如任务调度、消息传递等。
还是一样只要读懂”先进先出（FIFO，First In First Out）“，那么你就可以学会队列了。
Java提供了几种队列实现：
- LinkedList- 基于链表的队列实现，允许在队列的两端进行高效的插入和删除操作。
LinkedList类实现了List和Deque接口，因此可以作为队列使用。 - ArrayDeque- 基于动态数组的双端队列实现。
ArrayDeque提供了在队列两端进行快速插入和删除操作的能力，并且可以作为栈或队列使用。 - PriorityQueue- 一种特殊的队列，它按照元素的自然顺序或者根据提供的
Comparator来决定元素的优先级，从而决定出队的顺序。 - BlockingQueue- 线程安全的队列，用于在任务生产者和消费者之间进行通信。
BlockingQueue接口是Java并发API的一部分，提供了几种实现，如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue等。
以下是使用
LinkedList作为队列的一些基本操作示例：import java.util.LinkedList;import java.util.Queue;public class Main { public static void main(String[] args) { // 创建一个队列 Queue<String> queue = new LinkedList<>(); // 向队列中添加元素 queue.add("Java"); queue.add("Python"); queue.add("C++"); // 查看队首元素但不移除 System.out.println("队首元素: " + queue.peek()); // 移除队首元素 while (!queue.isEmpty()) { System.out.println("出队元素: " + queue.poll()); } }}在这个示例中，我们创建了一个
LinkedList的实例，并使用add方法向队列中添加元素。使用peek方法可以查看队首元素而不移除它。最后，我们使用poll方法在循环中移除所有元素，直到队列为空。请注意，
LinkedList和ArrayDeque都可以用来实现队列，但是ArrayDeque提供了更多的灵活性，因为它可以作为双端队列使用，允许在两端进行插入和删除操作。而PriorityQueue和BlockingQueue则提供了队列的其他变体，适用于不同的应用场景。我们这篇文章用的是LinkedList实现队列，毕竟我们现在暂时只了解链表。
链表的主要方法
在Java中，队列（Queue）接口定义了一系列用于队列操作的方法。以下是一些基本的队列操作方法：
boolean add(E e)- 向队列添加一个元素。如果成功，返回true；如果没有足够空间，则抛出IllegalStateException。boolean offer(E e)- 向队列添加一个元素。如果成功，返回true；如果没有足够空间，返回false。E remove()- 移除并返回队列头部的元素。如果队列为空，则抛出NoSuchElementException。E poll()- 移除并返回队列头部的元素。如果队列为空，则返回null。E element()- 返回队列头部的元素但不移除它。如果队列为空，则抛出NoSuchElementException。E peek()- 返回队列头部的元素但不移除它。如果队列为空，则返回null。int size()- 返回队列中的元素数量。boolean isEmpty()- 如果队列为空，则返回true。Iterator<E> iterator()- 返回一个迭代器，用于遍历队列中的元素。Spliterator<E> spliterator()- 返回一个分割器（Spliterator），它提供对队列元素的并行迭代。void clear()- 清除队列中的所有元素。
这些方法提供了队列的基本操作，包括元素的添加、移除、查看以及队列状态的检查。不同的队列实现可能会提供额外的方法，例如
PriorityQueue提供了根据优先级排序的元素出队的方法。以下是使用
Queue接口的一个简单示例：import java.util.LinkedList;import java.util.Queue;public class QueueExample { public static void main(String[] args) { Queue<String> queue = new LinkedList<>(); // 添加元素到队列 queue.add("Element 1"); queue.add("Element 2"); // 查看队首元素 System.out.println("队首元素: " + queue.peek()); // 移除队首元素 System.out.println("出队元素: " + queue.poll()); // 检查队列是否为空 System.out.println("队列是否为空: " + queue.isEmpty()); // 获取队列大小 System.out.println("队列大小: " + queue.size()); }}在这个示例中，我们使用
LinkedList作为队列的实现，并演示了如何添加元素、查看队首元素、移除元素、检查队列是否为空以及获取队列的大小。我们的队列也是可以使用addall的。
public static void main(String[] args) { Queue<Integer> queue=new LinkedList<>(); ArrayList<Integer> arrayList=new ArrayList<>(); arrayList.add(11); arrayList.add(12); arrayList.add(13); arrayList.add(14); queue.add(1); queue.add(2); queue.add(3); queue.add(4); queue.addAll(arrayList); System.out.println(queue.toString());}
队列练习（小试牛刀）
这个题目就是要我们运用队列来模拟出一个栈。还是大家先想一下在展示答案
好了开始展示答案：
class MyStack { Queue<Integer> queue; Queue<Integer> queue1; public MyStack() { queue=new LinkedList<>(); queue1=new LinkedList<>(); } public void push(int x) { if(queue.isEmpty()){ queue1.add(x); }else { queue.add(x); } } public int pop() { if(queue.isEmpty()) { int count=queue1.size()-1; for (int i = 0; i <count; i++) { queue.add(queue1.poll()); } return queue1.poll(); }else{ int count=queue.size()-1; for (int i = 0; i <count; i++) { queue1.add(queue.poll()); } return queue.poll(); } } public int top() { if(queue.isEmpty()) { int count=queue1.size(); for (int i = 0; i <count-1; i++) { queue.add(queue1.poll()); } int n= queue1.poll(); queue.add(n); return n; }else{ int count=queue.size(); for (int i = 0; i <count-1; i++) { queue1.add(queue.poll()); } int n= queue.poll(); queue1.add(n); return n; } } public boolean empty() { return queue1.isEmpty()&&queue.isEmpty(); }}思路：很简单我们运用两个队列来模拟实现栈。首先我们都知道队列是先进先出。而栈是先进后出。那么第二个队列的作用就出来了。在入模拟栈时我们将数据存储进一个有数据的队列，这个有数据的队列的主要作用就是存储数据，那么第二个队列的作用就是辅助实现出栈了。进行出栈操作时我们将有数据的队列出到只剩一个数据，那么这时剩下的那个数据就是我们想要出栈的数据了。然后根据思路写出的代码就如上了。
文章已到末尾，喜欢的话点赞一下唔，后面会持续更新这个系列唔。
评论专区