Java教程
[java数据结构篇]栈和队列的使用
文章目录
- 1.栈
- 有关栈的相关概念
- 栈的相关方法：
- 中缀表达式转化成为后缀表达式
- 手动实现一个栈(底层为数组)
- 手动实现一个栈(底层为单链表)
- 队列
- 有关队列的基本概念
- 队列相关的一些常用方法
- 手动实现一个队列(底层为单链表)
- 手动实现一个队列(底层为一个循环数组)
- 双端队列
- 栈和队列的相关习题
- 1.括号匹配
- 2.后缀表达式转化成为中缀表达式，并计算结果
- 3.实现最小栈
- 4.两个栈实现一个队列
- 5.两个队列实现一个栈
- 6.棒球比赛
- 7.栈的压入，弹出序列
- 8.比较含有退格的字符串
- 9.猫狗收容所
1.栈
有关栈的相关概念
**首先栈是一种基础的较为常用的数据结构，它的特点为：先进后出，底层可以是链表实现，也可以是数组实现，在使用栈这个数据结构的时候，只能对数组的一端进行具体操作。**进行插入和删除操作的一端为栈顶，另一端为栈
底。
栈也可以这样理解：当你在厨房洗盘子的时候，当一个又一个盘子洗完后，盘子就挨个的垒了起来，肯定先洗完的盘子在这一摞盘子的最下面，当我们如果要拿盘子的时候，只能取这一摞盘子最上面的一个。另外当你进入一个网页的时候，在这个网页中又打开了别的栏目，在进入这个网页的时候相当于入栈，而当我们要退出这个网页时，要进行关闭，相当于出栈。
具体动图进行演示
看图说话：
入栈：
出栈：
压栈：在栈中插入元素，又称为入栈。
出栈：删除栈顶元素，把栈顶元素弹出。
栈的相关方法：
首先在使用栈这个数据结构之前，要实例化一个栈的对象。
Stack<Integer> stack = new Stack<>();//在<>里边添加的是在栈中添加数据所对应的类的名称，如果是基本数据类型，使用包装类。
几个较为常用的方法：
| 方法名称 | 方法解释 |
|---|---|
void push(int val) | 在栈中压入数据 |
void pop() | 删除栈顶元素 |
boolean empty() | 判断栈是否为空 |
int peek() | 返回栈顶元素 |
int size() | 返回栈中元素的个数 |
案例：
public static void main(String[] args) {
Stack<Integer>stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.peek());
stack.pop();
System.out.println(stack.peek());
System.out.println(stack.size());
System.out.println(stack.empty());
//运行结果：
//3
//2
//2
//false
}
中缀表达式转化成为后缀表达式
后缀表达式：逆波兰式（Reverse Polish notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）类似于：2,3,5,*,+;
中缀表达式：中缀表达式是一个通用的算术或逻辑公式表示方法。类似于
3*5+2；
那么怎样才能由中缀表达式转化转化成为后缀表达式呢？
这里有一个技巧，绝对惊艳到你！
例题：有一个中缀表达式为 a * ( b - (c +d) ),现在要得到它对应的后缀表达式
解法:根据表达式，先乘除后加减，有括号的，把括号面的运算符移到对应的括号外，最终去除所有的括号。
解题过程：
那么怎样用后缀表达式转化成为中缀表达式呢？
这里就要用到我们今天刚刚学到的栈
解法：遍历后缀表达式，如果遍历字符串，如果遍历到了数字字符就把这个数字字符转化成为数字，然后压到栈中，当遍历到了非数字字符，就把栈中的两个元素弹出，注意，弹出是弹出栈顶的两个元素。并执行加减乘除。详细思想解题过程和相关代码，在栈和队列相关习题中下文。
手动实现一个栈(底层为数组)
//数组实现栈
//自定义异常，继承了Expection类
class MyException extends Exception{
public MyException(String message){
super(message);
}
}
public class MyStack {
public int []elem;
public int usedSize;//当数组中还没有添加元素的时候，有效长度为0
//初始话数组的长度为10
public MyStack() {
this.elem = new int[10];
}
//判断数组现在是否被填满，如果数组满了，就实现扩容
public boolean isFull(){
if(this.elem.length == usedSize){
return true;
}
return false;
}
//先判断数组是否是满的，如果是满的就进行2倍扩容
public int push(int val){
//如果数组满了装不下，扩容
if(isFull()){
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);//二倍扩容
}
this.elem[usedSize] = val;//默认把新的元素添加上次元素的末尾
usedSize++;//有效长度加1
return this.elem[usedSize];
}
public int pop()throws MyException{
//在进行是出栈的时候，如果发现数组中有效长度为0，说明这个数组为空，然后报异常
if(usedSize == 0){
//抛出异常
throw new MyException("数组为空，无法删除");
}
//因为出栈只能从栈顶出，所以在这里直删除数组中最后一个元素
int num = this.elem[usedSize - 1];
//有效长度减一
usedSize--;
return num;
}
public int peek()throws MyException{
//如果数组为空
if(usedSize == 0){
//抛出异常
throw new MyException("数组为空，无法显示");
}
return this.elem[usedSize-1];
}
public boolean empty(){
if(usedSize == 0){
return true;
}
return false;
}
}
手动实现一个栈(底层为单链表)
在使用单链表实现一个栈的时候，要用到头插法，在在头节点插入元素，在头节点删除元素，如果使用尾插法的话，时间复杂的就会上升，在插入和删除的时候都要从头节点向后遍历。它的时间复杂的为O(n),如果使用头插法时间复杂的为O(1).
//创建一个节点类，数据域中存放的是栈中的元素，指针域中存储的是下一个元素的地址
class Node {
public int val;
public Node next;
public Node(int val){
this.val = val;
}
}
public class MyStack1 {
public Node head = null;
public int push(int val){//头插法
Node node = new Node(val);
//让node的后继指针指向head
node.next = head;
//node在head节点之前，更新head节点的位置
head = node;
return head.val;
}
public int pop() throws RuntimeException{
Node cur = head;//保留节点
if(head != null){
//头节点指向头节点的下一个节点
head = head.next;
}else{
//如果头节点为空，说明链表中不存在数据，抛出异常
throw new RuntimeException("栈空");
}
return cur.val;
}
public int peek() throws RuntimeException{
if(head == null){
throw new RuntimeException("栈空");
}
return head.val;
}
public boolean empty(){
if(head == null){
return true;
}
return false;
}
}
队列
有关队列的基本概念
队列：它的特性是先入先出
出队：从队头出，也就是在队头进行删除元素。
入队：从队尾入，也就是在队尾添加元素。
队列的底层是一双向链表链表
队列也可以这样理解，他就和我们在学校饭堂打饭一样(需要排队)，先到的先打饭，打完饭后，离开队伍，这就相当于出队。然而后来到队伍的只能排到队尾，这就相当于入队。
动图演示：
入队：
出队：
队列相关的一些常用方法
在调用队列的一些常用方法之前，首先要实例化一个队列对象。
Queue<Integer>qurue = new LinkedList<>();
队列的一些常用方法：
| 方法名称 | 方法解释 |
|---|---|
void offer(int val) | 将val入队列 |
void poll() | 出队，将队头元素删除 |
boolean isEmpty() | 判断队列是否为空 |
int peek() | 返回队头元素 |
案例：
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.peek());
queue.poll();
System.out.println(queue.peek());
System.out.println(queue.isEmpty());
System.out.println(queue.size());
}
//运行结果：
//1
//2
//false
//2
手动实现一个队列(底层为单链表)
看了上面的关于队列的方法，那么它们是怎样实现的呢？
//建立一个节点类，在节点中，数据域为队列中添加的元素,指针域表示的是下一个元素的地址
class Node{
public int val;
public Node next;
public Node(int val){
this.val = val;
}
}
public class MyQueueLinked {
public Node head;//表示链表的头节点
public Node last;//表示链表的尾节点
public int size;//链表的长度
public void offer(int val){
//向队列中添加元素
Node node = new Node(val);
if(last == null){
head = node;//如果在入队的时候，尾节点为空说明此时队列中还没有元素，这时候让头节点指向node,尾节点也指向node
last = node;
}else{
last.next = node;//如果链表不为空，就让尾节点的指针指向node
last = node; //然后更新尾节点
}
size++;//最后链表节点的个数加一
}
public int peek()throws RuntimeException{//显示队列的队头
//如果队列为空
if(empty()){
throw new RuntimeException("队列为空");
}
//因为是从队列的头部出队，所以显示头节点的val值
return head.val;
}
public int poll()throws RuntimeException{//出队。删除队列的对头
//如果队列为空
if(empty()){
throw new RuntimeException("队列为空");
}
//保存节点
Node cur = head;
//出队，更新链表的节点，让链表的头节点变为头节点之后的有个节点
head = head.next;
//队列中的元素减一
size--;
return cur.val;
}
public int size(){
return size;
}
public boolean empty(){
if(head == null){
return true;
}
return false;
}
}
手动实现一个队列(底层为一个循环数组)
使用链表可以实现一个栈，那么使用数组可以吗？
答案：可以。
但是这样时间复杂度就会提高，它的时间复杂的为O(n),下来就该介绍循环对列了。
把数组的首尾相连。形成一个循环。如图：
为什么要在循环数组的rear下标和空一格元素空间呢？
大家先想想这个问题，什么时候判断循环数组中被存满了，什么时候队列为空。
有人肯定想也不很简单嘛，当rear下标和font下标同时指向一个元素空间的时候不就是数组为空，即队列为空吗。
但是想一想，当队列中数据存满的时候怎么办，那不就是循环数组吗，rear下标继续往后走呀，这也不就成了rear下标要和font下标重合吗？
仔细想一想为什么要要故意在循环数组中空一格。
其实有一个公式，(rear + 1) % 数组的长度，就可以在循环判断元素是否已满，就是(rear + 1) % 数组长度 是不是等于 font，如果相等就说明数组已经满了，就返回false.
class MyCircularQueue {
public int []elem;
public int front;//队头
public int rear;//队尾
public MyCircularQueue(int k) {
this.elem = new int[k+1];//原循环队列初始化为10
}
public boolean enQueue(int val) {
//判断元素循环队列是否已满
if(isFull()){
return false;
}
this.elem[rear] = val;
int ret = this.elem[rear];
rear = (rear+1) % this.elem.length;//在队尾添加之后，rear下标向后移动
return true;
}
public boolean deQueue() {
//如果原来的循环队列为空
if(isEmpty()){
return false;
}
int ret = this.elem[front];//在队首删除元素
front = ((this.front + 1) % this.elem.length);//front更新
return true;
}
//获取队首元素
public int Front() {
if(isEmpty()){
return -1;
}
int ret = this.elem[front];
return ret;
}
//获取队尾元素
public int Rear() {
if(isEmpty()){
return -1;
}
if(this.rear == 0){
return this.elem[this.elem.length-1];
}
return this.elem[this.rear-1];
}
public boolean isEmpty() {
if(this.rear == this.front){
return true;
}
return false;
}
public boolean isFull() {
if((rear+1)%this.elem.length == front){
return true;
}
return false;
}
}
双端队列
既然是双端队列，就有和队列有着不同之处，它的特殊性在于，在双端队列中队列的两边都可以入队和出队
栈和队列的相关习题
1.括号匹配
有效括号的匹配 OJ链接
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。
解题思想：
1.如果传来的字符串为null,或者传来的字符串的长度为零，或者传来的字符串的个数为奇数(因为括号与括号之间是两两进行匹配的)返回false。
2.其次就是遍历字符串，如果遍历到了左括号，就把左括号入栈，如果遍历到了右括号就peek()一下，返回栈顶元素，判断弹出的栈顶元素和遍历到的右括号是否匹配，如果匹配就把栈顶元素删除，如果不匹配就返回false。
3.当传来的字符串为"[[[[[[[[]]",明显是左括号多的时候，当遍历完右括号的时候，这时候把和右括号等量的左括号删除，栈中还存在元素，在最后判断如果栈不为空，就返回false,即括号不匹配。
4.当传来的字符串为"{{}}}}}",是右括号多的时候，要在栈中peek()的时候，判断栈是否为空，如果为空，就直接返回false.
public static boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for(int i = 0;i<s.length();i++){
if(s.charAt(i) == '{' || s.charAt(i) == '[' ||s.charAt(i) == '('){
stack.push(s.charAt(i));
}else{
if(stack.empty()){
return false;
}
if(s.charAt(i) == '}' && stack.peek() == '{' ||s.charAt(i) == ']' && stack.peek() == '[' ||s.charAt(i) == ')' && stack.peek() == '('){
stack.pop();
}else{
return false;//括号不匹配
}
}
}
//如果栈不为空，说明左括号多
if(!stack.empty()){
return false;
}
return true;
}
2.后缀表达式转化成为中缀表达式，并计算结果
后缀表达式转化 OJ链接
有效的算符包括 +、-、、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = [“2”,“1”,"+",“3”,""]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = [“4”,“13”,“5”,"/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
解题思想：
1.还是先排除边界，如果传来的字符串数组为null,或者字符串数组的长度为0，就返回-1
2.遍历字符串数组，如果遍历到了数字字符串，就把这个字符串转化成为数字，然后把这个数组压到栈中，如果遍历到了非数字字符串，当字符串为 "+"，或者为"*" 的时候，弹出栈中的两个元素，进行加法，或者乘法。完成计算之后，把计算出来的结果，压到栈中，如果遍历到了"-"或者是"/"的话，注意先出栈的是减数，或者是除数，后出栈的元素为被减数或者除数。
3.最后栈中，只有一个数据，直接peek()一下，就完了。
public static boolean isNumber(String taken){
if(!("+".equals(taken) ||"-".equals(taken) ||"*".equals(taken) ||"/".equals(taken)){
return true;
}
return false;
}
public static int evalRPN(String[] tokens) {
if(tokens == null){
return -1;
}
Stack<Integer>stack = new Stack<>();
//遍历String 类型的字符串，当遍历到时数字字符的时候，就把该数字压到栈中
for(int i = 0;i<tokens.length;i++){
String str = tokens[i];
if(isNumber(str)){//如果遍历到了数字字符，那么把数字字符压栈
stack.push(Integer.parseInt(str));
}else{//如果遍历到了加减乘除好，那么把数字出栈
int num2 = stack.pop();
int num1 = stack.pop();
if(str.equals("+")){
stack.push(num1 + num2);
}else if(str.equals("-")){
stack.push(num1 - num2);
}else if(str.equals("*")){
stack.push(num1 * num2);
}else if(str.equals("/")){
stack.push(num1 / num2);
}
}
}
return stack.peek();//最后栈中就只剩下一个元素
}
3.实现最小栈
实现最小栈 OJ链接
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。
示例: 输入：
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]] 输出： [null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin();
–> 返回 -2.
解题思想：
1.先创建两个栈的对象，一个为普通栈，一个为最小栈，和为最小栈，即栈顶元素是栈中所有元素栈中最小的一个。
2.当要实现push()的时候，把每个数据都压到普通栈中，当最小栈为空时，和普通栈一起把相同的数据压到栈中，当最小栈不为空的时候，当我们要在最小栈压入元素的时候，每次都要拿最小栈的栈顶元素和新压到普通栈中的元素进行比较，如果比最小栈栈顶元素小或者等于，就压到最小栈，否则就不压入。
3.当要实现pop()方法的时候，删除普通栈的栈顶元素，看删除的这个元素和最小栈中的栈顶元素是否相同，如果相同，也把最小栈中的栈顶元素进行删除。
4.当要实现peek()方法的时候，直接返回普通栈中的栈顶元素。
5.当要实现getMin()方法时，直接返回最小栈的栈顶元素。
class MinStack {
Stack<Integer>stack1 = new Stack<>();
Stack<Integer> minStack = new Stack<>();
//如果最小栈中为空，那么和原栈中添加同样的数据，如果不为空，就和上次添加到最小栈中的元素进行比较，小的话添加到最小栈中
public void push(int val) {
stack1.push(val);
if(minStack.empty()){
minStack.push(stack1.push(val));
}else{
//和上一次比较
if(stack1.push(val) <= minStack.peek()){
minStack.push(val);
}
}
}
public void pop() {
stack1.pop();
if(stack1.pop().equals(minStack.peek())){
minStack.pop();
}
}
public int top() {
return stack1.peek();
}
public int getMin() {
return minStack.peek();
}
}
4.两个栈实现一个队列
两个栈实现一个队列 OJ链接
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek()
返回队列开头的元素 boolean empty() 如果队列为空，返回 true ；否则，返回 false
解题思想：
1.首先新建两个栈stack1和stack2,在两个栈中还没有数据的时候，默认在stack1z中添加数据，这就实现了push()。
2.当stack2为空时，把stack1中的所有数据全部压到stack2中，这样就把stack1中的元素顺序颠倒了过来，这样出栈的时候，就实现了出队。
动图分析：
3.要实现peek()方法，就直接返回stack2中的栈顶元素。
4.要实现empty()方法，当两个栈都为空时，队列为空
class MyQueue {
Stack<Integer>stack1 = new Stack<>();
Stack<Integer>stack2 = new Stack<>();
public void push(int x) {
stack1.push(x);
}
public int pop() {
if(empty()){
return -1;
}
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
public int peek() {
if(empty()){
return -1;
}
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
public boolean empty() {
return stack1.empty() && stack2.empty();
}
}
5.两个队列实现一个栈
两个队列实现一个栈 OJ链接
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。 int pop() 移除并返回栈顶元素。 int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的基本操作` —— 也就是 push to back、peek/pop from front、size 和 is empty
这些操作。 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 ,
只要是标准的队列操作即可。
1.在删除的时候，将一个队列中的size-1个元素移到另一个队列中，剩下的一个元素就是要进行删除的元素
2. 在我们获得栈顶时，就是peek，就是获取要删除的元素，把一个队列中的所有元素全部移到另一个队列中，标记最后一个元素
3.添加元素的时候，如果两个队列都为空，就把所有的元素默认的添加到queue1中，如果有一个队列不为空，就把元素添加到这个队列中
4.判断栈`是否为空，如果两个队列都为空，栈就为空
class MyStack {
Queue<Integer> queue1 = new LinkedList<>();
Queue<Integer> queue2 = new LinkedList<>();
//添加
public void push(int x) {
//在第一次添加的时候，因为两个队列都为空，所以第一次默认在queue1中添加数据，以后在添加数据的时候，就在
//不为空的队列中添加
if(queue1.isEmpty() && queue2.isEmpty()){
queue1.offer(x);
}else{
//不是第一次添加
if(!queue1.isEmpty()){
queue1.offer(x);
return;
}
queue2.offer(x);
return;
}
}
//删除栈顶元素
public int pop() {
//删除栈顶元素，在不为空的队列中，把size-1个数据向为空的队列中添加，剩下的一个元素就是要进行删除的元素
if(empty()){
return -1;
}
int e = 0;
if(!queue1.isEmpty()){
int size = queue1.size();
for(int i = 0;i<size-1;i++){
e = queue1.poll();
queue2.offer(e);
}
e = queue1.poll();
}else{
int size = queue2.size();
for(int i = 0;i<size-1;i++){
e = queue2.poll();
queue1.offer(e);
}
e = queue2.poll();
}
return e;
}
//获取栈顶元素，不删除
//把不空的队列移到空的队列，记录最后一个元素
public int top() {
if(empty()){
return -1;
}
int e = 0;
if(!queue1.isEmpty()){
int size = queue1.size();
for(int i = 0;i<size;i++){
e = queue1.poll();
queue2.offer(e);
}
}else{
int size = queue2.size();
for(int i = 0;i<size;i++){
e = queue2.poll();
queue1.offer(e);
}
}
return e;
}
//判断栈是否为空
public boolean empty() {
if(queue1.isEmpty() && queue2.isEmpty()){
return true;
}else{
return false;
}
}
}
6.棒球比赛
棒球比赛 OJ链接
你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。
比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：
整数 x - 表示本回合新获得分数 x
“+” - 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。
“D” - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。
“C” - 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。
请你返回记录中所有得分的总和。
解题思想：
- 本题解决思想：遍历字符串，首先排除边界条件，如果字符串为空，或者字符串的长度为0，直接返回-1.
- .遍历字符串，当遇到数字字符的时候，使用栈这个栈这个数据结构，把数字字符转化成数字，压到栈中。
- 当遍历到’C’字符的时候，就删除栈顶元素。
- .当遍历到’D’字符的时候，在栈中压入一个值，这个值等于栈顶元素的两倍
- 当遍历到’+'字符的时候，把栈中的栈顶元素和栈顶元素在栈中的下一个元素，加起来，然后压到栈中。
- 之后把所有栈中的元素相加
class Solution {
public boolean isNumber(String str){
return !(str.equals("+")) && !(str.equals("D")) && !(str.equals("C"));
}
public int calPoints(String[] ops) {
//排除边界条件
if(ops == null || ops.length == 0){
return -1;
}
int prevC = 0;
Stack<Integer> stack = new Stack<>();
for(int i = 0;i<ops.length;i++){
String str = ops[i];
if(isNumber(str)){
stack.push(Integer.parseInt(str));
}else{
switch (str){
//表示本回合新获得的得分是前两次得分的总和
case "+"://stack.push(prevC + stack.peek());
int num1 = stack.peek();
int num2 = stack.pop();
int num3 = stack.peek(); //找到栈顶元素之下的元素
stack.push(num2);
stack.push(num1 + num3);
continue;
case "C":stack.pop();
continue;
case "D":stack.push(stack.peek() * 2);
}
}
}
int sum = 0;
while(!stack.empty()){
sum += stack.pop();
}
return sum;
}
}
7.栈的压入，弹出序列
OJ链接
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
- 0<=pushV.length == popV.length <=1000
- -1000<=pushV[i]<=1000
- pushV 的所有数字均不相同
示例1 输入： [1,2,3,4,5],[4,5,3,2,1] 返回值： true 说明： 可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop() 这样的顺序得到[4,5,3,2,1]这个序列，返回true
解题思想：将数组pushA中的数据挨个的进行入栈，当每一个元素入栈之后，peek()一下，如果和数组popA中的元素相同，就把这个栈顶元素出 ，最后如果栈为空，说明popA和 pushA是一对压入，弹出序列
import java.util.ArrayList;
import java.util.Stack;public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer>stack = new Stack<>();
//在入栈的时候，遍历出栈数组，如果相等，就出模拟栈，如果不相等就就继续入栈
int j = 0;
for(int i = 0;i<pushA.length;i++){
stack.push(pushA[i]);
while(!stack.empty() && stack.peek() == popA[j]){
stack.pop();
j++;
}
}
return stack.empty();//如果栈为空，返回true
}
}
8.比较含有退格的字符串
OJ链接
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。
如果相等，返回 true ；否则，返回 false 。
注意：如果对空文本输入退格字符，文本继续为空。
示例 1：
输入：s = “ab#c”, t = “ad#c” 输出：true 解释：S 和 T 都会变成 “ac”。
解题思想：
- 这里说的退格是，当你输入一个字符时，如果按下退格这个字符就会被删除，这里使用到了栈，删除的时候，就是用pop方法
- 在遍历字符串是如果遇到了字母字符，就把字母字符压到栈中，如果遍历到了’#’，’#'不能入栈，并且要删除栈顶元素。
- 最后比较两个栈中元素的个数，如果不相等，那么直接false,如果个数相等，那么继续向下执行 比较栈中的每个字符是否相等
- 注意：在栈为空的时候，遍历到’#'的时候，不执行删除栈中元素
class Solution {
public boolean backspaceCompare(String s, String t) {
if(s == null && t == null){ //如果两个字符串都为空
return true;
}
if(s == null || t == null){//如果有一个字符串为空
return false;
}
Stack<Character>stack1 = new Stack<>();
Stack<Character>stack2 = new Stack<>();
for(int i = 0;i<s.length();i++){
char ch = s.charAt(i);
if(ch == '#' && !stack1.empty()){ //空栈时，不能删除栈中元素
stack1.pop();
}
if(ch != '#'){
stack1.push(ch);
}
}
int size1 = stack1.size();
for(int i = 0;i<t.length();i++){
char ch = t.charAt(i);
if(ch == '#' && !stack2.empty()){
stack2.pop();
}
if(ch != '#'){
stack2.push(ch);
}
}
int size2 = stack2.size();
if(size1 == 0 && size2 == 0){
return true;
}
if(size1 != size2){
return false;
}
while(size1 != 0){
if(stack1.pop() != stack2.pop()){
return false;
}
size1--;
}
return true;
}
}
9.猫狗收容所
OJ链接
给定一个栈及一个操作序列int[][2] ope(C++中为vector<vector>)，代表所进行的入栈出栈操作。第一个元素为1则入栈，第二个元素为数的正负号；第一个元素为2则出栈，第二个元素若为0则出最先入栈的那个数，为1则出最先入栈的正数，为-1则出最先入栈的负数。请按顺序返回出栈的序列，并做异常处理忽略错误操作。
测试样例： [[1,1],[1,-1],[2,0],[2,-1]] 返回：[1,-1]
解题思想：
- 本题解法：在题目中是这样告诉的重点在于他要取到当二维数组的第一个元素为2是出栈，当第二个元素为-1时，取最先入栈的负数，根据栈的特性，要结果本题，不能用栈，因为栈的特性是，只能从数组的一端进行删除和增加，考虑到队列，队列也不可以，因为队列的特性是在数组的一端进行添加，另一端进行删除，不能遍历到数组的中间元素。因为要遍历到数组的中间元素所以能够想到list。
- 如果遍历到的二维数组中第一个元素为1，就执行添加操作，把对应的第二个元素添加到list中
- 如果第一个元素不是1，当第二个元素为0的时候,返回list中的第一个元素,在ret中添加list中的第一个元素
- 如果第一个元素不1，当第二个元素为1的时候，返回list中从下标为0，开始的第一个正数，在ret中添加这个正数
- 如果第一个元素不为1，当第二个元素为-1的时候，返回list中从下标为0，看是的第一个负数，在ret中添加这个负数
import java.util.*;
public class CatDogAsylum {
public static ArrayList<Integer> asylum(int[][] ope) {
//排除边界条件
if (ope == null) {
return null;
}
ArrayList<Integer> list = new ArrayList<>();
ArrayList<Integer> re = new ArrayList<>();
for(int i = 0;i<ope.length;i++){
if(ope[i][0] == 1){
list1.add(ope[i][1]);
}else{
if(ope[i][1] == 0) {
list.add(list1.get(0));
list1.remove(0);
}else if(ope[i][1] == 1){
//在list中从前删除list中的第一个整数
for(int j = 0;j<list1.size();j++){
if(list1.get(j) * -1 < 0){
list.add(list1.get(j));
list1.remove(j);
break;
}
}
}else{
for(int j = 0;j<list1.size();j++){
if(list1.get(j) * -1 > 0){
list.add(list1.get(j));
list1.remove(j);
break;
}
}
}
}
}
return list;
}
}
-
Java部署教程：新手入门指南11-01
-
Java部署教程：从入门到实践11-01
-
Java订单系统教程：新手入门指南11-01
-
Java分布式教程：新手入门指南11-01
-
Java管理系统教程：新手入门详解11-01
-
Java监控系统教程：从入门到实践11-01
-
SpringCloud Alibaba入门：轻松搭建微服务架构11-01
-
Swagger入门：新手必读指南11-01
-
Swagger入门：轻松搭建API文档11-01
-
uni-APP入门：新手快速上手指南11-01
-
UNI-APP入门：新手必读的开发指南11-01
-
手把手教你学习编译部署教程11-01
-
编译部署SpringCloudAlibaba教程：新手入门指南11-01
-
订单微服务系统教程：新手入门必备指南11-01
-
订单系统教程：新手入门指南11-01
