數據結構與算法——棧

bladefury 發布于2019-08-16 15:51 / 1729人閱讀

摘要：概述今天來看看棧這種線性數據結構，非常的基礎，我舉個例子你就能明白了。這種滿足了先進后出，后進先出特點的數據結構，就叫做棧。相信結合上圖你能夠看到，棧這種數據結構，插入和刪除的操作都被局限在了棧的一端，插入數據叫做入棧，刪除數據叫做出棧。

1. 概述

今天來看看棧這種線性數據結構，非常的基礎，我舉個例子你就能明白了。比如你桌子上堆放的一摞文件，最先放的在最下面，拿的時候也是最后拿，最后放的在最上面，拿的時候也先拿到。這種滿足了 先進后出，后進先出 特點的數據結構，就叫做棧。

相信結合上圖你能夠看到，棧這種數據結構，插入和刪除的操作都被局限在了棧的一端，插入數據叫做入棧，刪除數據叫做出棧。

2. 棧的實現

棧有兩種實現方式，一是使用數組，這種實現叫做順序棧，二是使用鏈表，叫做鏈式棧。下面是其實現的代碼：

順序棧的代碼實現

public class ArrayStack {
    
    private String[] items;//儲存數據的數組
    private int size;//棧中數據個數
    
    public ArrayStack(int capacity) {
        this.items = new String[capacity];
        this.size = 0;
    }
    
    public ArrayStack() {
        this(10);
    }
    
    //入棧
    public boolean push(String value) {
        //如果棧已滿，則擴容數組
        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];
    }

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

鏈式棧的代碼實現

public class LinkedListStack {

    private Node head = null;//棧頂元素
    private int size = 0;//棧中元素個數
    
    //入棧
    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;
    }
    
    //棧中元素的個數
    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();
    }
    
    //定義棧的節點
    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. 棧練習

下面思考一個練習題：如何使用棧來實現瀏覽器的前進和后退功能？我們在使用瀏覽器的時候，會新打開一個網頁，如果連續打開了多個網頁，我們可以后退，也可以前進，如果這時候又新打開了一個網頁，那就不能在新頁面中前進了。使用棧，我們可以輕松實現這個功能。

瀏覽器的前進后退功能代碼實現

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

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

GPU云服務器云服務器算法與數據結構數據結構與算法數據結構與算法教程數據結構與算法答案

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/73739.html

學習數據結構與算法之棧與隊列

摘要：于是翻出了機房里的這本學習數據結構與算法開始學習程序員的基礎知識。這本書用了我最熟悉的來實現各種數據結構和算法，而且書很薄，可以說是一本不錯的入門教程。隊列在頭部刪除元素，尾部添加元素。本系列所有文章：第一篇文章：學習數據結構與算法之棧與隊列第二篇文章：學習數據結構與算法之鏈表第三篇文章：學習數據結構與算法之集合第四篇文章：學習數據結構與算法之字典和散列表第五篇文章：學習數據結構與算...

pingan8787 2019-08-20 18:37 評論0 收藏0
JS數據結構與算法_棧&隊列

摘要：下一篇數據結構與算法鏈表寫在前面說明數據結構與算法系列文章的代碼和示例均可在此找到原計劃是把你不知道的三部全部看完的，偶然間朋友推薦了數據結構與算法的一套入門視頻，學之。手頭上恰好有學習數據結構與算法的書籍，便轉而先把數據結構與算法學習。下一篇：JS數據結構與算法_鏈表寫在前面說明：JS數據結構與算法系列文章的代碼和示例均可在此找到原計劃是把《你不知道的Javascript》...

AndroidTraveler 2019-08-23 14:45 評論0 收藏0
學習JavaScript數據結構與算法（一）：棧與隊列

摘要：之數組操作接下來就是數據結構的第一部分，棧。以字符串顯示棧中所有內容方法的實現說明需要往棧中添加新元素，元素位置在隊列的末尾。的前端樂園原文鏈接寒假前端學習學習數據結構與算法，棧與隊列本系列的第一篇文章: 學習JavaScript數據結構與算法（一），棧與隊列第二篇文章：學習JavaScript數據結構與算法（二）：鏈表第三篇文章：學習JavaScript數據結構與算法（三）：集合第...

Flink_China 2019-08-19 17:23 評論0 收藏0
JavaScript數據結構與算法—— 棧

摘要：棧數據結構棧是一種遵循后進先出原則的有序集合。新添加的或待刪除的元素都保存在棧的同一端，叫做棧頂，另一端叫棧底。在棧中，新元素靠近棧頂，舊元素接近棧底。我們可以在數組的任何位置上刪除或者添加元素，但有時候我們還需要在元素的添加或刪除時有更多控制的數據結構，有兩種數據結構類似于數組，但在添加或刪除元素時更為可控，它們就是棧和隊列。本節主要介紹棧。 1.棧數據結構棧是一種遵循后進先出（...

王巖威 2019-08-23 15:11 評論0 收藏0
Java數據結構與算法[原創]——棧

摘要：前言數據結構與算法專題會不定時更新，歡迎各位讀者監督。方法調用編寫的程序在進行方法函數調用時，會完成對方法的壓棧操作，等方法執行結束后，對應的會完成對方法的彈棧操作。聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。前言：Java數據結構與算法專題會不定時更新，歡迎各位讀者監督。本文介紹數據結構中的棧的概念、存儲結構、棧的特點以及棧的適用場景，另外會穿插介紹面試中的一些經典問題...

hiyang 2019-08-19 10:42 評論0 收藏0
算法面試：隊列實現棧的方案

摘要：基本解決方案按照上述的大體思路，我們給出解決方案入棧和出棧都在中完成，只作為臨時中轉空間。入棧入隊出棧除隊尾的元素外將其他所有元素出隊，再入隊中轉暫存，然后將中的元素出隊出棧。聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。前言：Java數據結構與算法專題會不定時更新，歡迎各位讀者監督。本篇介紹的是如何用兩個隊列實現棧的問題。這道題作為上一篇文章算法面試：棧實現隊列的方案的姊...

dabai 2019-08-16 11:06 評論0 收藏0