数据结构--栈和队列详解

1. 栈

1.1 栈的基本概念

栈(Stack):是一种按照先进后出(FILO)、后进先出(LIFO)模式的容器结构。准确的讲，其实并不一定是线性结构，只是一般线性结构实现最简单，所以大多数以线性结构来实现

栈是一个一头开口，一头有底的一个容器

栈顶（Top）：允许进行插入删除的那一端
栈底（Bottom）：最底部，不允许进行插入和删除的另一端
空栈 ：没有任何元素的栈

1.2 栈的基本操作

---

1.3 栈的顺序存储结构(顺序栈)

用连续的一片存储空间来存储数据元素，这样的栈称为顺序栈。类似于顺序表，用一维数组来存放顺序栈中的数据元素。
设置一个指示器 top 始终指向栈顶位置，top随着插入或删除而变化，top 的值必须小于栈的长度 size ，通常当栈为空时，to = -1

1.3.1 push ()

首先判断栈是否已满(前提默认入栈元素不能为 null)，若不满进行入栈操作，若栈满证明 top == size - 1 ，则抛出异常

//入栈
public void push(T val) {
        if (!isFull()) {
            top++;
            arr[top] = val;
            return;
        }
        throw new ArrayIndexOutOfBoundsException("栈已满！ top：" + top + "  size：" + size);
    }
1
2
3
4
5
6
7
8
9

1.3.2 pop ()

首先判断栈是否为空，若栈空则返回 null，若栈不为空就返回 top 位置的元素，并置空该位置，top–

//出栈
public T pop() {
        if (isEmpty()) {
            return null;
        }

        T result = (T) arr[top];
        arr[top] = null;
        top--;
        return result;
    }
1
2
3
4
5
6
7
8
9
10
11

1.3.3 peek ()

首先判断栈是否为空，若为空就返回 null，否则返回 top 位置的元素

//查看栈顶元素
 public T peek() {
        if (isEmpty()) {
            return null;
        }

        T result = (T) arr[top];
        return result;
    }
1
2
3
4
5
6
7
8
9

1.3.4 isEmpty ()、isFull ()、size ()

判断栈空条件：top == -1
判断栈满条件：top == size - 1
获取栈的长度：top + 1

 //判断栈是否为空
 public boolean isEmpty() {
      return top == -1;
  }
  //判断栈是否满溢
  public boolean isFull() {
      return top == size - 1;
  }
  //获取栈的长度 
  public int size() {
      return top + 1;
  }
1
2
3
4
5
6
7
8
9
10
11
12

完整代码

public class myStack<T> {
    //栈的长度
    public int size;
    //栈数组	
    public Object[] arr;	
    //栈顶指示器
    public int top;		

    //默认构造方法
    public myStack() {
        size = 10;
        arr = new Object[size];
        top = -1;
    }

	//出栈
    public T pop() {
        if (isEmpty()) {
            return null;
        }

        T result = (T) arr[top];
        arr[top] = null;
        top--;
        return result;
    }

	//入栈
    public void push(T val) {
        if (!isFull()) {
            top++;
            arr[top] = val;
            return;
        }
        throw new ArrayIndexOutOfBoundsException("栈已满！ top：" + top + "  size：" + size);
    }

	//查看栈顶元素
    public T peek() {
        if (isEmpty()) {
            return null;
        }

        T result = (T) arr[top];
        return result;
    }

	//获取栈的长度
    public int size() {
        return top + 1;
    }

	//判断栈满
    public boolean isFull() {
        return top == size - 1;
    }

	//判断栈空
    public boolean isEmpty() {
        return top == -1;
    }
}
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

1.4 栈的链式结构(链栈)

使用链式存储结构存储的栈称为链栈，链栈通常用单链表来表示，它的结点结构与单链表的结构一样，都是由 val 和 next 两部分组成。我们将栈顶设在链表的头部，即将栈顶指示器指向链表的头部，所有对栈的数据元素的增加和删除操作都在链表头部进行

完整代码

public class LinkedStack<T> {
    //定义内部类，用来存放结点数据
    class Node {
        public T val;
        public Node next;

        public Node() {

        }

        public Node(T val, Node next) {
            this.val = val;
            this.next = next;
        }
    }

	//栈顶指示器
    public Node top;
    //栈的长度
    public int size;
	
	//默认构造方法
    public LinkedStack() {
        top = null;
        size = 0;
    }

	//出栈
    public T pop() {
        if (isEmpty()) {
            return null;
        }

        T node = top.val;
        top = top.next;
        size--;
        return node;
    }

	//入栈
    public void push(T node) {
        Node newNode = new Node(node, null);
        if (!isEmpty()) {
            newNode.next = top;
        }
        top = newNode;
        size++;
    }

	//查看栈顶元素
    public T peek() {
        if (isEmpty()) {
            return null;
        }
        return top.val;
    }

	//获取栈的长度
    public int size() {
        return size;
    }

	//判断栈空
    public boolean isEmpty() {
        return top == null && size == 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

2.队列

2.1队列的基本概念

队列： 队列是一种线性表，是一种先进先出(FIFO)的线性结构。队列只允许在表的一端进行插入、删除操作。允许插入的一端称为队尾，允许删除的一端称为队头

队头（Front）：允许删除的一端，又叫队首
队尾（Rear）：允许插入的一端
空队列：没有任何元素的空队列

2.2 队列的基本操作

---

2.3 队列的顺序结构(顺序队列)

2.3.1 offer ()

//插入元素
    public void offer(int value) {
        if (isFull()) {
            System.out.println("满队列，不能添加元素" + value);
        } else {
            arr[rear++] = value;
        }
    }
1
2
3
4
5
6
7
8

2.3.2 poll ()

//取出元素
    public T poll() {
        if (isEmpty()) {
            throw new RuntimeException("该队列为空，不能取出");
        } else {
            return (T) arr[front++];
        }
    }
1
2
3
4
5
6
7
8

2.3.3 peek ()

//查看队首元素
    public T peek() {
        if (isEmpty()) {
            throw new RuntimeException("该队列为空");
        } else {
            return (T) arr[front];
        }
    }
1
2
3
4
5
6
7
8

2.3.4 isEmpty ()、isFull ()、size ()

//判断队列是否空
    public boolean isEmpty() {
        return front == rear;
    }

    //判断队列是否满
    public boolean isFull() {
        return rear == size;
    }

    //返回队列长度
    public int size(){
        return rear - front;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

完整代码

public class ArrayQueue<T> {
    public int size;	//队列长度
    public int front;	//队首指示器
    public int rear;	//队尾指示器
    public Object[] arr;	//队列数组

    public ArrayQueue() {	//默认构造方法
        size = 10;
        front = 0;
        rear = 0;
        arr = new Object[size];
    }

    //插入元素
    public void offer(int value) {
        if (isFull()) {
            System.out.println("满队列，不能添加元素" + value);
        } else {
            arr[rear++] = value;
        }
    }

    //取出元素
    public T poll() {
        if (isEmpty()) {
            throw new RuntimeException("该队列为空，不能取出");
        } else {
            return (T) arr[front++];
        }
    }

    //查看队首元素
    public T peek() {
        if (isEmpty()) {
            throw new RuntimeException("该队列为空");
        } else {
            return (T) arr[front];
        }
    }

    //判断队列是否空
    public boolean isEmpty() {
        return front == rear;
    }

    //判断队列是否满
    public boolean isFull() {
        return rear == size;
    }

    //返回队列长度
    public int size(){
        return rear - front;
    }
}
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

2.4 队列的链式结构(链式队列)

队列的链式存储结构其实和栈都是相似的，都在其内部定义一个内部类 Node，用于存储每个元素的结点属性，它也必循有 next ，用于指向下一个元素结点，并且它有队头和队尾指示器front 和 rear
它的入队是从队尾插入，而出队是从对头删除

空队列时，front 和 real 都指向头结点

完整代码

public class LinkedQueue<T> {
    class Node {	//内部类 Node，存放节点信息
        public T val;
        public Node next;

        public Node() {

        }

        public Node(T val) {
            this.val = val;
        }

        public Node(T val, Node next) {
            this.val = val;
            this.next = next;
        }
    }

    public Node front;	//队首指示器
    public Node rear;	//队尾指示器
    public int size;	//队列长度

    public LinkedQueue() {	//默认构造方法
        front = null;
        rear = null;
    }

	//入队操作
    public void offer(T item) {
        Node newNode = new Node(item);
        if (isEmpty()) {
            front = newNode;
        } else {
            rear.next = newNode;
        }
        rear = newNode;
        size++;
    }

	//出队操作
    public T poll() {
        if (isEmpty()) {
            return null;
        }

        Node node = front;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        size--;
        return node.val;
    }

	//查看队首元素
    public T peek() {
        if (!isEmpty()) {
            return front.val;
        } else
            return null;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        if ((front == rear) && (size == 0)) {
            return true;
        } else {
            return false;
        }
    }

	//获取队列长度
    public int size() {
        return size;
    }

}
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