Data Structures (三) - 栈Stack实现

RiemannHypothesis

发布于 2022-08-19 16:09:47

2460

发布于 2022-08-19 16:09:47

文章被收录于专栏：Elixir

一、栈的基本概念

栈也是线性表的一种，但是与其他线性表不同的是，栈分为栈顶和栈底且只允许从栈顶进行操作，即入栈(push)或者出栈(pop)操作，所以栈的操作遵循后进先出的原则（Last In First Out）

由于栈的特殊性，它的方法也就与其他线性表相对来说会少一些，但是栈的本质也是数组，栈中的数据也是连续的，拥有size属性，只不过只有一端可以操作，主要包含下面这些方法

int size(); //获取栈中元素的数量
boolean isEmpty(); // 判断栈是否为空
void push(T element); // 入栈操作
T pop(); // 出栈操作
T top(); //获取栈顶的元素
void clear(); // 清空栈中的元素

二、栈的实现

栈的内部可以使用动态数组实现，即将动态数组作为栈的私有属性，如果继承动态数组的话，就不符合只能从栈顶操作栈的元素特性了。在data-structures项目中新增一个Module 04-栈，新增package com.citi.stack，新增栈实体类Stack，并且将之前实现过数据结构中的List接口、AbstractList抽象类、ArrayList动态数组拷贝到citi包下面的list包中，将utils包拷贝到citi包下。

public class Stack<T> {

    // 私有属性ArrayList
    private List<T> list = new ArrayList<T>();

 
    public int size(){
        return null;
    }

    public boolean isEmpty(){
        return false;
    }

    public void push(T element){

       
    }

    public T pop(){

        return null
    }

    public T top(){
        return null;
    }

}

**size()**，栈是基于动态数组ArrayList的，栈的size就是动态数组的size

public int size(){
    return list.size();
}

**isEmpty()**，同样如果ArrayList为空，那么栈也为空，栈的数据存储在私有属性ArrayList中

public boolean isEmpty(){
    return list.isEmpty();
}

**push()**，栈的栈顶相当于动态数组的尾部，从栈顶加入元素即动态数组中从数组尾部添加元素，直接调用动态数组的add方法

public void push(T element){
    list.add(element);
}

**pop()**，从栈顶删除元素即动态数组删除末尾元素，调用remove方法

public T pop(){
    return list.remove(list.size() - 1);
}

**top()**，获取栈顶元素即获取动态数组的尾部的元素，调用get方法，索引为size-1

public T top(){
    return list.get(list.size() - 1);
}

clear()，调用动态数组中的clear方法既可以清空栈中的元素

public void clear(){
    list.clear();
}

增加栈的测试类StackTest

public class StackTest {

    Stack stack = null;

    @Before
    public void init(){
        stack = new Stack<>();
        stack.push(11);
        stack.push(10);
        stack.push(20);
        System.out.println("Init Stack " + stack);
    }

    @Test
    public void push() {
        stack.push(30);
        System.out.println("After Push " + stack);
    }

    @Test
    public void pop() {
        stack.pop();
        System.out.println("After Pop " + stack);
    }

    @Test
    public void top() {
        System.out.println("Get Top " + stack.top());
    }
}

在Stack中增加toString()方法，也是调用动态数组的toString()方法

@Override
public String toString() {
    return list.toString();
}

执行所有的测试方法，即可验证Stack

三、栈的应用

由于栈只能从栈顶操作元素的特性，所有凡是包含了前进后退、恢复撤销等功能的实现都是利用了栈的数据特性，例如浏览器的前进后退功能就可以概括为是由两个栈数据结构实现的。

首先在浏览器中依次访问page1、page2、page3，就相当于依次将page1、page2、page3三个页面push到第一个栈中，第一个栈的栈顶元素就是浏览器当前显示的页面，浏览器最后访问的page3，浏览器当前显示的页面也是page3。

此时点击后退按钮，相当于把第一个栈中栈顶元素pop弹出并push到第二个栈中，而第一个栈的栈顶元素就变成了page2，所有浏览器显示的页面为page2；再点击一次后退按钮，又把第一个栈的栈顶元素弹出并push进第二个栈，这是第一个栈的栈顶元素为page1，此时浏览器显示的页面为page1；若点击前进按钮，相当于将第二个栈的栈顶元素page2弹出并push进第一个栈作为栈顶元素，此时浏览器的现实的页面为page2

四、有效的括号

LeetCode第20题：有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s，判断字符串是否有效

class Solution {
public boolean isValid(String s) {
    }
}

利用Stack的数据特性解决：首先遍历字符串，如果遇到左字符(括号的左边部分)就push到栈中，如果遇到右字符就将由字符与栈顶元素比较，如果一致就弹出该元素，直到最后如果栈为空，说明是有效的括号，如果栈不为空，说明不是有效的括号,如果遇到右字符时栈为空，那么也是无效的括号。

首先定义一个栈，用来保存左字符

// 定义一个栈
Stack<Character> stack = new Stack<>();

接着遍历字符串，将遇到的左字符放入栈中，如果遇到右字符串，首先判断栈是否为空，栈为空返回false，接着取出栈顶元素，判断栈顶元素与遍历到的右字符是否为一对，否则返回false

for (int i = 0; i < len; i++) {
    char c = s.charAt(i);
    if (c == '(' || c == '[' || c == '{'){
        // 入栈
        stack.push(c);
    } else { // 有括号
        // 判断栈是否为空
        if (stack.isEmpty()) return false;
        // 弹出栈顶元素
        char left = stack.pop();
        // 判断栈顶元素与遍历到的右字符是否是一对
        if (left == '(' &amp;&amp; c != ')') return false;
        if (left == '[' &amp;&amp; c != ']') return false;
        if (left == '{' &amp;&amp; c != '}') return false;
    }
}

最后判断栈是否为空

return stack.isEmpty();

完整代码

public boolean isValid(String s) {

    // 定义一个栈
    Stack<Character> stack = new Stack<>();
    int len = s.length();

    for (int i = 0; i < len; i++) {
        char c = s.charAt(i);
        if (c == '(' || c == '[' || c == '{'){
            // 入栈
            stack.push(c);
        } else { // 有括号
            // 判断栈是否为空
            if (stack.isEmpty()) return false;
            // 弹出栈顶元素
            char left = stack.pop();
            // 判断栈顶元素与遍历到的右字符是否是一对
            if (left == '(' &amp;&amp; c != ')') return false;
            if (left == '[' &amp;&amp; c != ']') return false;
            if (left == '{' &amp;&amp; c != '}') return false;
        }
    }
    return stack.isEmpty();
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-01-29，如有侵权请联系 cloudcommunity@tencent.com 删除

java