目录
1.前言
栈和队列是两种重要的线性结构。从数据结构角度看,栈和队列也是线性表, 其特殊性在于栈和队列的基本操作是线性表操作的子集,它们是操作受限的线性表,因此,可称为限定性的数据结构
2.栈stack的用法
实例化一个对象
Deque<TreeNode> stk = new LinkedList<TreeNode>();
用这个对象调用函数
判断是否为空 stk.isEmpty();
入栈stk.push();
出栈stk.pop();
显示栈顶头元素,但不移除stk.peek();
3.队列queue的用法
LinkedList类实现了Queue接口,因此我们可以把LinkedList当成Queue来用
实例化一个对象
Queue<TreeNode> q = new LinkedList<TreeNode>();
用这个对象调用函数
判断是否为空 q.isEmpty();
添加元素q.offer();
删除元素q.poll();
显示队列头元素但不移除q.peek();
常用的函数用法有这些
offer(); add();//表示增加元素
poll();remove();//表示移除元素
element();peek();//显示队列头一个元素,不会删除元素
区别
add(),remove(),element()出错的时候会抛出异常,比如队列满了,add会抛出异常
而offer(),poll(),peek()l则不会抛出异常,offer显示false,poll显示null,peek显示null。
4.额外补充
数组的实例化对象
List<Integer> res = new ArrayList<Integer>();
5.具体案列测试
中序遍历的用栈的迭代
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
Deque<TreeNode> stk = new LinkedList<TreeNode>();
while (root != null || !stk.isEmpty()) {
while (root != null) {
stk.push(root);
root = root.left;
}
root = stk.pop();
res.add(root.val);
root = root.right;
}
return res;
}
}
对称二叉树用队列实现
class Solution {
public:
bool check(TreeNode *u, TreeNode *v) {
queue <TreeNode*> q;
q.push(u); q.push(v);
while (!q.empty()) {
u = q.front(); q.pop();
v = q.front(); q.pop();
if (!u && !v) continue;
if ((!u || !v) || (u->val != v->val)) return false;
q.push(u->left);
q.push(v->right);
q.push(u->right);
q.push(v->left);
}
return true;
}
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
};