栈：
引言：栈是Vector的一个子类，它实现了一个标准的后进先出的栈。 栈只定义了默认构造函数，用来创建一个空栈。 栈除了包括由Vector定义的所有方法，也定义了自己的一些方法。
创建一个空栈
Stack()；
测试栈是否为空
boolean empty()
查看栈顶部的对象，但不从栈中移除它
Object peek( )
移除栈顶部的对象，并作为此函数的值返回该对象
Object pop( )；
把项压入栈顶部：
Object push(Object element)；
返回对象在栈中的位置，以 1 为基数：
int search(Object element)；
用栈Stack 创建对象（类型不同）：
Stack stack = new Stack<>();
Stack<Character> stack = new Stack<>();
示例：
//1.创建一个字符型的栈
Stack<Character> stack=new Stack<>();
System.out.println(stack);
//2.测试栈是否为空
System.out.println(stack.empty());
//3.入栈
stack.push('a');
stack.push('b');
stack.push('c');
System.out.println(stack);
//4.查看栈顶元素
System.out.println(stack.peek());
System.out.println(stack);
//5.出栈
stack.pop();
System.out.println(stack);
//6.返回对象在栈中的位置
System.out.println(stack.search('b'));
System.out.println(stack.search('a'));
//结果
[]
true
[a, b, c]
c
[a, b, c]
[a, b]
1
2
1.前序遍历二叉树：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
//创建一个集合
List<Integer> list = new ArrayList<>();
//调用方法
pre(root,list);
//返回集合
return list;
}
public void pre(TreeNode root , List<Integer> list){
//创建一个栈
Stack<TreeNode> stack = new Stack<>();
//判断下一个根节点和栈是否为空
while(root != null || !stack.isEmpty()){
//若根节点不等于空，将节点的值放入集合中，将节点放入栈中。
while (root != null){
list.add(root.val);
stack.add(root);
//继续向左子树遍历
root = root.left;
}
//若左子树遍历完，从栈中弹出一个节点。即上一次根节点，以此来遍历右子树。以此循环来做。
root = stack.pop().right;
}
}
}
网友评论