[数据结构]之栈

1. 概述

• • 栈对应的操作是数组的子集
  • 只能从一端添加元素，也只能从一端获取元素；这一端称之为栈顶
  • 栈是一种后进先出的数据结构（LIFO：Last In First Out）

2. 栈的应用

• • 撤销操作
  • 程序调用的系统栈

3. 栈的实现

　　定义栈的接口，根据栈的数据结构特性，它有以下基本的方法：

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

栈接口定义代码：

package com.ytuan.stack;

public interface Stack<E> {

    public void push(E e);

    public E pop();

    public E peek();

    public int getSize();

    public boolean isEmpty();

}

 

　　对于栈的实现，在底层有很多的实现方式，在这里我么使用的是数组的实现方式，也会重用之前实现的动态数组。参考链接：https://www.cnblogs.com/ytuan996/p/10692548.html

栈的实现代码：

package com.ytuan.stack;

import com.ytuan.array.Array;

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

    private Array<E> array;

    public ArrayStack(int capacity) {

        array = new Array<>(capacity);
    }

    public ArrayStack() {
        this(10);
    }

    @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 int getSize() {
        return array.getSize();
    }

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

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

    @Override
    public String toString() {

        StringBuffer res = new StringBuffer();

        res.append(String.format("Stack:  size = %d, capacity= %d. \n", array.getSize(),array.getCapacity()));

        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();
    }

}

View Code

 

4. 栈的实际应用

括号匹配：leetcode的20问题：https://leetcode-cn.com/problems/valid-parentheses/

import java.util.Stack;

class Solution {
    public boolean isValid(String s) {

        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {

            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{')
                stack.push(c);
            else {

                if (stack.isEmpty())
                    return false;

                Character pop = stack.pop();
                if (c == ')' && pop != '(')
                    return false;
                if (c == ']' && pop != '[')
                    return false;
                if (c == '}' && pop != '{')
                    return false;
            }
        }

        return stack.isEmpty() ? true : false;
    }

} 

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄