Java数据结构与算法解析(二)——栈

心已赠人 2022-05-29 06:13 197阅读 0赞

#                                 Java数据结构与算法解析(二)——栈 #

关联文章:   
[Java数据结构与算法解析(一)——表][Java]

栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈顶。对栈的基本操作有push(进栈)和pop(出栈)，对空栈进行push和pop，一般被认为栈ADT的一个错误。当push时空间用尽是一个实现限制，而不是ADT错误。栈有时又叫做LIFO（后进先出）表。

## 基本概念 ##

允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）,不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表   
![这里写图片描述][SouthEast]

栈的顺序存储结构   
栈的数序结构可以使用数组来实现，栈底是:下标为0的一端   
![这里写图片描述][SouthEast 1]

栈的链式存储结构   
![这里写图片描述][SouthEast 2]

栈的实现   
栈的实现，一般分为两种形式，链式结构和数组。两者均简化了ArrayList和LinkedList中的逻辑。

## 栈的数组实现 ##

抽象出栈的必备接口

public interface Stack<T> {
    
        boolean isEmpty();
    
        void push(T data);
    
        T pop();
    
        int size();
    }
      
       
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10

栈的数组实现形式

public class ArrayStack<T> implements Stack<T>, Iterable {
    
        private T[] mArray;
        private int mStackSize;
    
        private static final int DEFAULT_CAPACITY = 10;
    
        public ArrayStack(int capacity) {
            if (capacity < DEFAULT_CAPACITY) {
                ensureCapacity(DEFAULT_CAPACITY);
            } else {
                ensureCapacity(capacity);
            }
        }
    
    
        public boolean isEmpty() {
            return mStackSize == 0;
        }
    
    
        public int size() {
            return mStackSize;
        }
    
        public void push(T t) {
            if (mStackSize == mArray.length) {
                ensureCapacity(mStackSize * 2 + 1);
            }
            mArray[mStackSize++] = t;
        }
    
        public T pop() {
            if (isEmpty()) {
                throw new EmptyStackException();
            }
            T t = mArray[--mStackSize];
            mArray[mStackSize] = null;
            //调整数组的大小，防止不必要的内存开销
            if (mStackSize > 0 && mStackSize < mArray.length / 4) {
                ensureCapacity(mArray.length / 2);
            }
            return t;
        }
    
    
        private void ensureCapacity(int newCapacity) {
            T[] newArray = (T[]) new Object[newCapacity];
            for (int i = 0; i < mArray.length; i++) {
                newArray[i] = mArray[i];
            }
            mArray = newArray;
        }
    
        @Override
        public Iterator iterator() {
            return null;
        }
    
        private class ArrayStackIterator implements Iterator<T> {
    
            @Override
            public boolean hasNext() {
                return mStackSize > 0;
            }
    
            @Override
            public T next() {
                return
                        mArray[--mStackSize];
            }
        }
    }
    
    
      
       
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        38
        39
        40
        41
        42
        43
        44
        45
        46
        47
        48
        49
        50
        51
        52
        53
        54
        55
        56
        57
        58
        59
        60
        61
        62
        63
        64
        65
        66
        67
        68
        69
        70
        71
        72
        73
        74
        75

对象游离   
Java的垃圾收集策略是回收所有无法被访问对象的内存，如果我们pop()弹出对象后，不调用如下代码，就会造成游离，因为数组中仍然持有这个对象的引用，保存一个不需要的对象的引用，叫做游离。

mArray[mStackSize] = null;
      
       
        1

动态调整数组大小   
pop()中，删除栈顶元素后，如果栈的大小小于数组的1/4，就将数组的大小减半，这样栈永远不会溢出，使用率也不会小于1/4。

## 栈的链表实现 ##

采用链式存储结构的栈，由于我们操作的是栈顶一端，因此这里采用单链表（不带头结点）作为基础，直接实现栈的添加，获取，删除等主要操作即可。

链栈的出入栈操作   
链栈的入栈操作：

![这里写图片描述][SouthEast 3]

![这里写图片描述][SouthEast 4]

链栈的出栈操作：   
![这里写图片描述][SouthEast 5]

![这里写图片描述][SouthEast 6]

“\`   
public class LinkedStack implements Stack, Iterable \{

private int mSize;
    private Node<T> endNote;
    private int modCount;
    
    public LinkedStack() {
        init();
    }
    
    private void init() {
        endNote = new Node<T>(null, null);
        modCount++;
    }
    
    
    @Override
    public boolean isEmpty() {
        return mSize == 0;
    }
    
    @Override
    public void push(T data) {
        Node<T> newNote = new Node<T>(data, null);
        endNote.mNext = newNote;
        mSize++;
        modCount++;
    }
    
    @Override
    public T pop() {
        if (endNote.mNext == null) {
            throw new NoSuchElementException();
        }
        T t = endNote.mNext.mData;
        endNote.mNext = endNote.mNext.mNext;
        mSize--;
        modCount++;
        return t;
    }
    
    @Override
    public int size() {
        return mSize;
    }
    
    @Override
    public Iterator iterator() {
        return new LinkedStackIterator();
    }
    
    private static class Node<T> {
    
        private Node<T> mNext;
        private T mData;
    
    
        public Node(T data, Node<T> next) {
            mData = data;
            mNext = next;
        }
    }
    
    private class LinkedStackIterator implements Iterator<T> {
        private Node<T> currentNode = endNote.mNext;
        private int expectedModCount = modCount;
    
        @Override
        public boolean hasNext() {
            return currentNode != null;
        }
    
        @Override
        public T next() {
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            T t = currentNode.mData;
            currentNode = currentNode.mNext;
            return t;
        }
    
    
    }
    
      
       
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        38
        39
        40
        41
        42
        43
        44
        45
        46
        47
        48
        49
        50
        51
        52
        53
        54
        55
        56
        57
        58
        59
        60
        61
        62
        63
        64
        65
        66
        67
        68
        69
        70
        71
        72
        73
        74
        75
        76
        77
        78
        79
        80
        81
        82
        83
        84
        85
        86

## 时间复杂度对比 ##

顺序栈复杂度

<table style="border-collapse:collapse; width:700px; text-align:center; margin-bottom:24px; color:rgb(69,69,69); font-size:16px"> 
 <thead style=""> 
  <tr style="border-width:1px 0px 0px; border-right-style:initial; border-bottom-style:initial; border-left-style:initial; border-right-color:initial; border-bottom-color:initial; border-left-color:initial; border-top-style:solid; border-top-color:rgb(221,221,221)"> 
   <th style="font-size:14px; color:rgb(79,79,79); line-height:22px; border:1px solid rgb(221,221,221); padding:8px; text-align:left; word-wrap:break-word; word-break:normal; vertical-align:middle; background-color:rgb(239,243,245)"> 操作</th> 
   <th style="font-size:14px; color:rgb(79,79,79); line-height:22px; border:1px solid rgb(221,221,221); padding:8px; text-align:left; word-wrap:break-word; word-break:normal; vertical-align:middle; background-color:rgb(239,243,245)"> 时间复杂度</th> 
  </tr> 
 </thead> 
 <tbody style="border:0px"> 
  <tr style="border-width:1px 0px 0px; border-right-style:initial; border-bottom-style:initial; border-left-style:initial; border-right-color:initial; border-bottom-color:initial; border-left-color:initial; border-top-style:solid; border-top-color:rgb(221,221,221)"> 
   <td style="font-size:14px; color:rgb(79,79,79); line-height:22px; border:1px solid rgb(221,221,221); padding:8px; text-align:left; word-wrap:break-word; word-break:normal; vertical-align:middle"> 空间复杂度(用于N次push)</td> 
   <td style="font-size:14px; color:rgb(79,79,79); line-height:22px; border:1px solid rgb(221,221,221); padding:8px; text-align:left; word-wrap:break-word; word-break:normal; vertical-align:middle"> O(n)</td> 
  </tr> 
  <tr style="border-width:1px 0px 0px; border-right-style:initial; border-bottom-style:initial; border-left-style:initial; border-right-color:initial; border-bottom-color:initial; border-left-color:initial; border-top-style:solid; border-top-color:rgb(221,221,221); background-color:rgb(247,247,247)"> 
   <td style="font-size:14px; color:rgb(79,79,79); line-height:22px; border:1px solid rgb(221,221,221); padding:8px; text-align:left; word-wrap:break-word; word-break:normal; vertical-align:middle"> push()</td> 
   <td style="font-size:14px; color:rgb(79,79,79); line-height:22px; border:1px solid rgb(221,221,221); padding:8px; text-align:left; word-wrap:break-word; word-break:normal; vertical-align:middle"> O(1)</td> 
  </tr> 
  <tr style="border-width:1px 0px 0px; border-right-style:initial; border-bottom-style:initial; border-left-style:initial; border-right-color:initial; border-bottom-color:initial; border-left-color:initial; border-top-style:solid; border-top-color:rgb(221,221,221)"> 
   <td style="font-size:14px; color:rgb(79,79,79); line-height:22px; border:1px solid rgb(221,221,221); padding:8px; text-align:left; word-wrap:break-word; word-break:normal; vertical-align:middle"> pop()</td> 
   <td style="font-size:14px; color:rgb(79,79,79); line-height:22px; border:1px solid rgb(221,221,221); padding:8px; text-align:left; word-wrap:break-word; word-break:normal; vertical-align:middle"> O(1)</td> 
  </tr> 
  <tr style="border-width:1px 0px 0px; border-right-style:initial; border-bottom-style:initial; border-left-style:initial; border-right-color:initial; border-bottom-color:initial; border-left-color:initial; border-top-style:solid; border-top-color:rgb(221,221,221); background-color:rgb(247,247,247)"> 
   <td style="font-size:14px; color:rgb(79,79,79); line-height:22px; border:1px solid rgb(221,221,221); padding:8px; text-align:left; word-wrap:break-word; word-break:normal; vertical-align:middle"> isEmpty()</td> 
   <td style="font-size:14px; color:rgb(79,79,79); line-height:22px; border:1px solid rgb(221,221,221); padding:8px; text-align:left; word-wrap:break-word; word-break:normal; vertical-align:middle"> O(1)</td> 
  </tr> 
 </tbody> 
</table>

链式栈复杂度

可知栈的主要操作都可以在常数时间内完成，这主要是因为栈只对一端进行操作，而且操作的只是栈顶元素。

## 栈的经典实用 ##

逆波兰表达式法   
标准四则运算表达式—中缀表达式   
![这里写图片描述][SouthEast 7]

我们在小学学习的四则运算表达式就是中缀表达式 ，但是计算机是不认识中缀表达式的，它采用的是后缀表达式

计算机采用—后缀表达式   
![这里写图片描述][SouthEast 8]

计算规则：

![这里写图片描述][SouthEast 9]

它的规则是，从头开始遍历，遇到数字进行压栈，遇到运算符号，将栈顶开始的两个元素进行运算符操作后，弹栈，结果进栈，931遇到“—”时，进行3-1=2，将2进栈，然后3进栈，遇到“\*”，3\*2=6进栈，遇到“+”，进行9+6=15进栈，然后10和2进栈，遇到“/”，进行10/2后结果进栈，最后是15+5=20，就完成了后缀表达式的计算操作。

中缀表达式转后缀表达式   
![这里写图片描述][SouthEast 10]  
数字输出，运算符进栈，括号匹配出栈，是当栈顶是运算符时，又压进来一个运算符，如果压进来的运算符优先级比栈顶的高，则这个压进来的运算符出栈。

![这里写图片描述][SouthEast 11]

![这里写图片描述][SouthEast 12]

![这里写图片描述][SouthEast 13]

![这里写图片描述][SouthEast 14]

![这里写图片描述][SouthEast 15]

如果我们见到任何其他的符号（+，\*,()，那么我们从栈中弹出栈元素直到发现优先级更低的元素为止。有一个例外：除非是在处理一个）的时候，否则我们决不从栈中移走（。对于这种操作，+的优先级最低，而（的优先级最高。当从栈弹出元素的工作完成后，我们再将操作符压入栈中。

[Java]: http://blog.csdn.net/u012124438/article/details/77618861
[SouthEast]: /images/20220529/4525154ba02c4d248ef1425f4b17d797.png
[SouthEast 1]: /images/20220529/fb77755ee6e94ba281ba3c1287daa97e.png
[SouthEast 2]: /images/20220529/582c2935fcf94ca1bfe635e28907f6e8.png
[SouthEast 3]: /images/20220529/06c7ac68789d4b56a2579fce7e153dab.png
[SouthEast 4]: /images/20220529/5bc0759689b9449ea9247dfcdd08c945.png
[SouthEast 5]: /images/20220529/7f3745b34f164d52a41cfa5ecde23075.png
[SouthEast 6]: /images/20220529/0c77a306ac144ad0a6b04f443a00474b.png
[SouthEast 7]: /images/20220529/90def03eaafa4617ab9b275909f6329b.png
[SouthEast 8]: /images/20220529/c5e500c1d0dc412e8e6a6d4a160ce7c4.png
[SouthEast 9]: /images/20220529/8aed2716564f4492a5060028f11e01a0.png
[SouthEast 10]: /images/20220529/094a9bc313b74329af4d57bf69276b20.png
[SouthEast 11]: /images/20220529/2a573db3ac9b4b2da252937b8b073274.png
[SouthEast 12]: /images/20220529/02bad707de0f4604bca7839d8225e0b2.png
[SouthEast 13]: /images/20220529/cf40ee12054d40c880e5091e4407268b.png
[SouthEast 14]: /images/20220529/23a101dd94674d2692e1a891609716a1.png
[SouthEast 15]: /images/20220529/42fafd193c5348f087f11e563f9b3110.png