數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)列

Stack

  • 棧也是一種線性結(jié)構(gòu)
  • 相比數(shù)組,棧對(duì)應(yīng)的操作是數(shù)組的子集
  • 棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)(LIFO)
  • 只能從一端添加元素,也只能從一端取出元素
  • 這一端稱為棧頂


棧的應(yīng)用是非常廣泛的,如無處不在的撤銷操作,程序運(yùn)行時(shí)調(diào)用的系統(tǒng)棧,剪貼板里面的內(nèi)容等等

創(chuàng)建自己的棧

首先確定棧的方法,創(chuàng)建棧的接口

public interface Stack<E> {

    int getSize();
    boolean isEmpty();
    void push(E e); //入棧
    E pop();    //出棧
    E peek();   //看一下棧頂元素
}

借用上面自定義中的數(shù)組來實(shí)現(xiàn)棧
創(chuàng)建ArrayStack類,實(shí)現(xiàn)接口中的方法

public class ArrayStack<E> implements Stack<E> {

    private Array<E> array;

    public ArrayStack(int capacity){
        array = new Array<>(capacity);
    }

    public ArrayStack(){
        array = new Array<>();
    }

    @Override
    public int getSize(){
        return array.getSize();
    }

    @Override
    public boolean isEmpty(){
        return array.isEmpty();
    }

    public int getCapacity(){
        return array.getCapacity();
    }

    @Override
    public void push(E e){
        array.addLast(e);
    }

    @Override
    public E pop(){
        return array.removeLast();
    }

    @Override
    public E peek(){
        return array.getLast();
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Stack: ");
        res.append('[');
        for(int i = 0 ; i < array.getSize() ; i ++){
            res.append(array.get(i));
            if(i != array.getSize() - 1)
                res.append(", ");
        }
        res.append("] top");
        return res.toString();
    }
}

根據(jù)棧的特性,在Array類中添加兩個(gè)方法

    public E getLast(){
        return get(size - 1);
    }

    public E getFirst(){
        return get(0);
    }

創(chuàng)建main函數(shù)進(jìn)行測(cè)試

public class Main {

    public static void main(String[] args) {

        ArrayStack<Integer> stack = new ArrayStack<>();

        for(int i = 0 ; i < 5 ; i ++){
            stack.push(i*i);
            System.out.println(stack);
        }

        stack.pop();
        System.out.println(stack);
    }
}

結(jié)果

Stack: [0] top
Stack: [0, 1] top
Stack: [0, 1, 4] top
Stack: [0, 1, 4, 9] top
Stack: [0, 1, 4, 9, 16] top
Stack: [0, 1, 4, 9] top

時(shí)間復(fù)雜度分析

push和pop可能會(huì)觸發(fā)resize操作

  • int getSize(); O(1)
  • boolean isEmpty(); O(1)
  • void push(E e); O(1) 均攤
  • E pop(); O(1) 均攤
  • E peek(); O(1)

Queue

  • 棧隊(duì)列也是一種線性結(jié)構(gòu)
  • 相比數(shù)組, 隊(duì)列對(duì)應(yīng)的操作也是數(shù)組的子集
  • 隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)(FIFO)
  • 只能從一端(隊(duì)尾)添加元素,也只能從一端(隊(duì)首)取出元素

創(chuàng)建自己的隊(duì)列

確定隊(duì)列的方法, 創(chuàng)建隊(duì)列的接口

public interface Queue<E> {

    int getSize();
    boolean isEmpty();
    void enqueue(E e);  //入隊(duì)
    E dequeue();        //出隊(duì)
    E getFront();       //查看隊(duì)首
}

依然使用自己創(chuàng)建的動(dòng)態(tài)數(shù)組來實(shí)現(xiàn)隊(duì)列
創(chuàng)建ArrayQueue類, 實(shí)現(xiàn)Queue的方法, 并進(jìn)行測(cè)試

public class ArrayQueue<E> implements Queue<E> {

    private Array<E> array;

    public ArrayQueue(int capacity){
        array = new Array<>(capacity);
    }

    public ArrayQueue(){
        array = new Array<>();
    }

    @Override
    public int getSize(){
        return array.getSize();
    }

    @Override
    public boolean isEmpty(){
        return array.isEmpty();
    }

    public int getCapacity(){
        return array.getCapacity();
    }

    @Override
    public void enqueue(E e){
        array.addLast(e);
    }

    @Override
    public E dequeue(){
        return array.removeFirst();
    }

    @Override
    public E getFront(){
        return array.getFirst();
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Queue: ");
        res.append("front [");
        for(int i = 0 ; i < array.getSize() ; i ++){
            res.append(array.get(i));
            if(i != array.getSize() - 1)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }

    public static void main(String[] args) {

        //每入隊(duì)三個(gè), 出隊(duì)一個(gè)
        ArrayQueue<Integer> queue = new ArrayQueue<>();
        for(int i = 0 ; i < 10 ; i ++){
            queue.enqueue(i);
            System.out.println(queue);
            if(i % 3 == 2){
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

輸出結(jié)果

Queue: front [0] tail
Queue: front [0, 1] tail
Queue: front [0, 1, 2] tail
Queue: front [1, 2] tail
Queue: front [1, 2, 3] tail
Queue: front [1, 2, 3, 4] tail
Queue: front [1, 2, 3, 4, 5] tail
Queue: front [2, 3, 4, 5] tail
Queue: front [2, 3, 4, 5, 6] tail
Queue: front [2, 3, 4, 5, 6, 7] tail
Queue: front [2, 3, 4, 5, 6, 7, 8] tail
Queue: front [3, 4, 5, 6, 7, 8] tail
Queue: front [3, 4, 5, 6, 7, 8, 9] tail

時(shí)間復(fù)雜度

  • int getSize(); O(1)
  • boolean isEmpty(); O(1)
  • void enqueue(E e); O(1) 均攤
  • E dequeue(); O(n)
  • E getFront(); O(1)

循環(huán)隊(duì)列

數(shù)組隊(duì)列在出隊(duì)時(shí)由于需要將后面的元素都向前挪一位,時(shí)間復(fù)雜度是O(n),如果使用循環(huán)隊(duì)列,時(shí)間復(fù)雜度就會(huì)降低

創(chuàng)建LoopQueue類,進(jìn)行測(cè)試

public class LoopQueue<E> implements Queue<E> {

    private E[] data;
    private int front, tail;
    private int size;

    //由于判空的條件是front == tail,
    //當(dāng)front不在下標(biāo)為o的位置,隊(duì)列滿時(shí),tail會(huì)從頭開始
    //因?yàn)榕锌諚l件是front == tail,
    //所以判滿條件是(tail + 1) % data.length == front
    //這樣就應(yīng)該在創(chuàng)建隊(duì)列時(shí)多開辟一個(gè)空間
    //      front
    //        ↓
    //?????????
    //      ↑
    //     tail
    public LoopQueue(int capacity){
        data = (E[])new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue(){
        this(10);
    }

    public int getCapacity(){
        return data.length - 1;
    }

    @Override
    public boolean isEmpty(){
        return front == tail;
    }

    @Override
    public int getSize(){
        return size;
    }

    // 入隊(duì)時(shí)首先判斷一下隊(duì)列是否已滿
    // 已滿的話需要進(jìn)行擴(kuò)容
    @Override
    public void enqueue(E e){

        if((tail + 1) % data.length == front)
            resize(getCapacity() * 2);

        data[tail] = e;
        tail = (tail + 1) % data.length;
        size ++;
    }

    // 出隊(duì)時(shí)需要將隊(duì)首向后挪一位
    // 判斷一下是否需要縮絨
    @Override
    public E dequeue(){

        if(isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size --;
        if(size == getCapacity() / 4 && getCapacity() / 2 != 0)
            resize(getCapacity() / 2);
        return ret;
    }

    // 看一眼隊(duì)首數(shù)據(jù)
    @Override
    public E getFront(){
        if(isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return data[front];
    }

    // 改變?nèi)萘繒r(shí)依然需要多開辟一個(gè)空間
    private void resize(int newCapacity){

        E[] newData = (E[])new Object[newCapacity + 1];
        for(int i = 0 ; i < size ; i ++)
            newData[i] = data[(i + front) % data.length];

        data = newData;
        front = 0;
        tail = size;
    }

    // 重寫toString方法時(shí)
    // 需要注意for 循環(huán)的起始位置和終止條件
    @Override
    public String toString(){

        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity()));
        res.append("front [");
        for(int i = front ; i != tail ; i = (i + 1) % data.length){
            res.append(data[i]);
            if((i + 1) % data.length != tail)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }

    public static void main(String[] args){

        LoopQueue<Integer> queue = new LoopQueue<>(5);
        for(int i = 0 ; i < 10 ; i ++){
            queue.enqueue(i);
            System.out.println(queue);

            if(i % 3 == 2){
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

循環(huán)隊(duì)列的時(shí)間復(fù)雜度

  • int getSize(); O(1)
  • boolean isEmpty(); O(1)
  • void enqueue(E e); O(1) 均攤
  • E dequeue(); O(1) 均攤
  • E getFront(); O(1)

數(shù)組隊(duì)列和循環(huán)隊(duì)列的比較

創(chuàng)建一個(gè)main函數(shù)進(jìn)行測(cè)試

import java.util.Random;

public class Main {

    // 測(cè)試使用q運(yùn)行opCount個(gè)enqueueu和dequeue操作所需要的時(shí)間，單位：秒
    private static double testQueue(Queue<Integer> q, int opCount){

        long startTime = System.nanoTime();

        Random random = new Random();
        for(int i = 0 ; i < opCount ; i ++)
            q.enqueue(random.nextInt(Integer.MAX_VALUE));
        for(int i = 0 ; i < opCount ; i ++)
            q.dequeue();

        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }

    public static void main(String[] args) {

        int opCount = 100000;

        ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
        double time1 = testQueue(arrayQueue, opCount);
        System.out.println("ArrayQueue, time: " + time1 + " s");

        LoopQueue<Integer> loopQueue = new LoopQueue<>();
        double time2 = testQueue(loopQueue, opCount);
        System.out.println("LoopQueue, time: " + time2 + " s");
    }
}

運(yùn)行結(jié)果

ArrayQueue, time: 58.8541207 s
LoopQueue, time: 0.0163572 s

主要差異:
ArrayQueue出隊(duì)的時(shí)間復(fù)雜度是O(n)級(jí)別的,再加上外層的循環(huán)就是O(n^2)級(jí)別的了,所以對(duì)于ArrayQueue來說,testQueue方法的時(shí)間復(fù)雜度是O(n^2)級(jí)別的; 而循環(huán)隊(duì)列出隊(duì)的時(shí)間復(fù)雜度是O(1)級(jí)別的, 再加上外層的循環(huán)就是O(n)級(jí)別的了,所以對(duì)于LoopQueue來說,testQueue方法的時(shí)間復(fù)雜度是O(n)級(jí)別的

完整代碼

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容