数据结构基础之栈与队列

本文主要是介绍数据结构基础之栈与队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

1. Java中的栈Stack

栈是Vector的一个子类，它实现了一个标准的后进先出的栈。

序号	方法描述
1	boolean empty() 测试堆栈是否为空。
2	Object peek( ) 查看堆栈顶部的对象，但不从堆栈中移除它。
3	Object pop( ) 移除堆栈顶部的对象，并作为此函数的值返回该对象。
4	Object push(Object element) 把项压入堆栈顶部。
5	int search(Object element) 返回对象在堆栈中的位置，以 1 为基数。

1.1. Stack的应用之括号匹配

leetcode 20. 有效的括号

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

class Solution {public boolean isValid(String s) {Stack<Character> strStack=new Stack<Character>();for(int i=0;i<s.length();i++){switch(s.charAt(i)){case ')':if(strStack.isEmpty() || strStack.peek()!='('){return false;}strStack.pop();break;case '}':if(strStack.isEmpty() || strStack.peek()!='{'){return false;}strStack.pop();break;case ']':if(strStack.isEmpty() || strStack.peek()!='['){return false;}strStack.pop();break;default:strStack.push(s.charAt(i));break;}}if(strStack.isEmpty()){return true;}else{return false;}}
}

leetcode921. 使括号有效的最少添加

给定一个由 ‘(’ 和 ‘)’ 括号组成的字符串 S，我们需要添加最少的括号（ ‘(’ 或是 ‘)’，可以在任何位置），以使得到的括号字符串有效。
从形式上讲，只有满足下面几点之一，括号字符串才是有效的：
它是一个空字符串，或者
它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
它可以被写作 (A)，其中 A 是有效字符串。
给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。

package stack.nine_hundred_and_twenty_one;import java.util.Stack;public class Solution {public int minAddToMakeValid(String S) {Stack<Character> myStack = new Stack<Character>();for (char c : S.toCharArray()) {if (c == '(') {myStack.push(c);}if (c == ')') {if (!myStack.isEmpty() && myStack.peek() == '(') {myStack.pop();} else {myStack.push(c);}}}return myStack.size();}
}

921还有一种不需要栈的解决方法，空间复杂度可以由基于栈的$O(n)$降为$O(1)$,见https://github.com/lankuohsing/LeetCode-Java/blob/master/LeetCodeInJava/src/stack/nine_hundred_and_twenty_one/Solution2.java

2. Java中的队列Queue

队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。

LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

offer，add 区别：

一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，多出的项就会被拒绝。

这时新的 offer 方法就可以起作用了。它不是对调用 add() 方法抛出一个 unchecked 异常，而只是得到由 offer() 返回的 false。

poll，remove 区别：

remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似， 但是新的 poll() 方法在用空集合调用时不是抛出异常，只是返回 null。因此新的方法更适合容易出现异常条件的情况。

peek，element区别：

element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。

这篇关于数据结构基础之栈与队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---