數(shù)據(jù)結(jié)構(gòu)與算法——棧

bladefury 發(fā)布于2019-08-16 15:51 / 1738人閱讀

摘要：概述今天來看看棧這種線性數(shù)據(jù)結(jié)構(gòu)，非常的基礎(chǔ)，我舉個(gè)例子你就能明白了。這種滿足了先進(jìn)后出，后進(jìn)先出特點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，就叫做棧。相信結(jié)合上圖你能夠看到，棧這種數(shù)據(jù)結(jié)構(gòu)，插入和刪除的操作都被局限在了棧的一端，插入數(shù)據(jù)叫做入棧，刪除數(shù)據(jù)叫做出棧。

1. 概述

今天來看看棧這種線性數(shù)據(jù)結(jié)構(gòu)，非常的基礎(chǔ)，我舉個(gè)例子你就能明白了。比如你桌子上堆放的一摞文件，最先放的在最下面，拿的時(shí)候也是最后拿，最后放的在最上面，拿的時(shí)候也先拿到。這種滿足了 先進(jìn)后出，后進(jìn)先出 特點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，就叫做棧。

相信結(jié)合上圖你能夠看到，棧這種數(shù)據(jù)結(jié)構(gòu)，插入和刪除的操作都被局限在了棧的一端，插入數(shù)據(jù)叫做入棧，刪除數(shù)據(jù)叫做出棧。

2. 棧的實(shí)現(xiàn)

棧有兩種實(shí)現(xiàn)方式，一是使用數(shù)組，這種實(shí)現(xiàn)叫做順序棧，二是使用鏈表，叫做鏈?zhǔn)綏?。下面是其?shí)現(xiàn)的代碼：

順序棧的代碼實(shí)現(xiàn)

public class ArrayStack {
    
    private String[] items;//儲存數(shù)據(jù)的數(shù)組
    private int size;//棧中數(shù)據(jù)個(gè)數(shù)
    
    public ArrayStack(int capacity) {
        this.items = new String[capacity];
        this.size = 0;
    }
    
    public ArrayStack() {
        this(10);
    }
    
    //入棧
    public boolean push(String value) {
        //如果棧已滿，則擴(kuò)容數(shù)組
        if(size == items.length) resize(items.length * 2);
        
        items[size ++] = value;
        return true;
    }
    
    //出棧
    public String pop() {
        if(size == 0) return null;
        
        return items[-- size];
    }
    
    //獲取棧頂元素
    public String peek() {
        if(size == 0) return null;
        return items[size - 1];
    }

    //重新設(shè)置數(shù)組大小，用于擴(kuò)容
    private void resize(int newSize) {
        String[] temp = new String[newSize];
        for (int i = 0; i < items.length; i++) {
            temp[i] = items[i];
        }
        items = temp;
    }
}

鏈?zhǔn)綏５拇a實(shí)現(xiàn)

public class LinkedListStack {

    private Node head = null;//棧頂元素
    private int size = 0;//棧中元素個(gè)數(shù)
    
    //入棧
    public boolean push(String value) {
        Node node = new Node(value);
        if(head == null) {
            head = node;
            this.size ++;
            return true;
        }
        
        node.next = head;
        head = node;
        this.size ++;
        return true;
    }
    
    //出棧
    public String pop() {
        if(head == null) return null;
        
        String result = head.data;
        head = head.next;
        this.size --;
        return result;
    }
    
    //獲取棧頂元素
    public String peek() {
        if(head == null) return null;
        return head.getData();
    }
    
    //判斷棧是否為空
    public boolean isEmpty() {
        return this.head == null;
    }
    
    //棧中元素的個(gè)數(shù)
    public int size() {
        return this.size;
    }
    
    //清空棧
    public void clear() {
        this.head = null;
        this.size = 0;
    }
    
    //打印棧中所有的元素
    public void print() {
        Node pNode = head;
        while(pNode != null) {
            System.out.print(pNode.getData() + "  ");
            pNode = pNode.next;
        }
        
        System.out.println();
    }
    
    //定義棧的節(jié)點(diǎn)
    public static class Node{
        private String data;
        private Node next;
        public Node(String data) {
            this.data = data;
            this.next = null;
        }
        
        public String getData() {
            return data;
        }
    }
}

3. 棧練習(xí)

下面思考一個(gè)練習(xí)題：如何使用棧來實(shí)現(xiàn)瀏覽器的前進(jìn)和后退功能？我們在使用瀏覽器的時(shí)候，會新打開一個(gè)網(wǎng)頁，如果連續(xù)打開了多個(gè)網(wǎng)頁，我們可以后退，也可以前進(jìn)，如果這時(shí)候又新打開了一個(gè)網(wǎng)頁，那就不能在新頁面中前進(jìn)了。使用棧，我們可以輕松實(shí)現(xiàn)這個(gè)功能。

瀏覽器的前進(jìn)后退功能代碼實(shí)現(xiàn)

public class BrowserForwardAndBack {
    
    private LinkedListStack forward;
    private LinkedListStack back;
    
    public BrowserForwardAndBack() {
        this.forward = new LinkedListStack();
        this.back = new LinkedListStack();
    }

    //新打開一個(gè)頁面
    public void open(String url) {
        //將其保存到前進(jìn)的棧中
        this.forward.push(url);
        //如果后退的棧不為空，則清空后退的棧
        if(!back.isEmpty()) back.clear();
        
        System.out.println("新打開一個(gè)頁面，url = " + url);
    }
    
    //前進(jìn)，從back中取出內(nèi)容到forward中
    public void goForward() {
        if(this.back.isEmpty()) {
            System.out.println("前面沒有頁面！");
            return;
        }
        
        this.forward.push(this.back.pop());
        System.out.println("前進(jìn)一個(gè)頁面，當(dāng)前頁面為：" + this.forward.peek());
    }
    
    //后退，從forward中取出內(nèi)容到back中
    public void goBack() {
        if(this.forward.size() <= 1) {
            System.out.println("后面沒有頁面！");
            return;
        }
        
        this.back.push(this.forward.pop());
        System.out.println("后退一個(gè)頁面，當(dāng)前頁面為：" + this.forward.peek());
    }
}