目錄

一，棧（Stack）

1.1 概念

1.2 棧的使用

1.3 棧的模擬實(shí)現(xiàn)

1.4 棧的應(yīng)用場景

1.5 棧，虛擬機(jī)棧，棧幀有什么區(qū)別？

二，隊列（Queue）

2.1 概念

2.2 隊列的使用

?2.3 隊列模擬實(shí)現(xiàn)

2.4 循環(huán)隊列

三，雙端隊列

一，棧（Stack）

1.1 概念

1.2 棧的使用

public static void main(String[] args) {

Stack<Integer> s = new Stack();

s.push(1);

s.push(2);

s.push(3);

s.push(4);

System.out.println(s.size()); // 獲取棧中有效元素個數(shù)---> 4

System.out.println(s.peek()); // 獲取棧頂元素---> 4

s.pop(); // 4出棧，棧中剩余1 2 3，棧頂元素為3

System.out.println(s.pop()); // 3出棧，棧中剩余1 2 棧頂元素為3

if(s.empty()){

System.out.println("棧空");

}else{

System.out.println(s.size());

}

}

1.3 棧的模擬實(shí)現(xiàn)

public interface IStack {
    //入棧
    public int push(int val);
    //出棧
    public int pop();
    //獲取棧頂元素
    public int peek();
    //獲取棧內(nèi)有多少元素
    public int size();
    //檢查棧是否為空
    public boolean empty();
    //已滿擴(kuò)容
    public void full();
}

import java.util.Arrays;

public class MyStack implements IStack{
    int[] array;
    int size;
    static final int capacity = 3;
    public MyStack() {
        array = new int[capacity];
    }
    //入棧
    @Override
    public int push(int val) {
        if (isFull()) {
            full();
        }
        array[size] = val;
        size++;
        return val;
    }

    //出棧
    //先進(jìn)先出
    @Override
    public int pop() throws EmptyStackException{
        if (empty()) {
            throw new EmptyStackException("空棧異常");
        } else {
            int val = array[size-1];
            array[size-1] = 0;
            size--;
            return val;
        }
    }

    //獲取棧頂元素
    @Override
    public int peek() throws EmptyStackException{
        if (empty()) {
            throw new EmptyStackException("空棧異常");
        } else {
            return array[size - 1];
        }
    }

    //獲取棧內(nèi)有多少元素
    @Override
    public int size() {
        return size;
    }

    //檢查棧是否為空
    @Override
    public boolean empty() {
        return size == 0;
    }

    @Override
    public void full() {
        if (isFull()) {
            //擴(kuò)容
            array = Arrays.copyOf(array,array.length * 2);
        }
    }
    //檢查棧是否已滿
    private boolean isFull() {
        return size() == capacity;
    }

    //打印棧
    public void display() {
        for (int i = 0; i < size; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println(" ");
    }
}

public boolean isValid(String s) {
        Stack<Character> sta = new Stack<>();
        //遍歷字符串
        for (int i = 0; i < s.length(); i++) {
            //判斷是不是左括號
            char ch = s.charAt(i);
            if (ch == '{' || ch == '[' || ch == '(') {
                sta.push(ch);
            } else {
                //遇到右括號
                if (sta.empty()) {
                    return false;
                } else {
                    char ch2 = sta.peek();
                    if ((ch2 == '(' && ch == ')') || (ch2 == '[' && ch == ']') || (ch2 == '{' && ch == '}')) {
                        sta.pop();
                    } else {
                        return false;
                    }
                }
            }
        }
        if (!sta.empty()) {
            return false;
        }
        return true;
    }
}

import java.util.Stack;

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String x:tokens) {
            if (!isOperator(x)) {
                stack.push(Integer.parseInt(x));
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (x) {
                    case "+" :
                        stack.push(num1 + num2);
                        break;
                    case "-" :
                        stack.push(num1 - num2);
                        break;
                    case "*" :
                        stack.push(num1 * num2);
                        break;
                    case "/" :
                        stack.push(num1 / num2);
                        break;
                }
            }
        }
        return stack.pop();
    }
    private boolean isOperator(String s) {
        if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
            return true;
        }
        return false;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
     *
     *
     * @param pushV int整型一維數(shù)組
     * @param popV int整型一維數(shù)組
     * @return bool布爾型
     */
     public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for (int x:pushV) {
            stack.push(x);
            int tmp = stack.size();
            for (int j = 0; j < tmp; j++) {
                if (stack.peek() == popV[i]) {
                    stack.pop();
                    i++;
                } else {
                    break;
                }
            }
        }
        for (int j = 0; j < stack.size(); j++) {
            if (stack.pop() != popV[i]) {
                return false;
            } else {
                i++;
            }
        }
        return true;
    }
}

?該題實(shí)現(xiàn)Stack各功能比較簡單，關(guān)鍵還是如何實(shí)現(xiàn)這個最小棧上

建立如下圖兩個棧

普通棧用來實(shí)現(xiàn)棧的各功能，最小棧用來存放每次入棧的最小值

具體怎么實(shí)現(xiàn)？

當(dāng)我們放入第一個元素時，在兩個棧當(dāng)中都放入，此時minStack中棧頂元素就是stack中的最小值

隨后放入第二個元素時間就與minStack中棧頂元素進(jìn)行比較，如果較小，就在兩個棧當(dāng)都放入

隨后第三個元素比minStack棧頂元素大，就只放入普通棧

按此思路

……

此時放入的元素和minStack棧頂元素相等，故兩個棧都放入

代碼實(shí)現(xiàn)：

import java.util.Stack;

class MinStack {
     private Stack<Integer> stack;
     private Stack<Integer> minStack;
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if (minStack.empty()) {
            minStack.push(val);
        } else {
            if (val <= minStack.peek()) {
                minStack.push(val);
            }
        }
    }

    public void pop() {
        int val = minStack.peek();
        if (stack.peek() == val) {
            stack.pop();
            minStack.pop();
        } else {
            stack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
       if (!minStack.empty()) {
           return minStack.peek();
       } else {
           return -1;
       }
    }
}

1.5 棧，虛擬機(jī)棧，棧幀有什么區(qū)別？

二，隊列（Queue）

2.1 概念

2.2 隊列的使用

在Java中，Queue是個接口，底層是通過鏈表實(shí)現(xiàn)的。?

public static void main ( String [] args ) {

Queue < Integer > q = new LinkedList <> ();

q . offffer ( 1 );

q . offffer ( 2 );

q . offffer ( 3 );

q . offffer ( 4 );

q . offffer ( 5 ); // 從隊尾入隊列

System . out . println ( q . size ());

System . out . println ( q . peek ()); // 獲取隊頭元素

q . poll ();

System . out . println ( q . poll ()); // 從隊頭出隊列，并將刪除的元素返回

if ( q . isEmpty ()){

System . out . println ( " 隊列空 " );

} else {

System . out . println ( q . size ());

}

}

?2.3 隊列模擬實(shí)現(xiàn)

?

class Queue {
    //雙向鏈表節(jié)點(diǎn)
    public static class ListNode {
        ListNode prev;
        ListNode next;
        int val;
        ListNode(int val) {
            this.val = val;
        }
    }
    ListNode first; // 隊頭
    ListNode last; // 隊尾
    int size = 0;
    // 入隊列---向雙向鏈表位置插入新節(jié)點(diǎn)
    public void offer(int e){
        ListNode node = new ListNode(e);
        if (first == null) {
            first = node;
        } else {
            last.next = node;
        }
        last = node;
        size++;
    }

    // 出隊列---將雙向鏈表第一個節(jié)點(diǎn)刪除掉
    public int poll() {

        // 1. 隊列為空
        if (first == null) {
            return -1;
        }

        int val = first.val;
        // 2. 隊列中只有一個元素----鏈表中只有一個節(jié)點(diǎn)---直接刪除
        if (first == last) {
            first = null;
            last = null;
        } else {
            // 3. 隊列中有多個元素---鏈表中有多個節(jié)點(diǎn)----將第一個節(jié)點(diǎn)刪除
            first = first.next;
            first.prev.next = null;
            first.prev = null;
        }
        size--;
        return val;
    }

    // 獲取隊頭元素---獲取鏈表中第一個節(jié)點(diǎn)的值域
    public int peek() {
        if (first == null) {
            return -1;
        }
        return first.val;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty(){ 
        return first == null; 
    }
}

2.4 循環(huán)隊列

?

?2. 下標(biāo)最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length

?

如何區(qū)分空與滿

?關(guān)于方法2：

設(shè)計循環(huán)隊列

代碼示例：

class MyCircularQueue {
    public int[] elem;
    public int front;//隊頭
    public int rare;//隊尾

    public MyCircularQueue(int k) {
       elem = new int[k + 1];
    }

    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        elem[rare] = value;
        rare = (rare + 1) % elem.length;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        elem[front] = 0;
        front = (front + 1) % elem.length;
        return true;
    }

    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return elem[front];
    }

    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        int index = (rare == 0) ? elem.length - 1 : rare - 1;
        return elem[index];
    }

    public boolean isEmpty() {
        return front == rare;
    }

    public boolean isFull() {
        return (rare + 1) % elem.length == front;
    }
}

?

三，雙端隊列

?

Deque是一個接口，使用時必須創(chuàng)建LinkedList的對象。?

?在實(shí)際工程中，使用Deque接口是比較多的，棧和隊列均可以使用該接口

Deque<Integer> stack = new ArrayDeque<>();// 雙端隊列的線性實(shí)現(xiàn)

Deque<Integer> queue = new LinkedList<>();// 雙端隊列的鏈?zhǔn)綄?shí)現(xiàn)

完。文章來源地址http://www.zghlxwxcb.cn/news/detail-786372.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)入門到入土——棧(Stack)和隊列(Queue)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！