java中栈stack和队列queue用法详细分析（全）_java中queue,stack

1.前言

栈和队列是两种重要的线性结构。从数据结构角度看，栈和队列也是线性表， 其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表，因此，可称为限定性的数据结构

2.栈stack的用法

实例化一个对象

Deque<TreeNode> stk = new LinkedList<TreeNode>();

1
2

用这个对象调用函数
判断是否为空 stk.isEmpty();
入栈stk.push();
出栈stk.pop();
显示栈顶头元素，但不移除stk.peek();

3.队列queue的用法

LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用
实例化一个对象

Queue<TreeNode> q = new LinkedList<TreeNode>();
1

用这个对象调用函数
判断是否为空 q.isEmpty();
添加元素q.offer();
删除元素q.poll();
显示队列头元素但不移除q.peek();

---

常用的函数用法有这些

offer(); add();//表示增加元素
poll();remove();//表示移除元素
element();peek();//显示队列头一个元素，不会删除元素
1
2
3

区别
add()，remove()，element()出错的时候会抛出异常，比如队列满了，add会抛出异常
而offer()，poll()，peek()l则不会抛出异常，offer显示false，poll显示null，peek显示null。

---

4.额外补充

数组的实例化对象

List<Integer> res = new ArrayList<Integer>();
1

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;
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

对称二叉树用队列实现

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);
    }
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26