栈:
引言:栈是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;
}
}
}