栈和队列

数据结构

栈和队列

栈Stack

栈也是一种线性结构，相比数组，栈对应的操作是数组的子集

只能从一端添加元素，也只能从一端取出元素，这一端称为栈顶

栈是一种后进先出的数据结构，Last In First Out（LIFO），在计算机世界里，栈拥有着不可思议的作用

栈的应用

无处不在的Undo操作（撤销）

程序调用的系统栈

栈的实现

Stack<E>

  • void push(E)
  • E pop()
  • E peek()
  • int getSize()
  • boolean isEmpty()

从用户的角度看，支持这些操作就好，具体底层实现，用户不用关心，实际底层有多种实现方式

image-20200220173223059 
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
/**
 * E表示的是数据类型，Array的数据类型是E，具体是什么，可以在使用的时候声明
 */
public class Array<E> {


    private E[] data;
    private int size;

    //构造函数，传入数组的容量capacity构造Array
    public Array(int capacity){
        data=(E[])new Object[capacity];
        size=0;
    }

    //无参数的构造函数，默认数组的容量capacity=10
    public Array(){
        this(10);
    }

    //获取数组中的元素个数
    public int getSize(){
        return size;
    }

    //获取数组的容量
    public int getCapacity(){
        return data.length;
    }

    //返回数组是否为空
    public boolean isEmpty(){
        return size==0;
    }

    //向所有元素后添加一个新元素
    public void addLast(E e){
        /*if (size==data.length) {
            throw  new IllegalArgumentException("AddLast failed.Array is full.");
        }
        data[size]=e;
        size++;*/
        add(size,e);
    }

    //向所有元素前添加元素
    public void addFirst(E e){
        add(0,e);
    }

    //在index个位置插入一个新元素e
    public void add(int index,E e){
        if (size==data.length) {
            resize(2*data.length);
        }

        if (index<0||index>size) {
            throw new IllegalArgumentException("Add failed.Require index >= 0 and index <= size.");
        }

        for (int i=size-1;i>=index;i--){
            data[i+1]=data[i];
        }
        data[index]=e;
        size++;
    }

    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for(int i=0;i<size;i++){
            newData[i]=data[i];
        }
        //将newData的引用交给data
        data=newData;
    }


    @Override
    public String toString(){
        StringBuffer res = new StringBuffer();
        res.append(String.format("Array:size=%d,capacity=%d\n",size,data.length));
        res.append("[");
        for (int i=0;i<size;i++){
            res.append(data[i]);
            if (i!=size-1) {
                res.append(", ");
            }
        }
        res.append("]");
        return res.toString();
    }

    //获取index索引位置的元素
    public E get(int index){
        if (index<0||index>=size) {
            throw new IllegalArgumentException("Get failed.Index is illegal");
        }
        return data[index];
    }

    //修改index索引位置的元素e
    public void set(int index,E e){
        if (index<0||index>=size) {
            throw new IllegalArgumentException("Get failed.Index is illegal");
        }
        data[index]=e;
    }

    //查询数组中是否有元素e
    public boolean contains(E e){
        for (int i=0;i<size;i++){
            if (data[i].equals(e)){
                return true;
            }
        }
        return false;
    }

    //查找数组中元素e所在的索引，如果不存在元素e，则返回-1
    public int find(E e){
        for (int i=0;i<size;i++){
            if (data[i].equals(e)){
                return i;
            }
        }
        return -1;
    }

    //从数组中删除index位置的元素，返回删除的元素
    public E remove(int index){
        if (index<0||index>size) {
            throw new IllegalArgumentException("Remove failed.Index is illegal");
        }

        E ret=data[index];
        for(int i=index+1;i<size;i++){
            data[i-1]=data[i];
        }
        size--;
        //这句话不是必须的
        data[size]=null;
        if (size==data.length/4&&data.length/2!=0) {
            resize(data.length/2);
        }
        return ret;
    }

    //从数组中删除第一个元素，返回删除的元素
    public E removeFirst(){
        return remove(0);
    }
    //从数组中删除最后一个元素，返回删除的元素
    public E removeLast(){
        return remove(size-1);
    }

    //从数组中删除元素e，只删除一个
    public void removeElement(E e){
        int index=find(e);
        if (index!=-1) {
            remove(index);
        }
    }

    public E getLast(){
        return get(size-1);
        //不这样写的原因是若size=0，则不合法，使用get方法能利用get方法中的条件判断
        //return data[size-1];
    }

    public E getFirst(){
        return get(0);
    }
}
1
2
3
4
5
6
7
8
9
10
11
public interface Stack<E> {
    int getSize();

    boolean isEmpty();

    void push(E e);

    E pop();

    E peek();
}
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
public class ArrayStack<E> implements Stack<E> {

    Array<E> array;

    public ArrayStack(int capacity){
        array=new Array<>(capacity);
    }

    public ArrayStack(){
        array=new Array<>();
    }
    @Override
    public int getSize() {
        return array.getSize();
    }

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

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

    @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 String toString() {
        StringBuffer res = new StringBuffer();
        res.append("Stack:");
        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();
    }
}
1
2
3
4
5
6
7
8
9
10
11
public class Main {
    public static void main(String[] args) {
        ArrayStack<Object> stack = new ArrayStack<>();
        for (int i=0;i<5;i++){
            stack.push(i);
            System.out.println(stack);
        }
        stack.pop();
        System.out.println(stack);
    }
}
1
2
3
4
5
6
Stack:[0] top
Stack:[0,1] top
Stack:[0,1,2] top
Stack:[0,1,2,3] top
Stack:[0,1,2,3,4] top
Stack:[0,1,2,3] top

栈的时间复杂度

image-20200220191109268

括号匹配

编译器中使用

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
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

栈顶元素反映了在嵌套的层次关系中，最近的需要匹配的元素

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
import java.util.Stack;
class Solution {
    public boolean isValid(String s) {
            Stack<Character> stack=new Stack<>();
            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;
                    }
                    char topChar=stack.pop();
                    if (c==')'&&topChar!='(') {
                        return false;
                    }
                    if (c==']'&&topChar!='[') {
                        return false;
                    }
                    if (c=='}'&&topChar!='{') {
                        return false;
                    }
                }
            }
            return stack.isEmpty();
    }
}

队列Queue

队列也是一种线性结构

相比数组，队列对应的操作是数组的子集

只能从一端（队尾）添加元素，只能从另一端（队首）取出元素

队列是一种先进先出的数据结构（先到先得）First In First Out（FIFO）

image-20200220205003619

队列的实现

1
2
3
4
5
6
7
8
9
10
11
12
public interface Queue<E> {

    int getSize();

    boolean isEmpty();

    void enqueue(E e);

    E dequeue();

    E geFront();
}
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
public class ArrayQueue<E> implements Queue<E> {

    private Array<E> array;

    public ArrayQueue(int capacity){
        array=new Array<>(capacity);
    }

    public ArrayQueue(){
        array=new Array<>();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

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

    @Override
    public void enqueue(E e) {
        array.addLast(e);
    }

    @Override
    public E dequeue() {
        return array.removeFirst();
    }

    @Override
    public E getFront() {
        return array.getFirst();
    }

    @Override
    public String toString() {
        StringBuffer res = new StringBuffer();
        res.append("Queue:");
        res.append("front [");
        for (int i=0;i<array.getSize();i++){
            res.append(array.get(i));
            if (i!=array.getSize()-1) {
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();
    }

    public static void main(String[] args){
        ArrayQueue<Integer> queue = new ArrayQueue<>();
        for (int i=0;i<10;i++){
            queue.enqueue(i);
            System.out.println(queue);
            if (i%3==2) {
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }

}

输出结果

1
2
3
4
5
6
7
8
9
10
11
12
13
Queue:front [0] tail
Queue:front [0, 1] tail
Queue:front [0, 1, 2] tail
Queue:front [1, 2] tail
Queue:front [1, 2, 3] tail
Queue:front [1, 2, 3, 4] tail
Queue:front [1, 2, 3, 4, 5] tail
Queue:front [2, 3, 4, 5] tail
Queue:front [2, 3, 4, 5, 6] tail
Queue:front [2, 3, 4, 5, 6, 7] tail
Queue:front [2, 3, 4, 5, 6, 7, 8] tail
Queue:front [3, 4, 5, 6, 7, 8] tail
Queue:front [3, 4, 5, 6, 7, 8, 9] tail

队列的时间复杂度

image-20200220212936334

循环队列

1
2
3
4
5
6
7
8
9
10
11
12
public interface Queue<E> {

    int getSize();

    boolean isEmpty();

    void enqueue(E e);

    E dequeue();

    E getFront();
}
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
public class LoopQueue<E> implements Queue<E> {

    private E[] data;

    private int front,tail;

    private int size;

    private LoopQueue(int capacity){
        data=(E[])new Object[capacity+1];
        front=0;
        tail=0;
        size=0;
    }

    public LoopQueue(){
        this(10);
    }

    public int getCapacity(){
        return data.length-1;
    }
    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return front==tail;
    }

    @Override
    public void enqueue(E e) {
        if ((tail + 1) % data.length == front) {
            resize(getCapacity() * 2);
        }

        data[tail] = e;
        tail = (tail + 1) % data.length;
        size++;
    }

    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity + 1];
        for (int i = 0; i < size; i++) {
            newData[i] = data[(i + front) % data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public E dequeue() {

        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue");
        }
        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size--;
        if (size==getCapacity()/4&&getCapacity()/2!=0) {
            resize(getCapacity()/2);
        }
        return ret;

    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue");
        }
        return data[front];
    }

    @Override
    public String toString() {
        StringBuffer res = new StringBuffer();
        res.append(String.format("Queue:size=%d,capacity=%d\n",size,getCapacity()));
        res.append("front [");
        for (int i=front;i!=tail;i=(i+1)%data.length){
            res.append(data[i]);
            if ((i+1)%data.length!=tail) {
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();
    }

    public static void main(String[] args){
        LoopQueue<Integer> queue = new LoopQueue<>();
        for (int i=0;i<10;i++){
            queue.enqueue(i);
            System.out.println(queue);
            if (i%3==2) {
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

输出结果

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
Queue:size=1,capacity=10
front [0] tail
Queue:size=2,capacity=10
front [0, 1] tail
Queue:size=3,capacity=10
front [0, 1, 2] tail
Queue:size=2,capacity=5
front [1, 2] tail
Queue:size=3,capacity=5
front [1, 2, 3] tail
Queue:size=4,capacity=5
front [1, 2, 3, 4] tail
Queue:size=5,capacity=5
front [1, 2, 3, 4, 5] tail
Queue:size=4,capacity=5
front [2, 3, 4, 5] tail
Queue:size=5,capacity=5
front [2, 3, 4, 5, 6] tail
Queue:size=6,capacity=10
front [2, 3, 4, 5, 6, 7] tail
Queue:size=7,capacity=10
front [2, 3, 4, 5, 6, 7, 8] tail
Queue:size=6,capacity=10
front [3, 4, 5, 6, 7, 8] tail
Queue:size=7,capacity=10
front [3, 4, 5, 6, 7, 8, 9] tail

此时循环队列出队的复杂度为O(1)

循环队列复杂度

image-20200221103416262

数组队列与循环队列的比较

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
public class Main {

    //测试使用q运行opCount个enqueue和dequeue操作所需要的时间，单位：秒
    private static double testQueue(Queue<Integer> q, int opCount) {

        long startTime = System.nanoTime();

        Random random = new Random();
        for (int i = 0; i < opCount; i++) {
            q.enqueue(random.nextInt(Integer.MAX_VALUE));
        }
        for (int i = 0; i < opCount; i++) {
            q.dequeue();
        }
        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;

    }

    public static void main(String[] args) {
        //操作数，入队十万个元素，出队十万个元素
        int opCount = 100000;
        ArrayQueue<Integer> arrayQueue=new ArrayQueue<>();
        double time1 = testQueue(arrayQueue, opCount);
        System.out.println("ArrayQueue,time"+time1+"s");

        LoopQueue<Integer> loopQueue=new LoopQueue<>();
        double time2 = testQueue(loopQueue, opCount);
        System.out.println("LoopQueue,time"+time2+"s");
    }
}

输出结果

1
2
ArrayQueue,time 5.258987444s
LoopQueue,time 0.019219109s

本文标题:栈和队列

文章作者:爱吃鱼的呆先生

发布时间:2020-03-15, 09:50:22

最后更新:2020-02-21, 11:14:54

原始链接:http://yoursite.com/2020/03/15/数据结构/2栈和队列/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 栈和队列
    1. 1.1. 栈Stack
      1. 1.1.1. 栈的应用
      2. 1.1.2. 栈的实现
      3. 1.1.3. 栈的时间复杂度
      4. 1.1.4. 括号匹配
    2. 1.2. 队列Queue
      1. 1.2.1. 队列的实现
      2. 1.2.2. 队列的时间复杂度
      3. 1.2.3. 循环队列
      4. 1.2.4. 循环队列复杂度
      5. 1.2.5. 数组队列与循环队列的比较
|