数据结构与算法(四)什么是栈

Posted on | In

输入图片说明

前言

今天是大年初三，在广州过的第四个还是第五个年了，已经忘了，中午吃完饭看书大话数据结构的这本书的栈与队列的关于栈的这篇文章。就去电影看黄渤演的疯狂的外星的人这部喜剧片。笑点还是挺多的。整部电影以外星文明想和人类建交而为起点。外星人在太空中意外坠楼到黄渤的训猴的马戏团。导致黄渤相依为命的猴子受伤无法继续表演。而外星人坠落时晕过去了。黄渤拿走了外星人超能力的能量环。黄渤误以为他稀有的猴子品种，把他当猴子训练发生的一系列啼笑皆非的故事。

栈与队列的概述

  • 栈是限定仅在表尾进行插入和删除操作的线性表 。
  • 队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表

栈的定义

  • 我们把允许插入和删除的一端称为栈顶(top) ,另一端称为核底 (bottom),不含任何数据元素的称为空钱。栈又称为后进先出 (LastIn FilrstOut) 的线性表,简 称 LlFO 结构 。
  • 首先它是一个统性表 ,也就是说,栈元素具有线性关系,即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作,这里表尾是指栈顶 ,而不是栈底 。

栈的顺序存储结构

  • 栈的顺序存储其实也是线性表顺序存储 的简化,我 们简称为顺序栈。下标为 0 的一端作为栈底比较好,因为首元素都存在栈底,变化最小,所以让它作栈底 。

顺序栈代码实现

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

public interface Stack<E> {

    //返回栈的长度
     int length();
     //出栈
     E pop();

    //进栈
     void push(E element);

    //访问栈顶元素
     E peek();

    //判断栈是否为空
     boolean empty();

     //清空栈
     void clear();

     String toString();
}

/**
 * 栈的顺序存储结构
 * 栈是先进后出的线性表
 * @author qinxuewu
 * @create 19/2/7下午1:23
 * @since 1.0.0
 *
 */
public class SequenceStack<E> implements  Stack<E> {
    //定义栈长度  给个默认值
    private int capacity = 16;
    //保存顺序栈中元素的个数
    private int size;
    //定义一个数组用于保存顺序栈中的元素
    private Object[] elementData;

    public SequenceStack(){
        this.elementData = new Object[capacity];
        this.size=0;
    }
    //以指定的大小来创建栈
    public SequenceStack(int initSize){
        this.capacity=initSize;
        this.elementData = new Object[capacity];
        this.size=0;
    }

    @Override
    public int length() {
        return size;
    }

    /**
     * 出栈思路：
     * 1.判断当前炸是否为空
     * 2. 栈不为空。先进后出原则。直接去栈顶的元素出栈szie-1的元素
     * 3. 返回出栈的元素，
     *
     * @return
     */
    @Override
    public E pop() {
        if(empty()){
            throw new IndexOutOfBoundsException("栈已空不能出栈");
        }
        E oldValue = (E)elementData[size - 1];
        //让垃圾回收器及时回收，避免内存泄露
        elementData[--size] = null;
        return oldValue;
    }

    /**
     * 进栈:
     * 1. 判断当前默认的栈长度是否已用完
     * 2. 如果栈空间已用完每次增加16位的长度
     * 3. 在新的栈空间的末尾元素增加新元素
     *
     * @param element
     */
    @Override
    public void push(E element) {
        //炸已满  每次增加16的长度
        if((size+1)>capacity){
            capacity=capacity+16;
            elementData = Arrays.copyOf(elementData, capacity);
        }
        elementData[size++]=element;
    }

    /**
     * 访问访问栈顶元素：
     * 先进后出。访问栈顶元素
     * @return
     */
    @Override
    public E peek() {
        if(empty()){
            return null;
        }
        E value = (E)elementData[size - 1];
        return value;
    }

    @Override
    public boolean empty() {
        return size==0;
    }

    @Override
    public void clear() {
        for (int i = 0; i <size ; i++) {
            elementData[i] = null;
        }
        this.size=0;
    }

    @Override
    public String toString() {
        StringBuilder str=new StringBuilder();
        str.append("[");
        for (int i = 0; i <size ; i++) {
            str.append(elementData[i]+",");
        }
        str.append("]");
        return str.toString();
    }

    public static void main(String[] args) {
        SequenceStack<Integer> stack=new SequenceStack<>();
        for (int i = 0; i <50 ; i++) {
            stack.push(i);
        }
        System.out.println(stack.toString());
        System.out.println(stack.size);
        System.out.println(stack.pop());
        System.out.println(stack.toString());
    }
}

栈的链式存储结构

  • 栈的链式存储结构简称为链栈。通常栈顶是放在单链表的头部，对于链栈来说，是不需要头结点的。
  • 对于链栈来说,基本不存在栈满的情况,除非内存已经没有可以使用的空间
  • 对于空栈来说,链表原定义是头指针指向空 , 那么链栈的空其实就是top=null的时候。

链栈

进栈思路

  • 让栈顶top指向新创建的元素，并且新元素的next指针指向原来的栈顶元素

    出栈思路

  • 出栈就是把当前栈顶替换为栈顶的next指向的结点。然后释放原栈顶的next引用

链栈代码实现

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
87

public class LinkStack<T> {

    private class Node {
        private T data;
        // 指向下个节点的指针
        private Node next;
        // 无参构造器
        public Node() {
        }
        public Node(T data, Node next) {
            this.data = data;
            this.next = next;

        }
    }

    //链栈的栈顶元素
    private Node top;
    // 结点数量
    private int size;

    public  LinkStack(){
        //空链栈，top的值为null
        top = null;
    }

    // 以指定数据元素来创建链栈，该链栈只有一个元素
    public LinkStack(T element) {
        top = new Node(element, null);
        size++;
    }
    public int length() {
        return size;
    }

    /**
     * 进栈思路：
     * 让栈顶top指向新创建的元素，并且新元素的next指针指向原来的栈顶元素
     * @param element
     */
    public void push(T element) {
        top = new Node(element, top);
        size++;

    }

    /**
     * 出栈思路：
     * 出栈就是把当前栈顶替换为栈顶的next指向的结点。然后释放原栈顶的next引用
     * @return
     */
    public T pop() {
        Node oldTop = top;
        // 让top引用指向原栈顶元素的下一个元素
        top = top.next;
        // 释放原栈顶元素的next引用
        oldTop.next = null;
        size--;
        return oldTop.data;

    }

    // 访问栈顶元素，但不删除栈顶元素
    public T peek(){
        return top.data;
    }

    // 请空链栈
    public void clear() {
        top = null;
        size = 0;
    }



    public static void main(String[] args) {
        LinkStack<Integer> stack=new LinkStack<Integer>();

        for (int i = 0; i <5 ; i++) {
            stack.push(i);
        }
        System.out.println(stack.pop());
        System.out.println(stack.size);

    }
}

栈的应用(递归)

斐波那契数列实现

说如果兔子在出生两个月后,就有繁殖能力, 一对兔子每个月能生出一对小兔子 来。假设所有兔都不死,那么一年以后可以繁殖多少对兔子呢?

我们拿新出生的一对小兔子分析一下;第一个月小兔子没有繁殖能力,所以还是 一对 i 两个月后,生下一对小兔子数共有两对; 三个月以后,老兔子又生下一对,因 为小兔子还没有繁殖能力 , 所以一共是三对……依次类推可以列出下表(表 4-8-1)。

前面相邻两项之和,构成了后一项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class DiGuiTest {
    public static void main(String[] args) {
        for (int i=1;i<=12;i++){
            System.out.println(test(i));
        }
    }
    /**
     *
     * @param n 月份
     */
    public static int test(int n){
        if(n==1 || n==2){
            /**
             * 两个月后新出生的兔子才有繁殖能力。
             * 所以前两个月都没有兔子出生 都是开始的第一对兔子
             */
            return  1;
        }
        //前面相邻两项之和,构成了后一项
        return  test(n-1)+test(n-2);
    }
}

觉得本文不错的话，分享一下给小伙伴吧~