java中棧stack和隊列queue用法詳細分析（全）

目錄

• 1.前言
• 2.棧stack的用法
• 3.隊列queue的用法
• 4.額外補充
• 5.具體案列測試

1.前言

棧和隊列是兩種重要的線性結構。從資料結構角度看，棧和隊列也是線性表， 其特殊性在于棧和隊列的基本操作是線性表操作的子集，它們是操作受限的線性表，是以，可稱為限定性的資料結構

2.棧stack的用法

執行個體化一個對象

用這個對象調用函數

判斷是否為空

stk.isEmpty();

入棧

stk.push();

出棧

stk.pop();

顯示棧頂頭元素，但不移除

stk.peek();

3.隊列queue的用法

LinkedList類實作了Queue接口，是以我們可以把LinkedList當成Queue來用

執行個體化一個對象

用這個對象調用函數

判斷是否為空

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.額外補充

數組的執行個體化對象

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