java中栈stack和队列queue用法详细分析(全)

目录

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


上一篇:C++提高编程(三)—— STL常用容器(5) :stack容器


下一篇:前序遍历