数据结构与算法——栈

bladefury 发布于2019-08-16 15:51 / 1625人阅读

摘要：概述今天来看看栈这种线性数据结构，非常的基础，我举个例子你就能明白了。这种满足了先进后出，后进先出特点的数据结构，就叫做栈。相信结合上图你能够看到，栈这种数据结构，插入和删除的操作都被局限在了栈的一端，插入数据叫做入栈，删除数据叫做出栈。

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云服务器算法与数据结构数据结构与算法数据结构与算法教程数据结构与算法答案

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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