医院做网站开发,wordpress 三主题公园,wordpress分享 赞插件,广州天河网站开发公司目录
前言
1.使用“栈”检查符号是否成对出现
2.使用“栈”实现字符串反转
3.使用“队列”实现“栈”
4.使用“栈”实现“队列” 前言 什么是栈#xff1f; 栈#xff08;stack#xff09;是一种特殊的线性数据集合#xff0c;只允许在栈顶按照后进先出LIFO#xff… 目录
前言
1.使用“栈”检查符号是否成对出现
2.使用“栈”实现字符串反转
3.使用“队列”实现“栈”
4.使用“栈”实现“队列” 前言 什么是栈 栈stack是一种特殊的线性数据集合只允许在栈顶按照后进先出LIFOLast In First Out进行数据操作 为什么使用栈 常见应用场景浏览器的前进与回退操作、虚拟机栈等 如何使用栈 栈的实现结构可以是一维数组或链表实现用数组实现的栈叫做顺序栈。在Java中顺序栈使用java.util.Stack类实现用链表实现的栈叫做链式栈。在Java中链式栈使用java.util.LinkedList类实现入栈push将新元素放入栈顶只允许从栈顶一侧放入元素类似于弹匣装弹只能从弹匣口依次压入弹匣内 出栈pop只有栈顶元素才允许出栈类似于枪射出子弹时子弹从弹匣口依次进入枪体射出 时间复杂度 访问指定位置的元素O(n) ——需要依次遍历所有元素所需元素可能在栈底入栈和出栈O(1) ——只涉及栈顶 什么是队列 队列queue是一种线性数据结构队列中的元素按照先入先出的规则从队尾进入队头出队按照实现机制分为单队列、循环队列 为什么使用队列 常见应用场景KTV点歌列表、阻塞队列、线程池的任务队列等 如何使用队列 队列的实现结构可以是数组或链表实现用数组实现的队列叫做顺序队列。在Java中顺序队列使用java.util.ArrayDeque类实现用链表实现的队列叫做链式队列。在Java中链式队列使用java.util.LinkedList类实现入队enqueue只允许从队尾的位置放入元素类似于银行取号等待叫号办理业务 出队dequeue只允许从队头的位置移出元素 假溢出使用数组实现队列执行出队操作时指向队头和队尾的指针会向后移队尾指针移动到最后的时候无法添加数据即使数组中之前出队的位置还要空闲空间这种现象就是“假溢出”。 1. 使用“栈”检查符号是否成对出现 public static boolean isValid(String s ){HashMapCharacter, Character mappings new HashMap();mappings.put(},{);mappings.put(),();mappings.put(],[);StackCharacter stack new Stack();for(int i0;is.length();i){char c s.charAt(i);if(mappings.containsKey(c)){//当前字符是“右括号”char topElement stack.isEmpty() ? # :stack.pop();char left mappings.get(c);if(left ! topElement){return false;}}else {//当前字符是左括号stack.push(c);}}return stack.isEmpty();} 解读 创建一个HashMap mappings用于存储右括号和对应的左括号的映射关系创建一个Stack stack用于存储遍历过程中遇到的左括号以便后续进行匹配检查进入for循环遍历输入的字符串s。在循环中取出字符串中的每个字符c如果当前字符c存在于 mappings 中即为右括号那么就从栈中弹出栈顶元素然后检查该右括号对应的左括号是否与弹出的左括号匹配如果不匹配则返回false如果当前字符c不存在于 mappings 中即为左括号将其压入栈中循环结束后检查栈是否为空如果栈为空则说明所有的括号都匹配返回true否则返回false 测试用例 public static void main(String[] args) {String str {[(!)]};System.out.println(isValid(str));}
测试结果 2. 使用“栈”实现字符串反转
public static void main(String[] args) {String str just do it;StringBuilder stringBuilder new StringBuilder(str);//使用栈实现字符串反转StackCharacter stringStack new Stack();//入栈for(int i0;istr.length();i){stringStack.push(str.charAt(i));}//出栈while (!stringStack.empty()){str stringStack.pop();}System.out.println(stringBuilder);} 解读 创建一个Stack stringStack用于存储字符串中的字符进入for循环遍历输入的字符串str将字符串中的每个字符依次压入栈中使用while循环当栈不为空时依次从栈中弹出字符并将其拼接到原字符串str的末尾循环结束后str中存储的就是原字符串str的反转结果 测试结果 3. 使用“队列”实现“栈”
public class MyStack{private QueueInteger queue1; //出栈队列private QueueInteger queue2; //入栈队列public MyStack(){queue1 new LinkedListInteger();queue2 new LinkedListInteger();}public void push(int x){queue2.offer(x);while(!queue1.isEmpty()){queue2.offer(queue1.poll());}QueueInteger temp queue1;queue1 queue2;queue2 temp;}public int pop(){return queue1.poll();}public int top(){return queue1.peek();}public boolean empty(){return queue1.isEmpty();}Overridepublic String toString() {return queue1.toString();}
} 解读 定义了一个名为 MyStack 的类其中包含两个私有属性 queue1 和 queue2分别表示出栈队列和入栈队列并在构造函数中对它们进行了初始化push 方法用于入栈操作将元素加入 queue2 中然后通过循环将 queue1 中的元素逐个转移到 queue2 中以确保新入栈的元素位于队列的头部因为队列的特性是先进先出。最后交换 queue1 和 queue2 的引用使得 queue1 始终指向当前栈中的元素所在的队列pop 方法用于出栈操作直接从 queue1 中弹出元素即可top 方法用于获取栈顶元素直接返回 queue1 的头部元素empty 方法用于判断栈是否为空直接返回 queue1 是否为空的结果 用两个队列模拟栈的基本操作通过不断在两个队列之间转移元素使得栈的操作可以在队列上进行 测试用例 public static void main(String[] args) {MyStack myStack new MyStack();//入栈myStack.push(1);myStack.push(2);myStack.push(3);myStack.push(4);myStack.push(5);System.out.println(入栈后myStack);System.out.println(入栈后栈顶元素:myStack.top());//出栈myStack.pop();myStack.pop();myStack.pop();myStack.pop();myStack.pop();System.out.println(出栈后myStack);System.out.println(出栈后栈是否为空:myStack.empty());}
测试结果 4. 使用“栈”实现“队列”
public class Queue{//入队栈private StackInteger inStack new Stack();//出队栈private StackInteger outStack new Stack();//入队public void offer(int item){while(!outStack.empty()){inStack.push(outStack.pop());}//新元素入队inStack.push(item);}//出队public int poll(){while(!inStack.empty()){outStack.push(inStack.pop());}return outStack.pop();}//判断是否为空public boolean empty(){return outStack.size() 0 inStack.size() 0;}Overridepublic String toString() {return inStack.toString();}
} 解读 offer 方法用于向队列中添加元素。首先它会将 outStack 中的元素逐个弹出并压入 inStack 中这样可以确保之前入队的元素在 inStack 的底部新的元素可以被放在队列的末尾接着将新元素直接入栈到 inStack 中表示将新元素放入队列中。poll 方法用于从队列中取出元素。首先它会将 inStack 中的元素逐个弹出并压入 outStack 中这样可以确保队列的头部元素位于 outStack 的栈顶然后从 outStack 中弹出栈顶元素并作为出队操作的结果返回。empty 方法用于检查队列是否为空。只有当 inStack 和 outStack 都为空时才表示整个队列为空 基于两个栈实现队列的方法称为双栈法通过巧妙地利用栈的特性可以实现队列的先进先出FIFO功能。在实际应用中双栈法可以用于需要频繁进行队列操作的场景同时也可以作为栈和队列之间的一个有趣的数据结构转换方式。 测试用例 public static void main(String[] args) {Queue myQueue new Queue();//入队myQueue.offer(1);myQueue.offer(2);myQueue.offer(3);myQueue.offer(4);myQueue.offer(5);System.out.println(入队后:myQueue);//出队myQueue.poll();myQueue.poll();myQueue.poll();myQueue.poll();myQueue.poll();System.out.println(出队后是否为空:myQueue.empty());}
测试结果
