栈与队列：概念、实现与典型应用

1
package myStack;
2
import exception.EmptyStackException;
3
import java.util.Arrays;
4

5
public class MyStack {
6
    public int[] elem;
7
    public int usedSize;
8

9
    public MyStack() {
10
        this.elem = new int[10];
11
    }
12

13
    public void push(int val){
14
        if(isFull()){
15
            this.elem = Arrays.copyOf(elem,2*elem.length);
16
        }
17
        elem[usedSize++] = val;
18
    }
19

20
    public boolean isFull(){
21
        return usedSize == elem.length;
22
    }
23

24
    public int pop(){
25
        if(isEmpty()){
26
            throw new EmptyStackException("栈中元素为空");
27
        }
28
        int val = elem[usedSize - 1];   //取得栈中的最后值
29
        usedSize--;    //取消对最后值的索引
30
        return val;
31
    }
32

33
    public int peek(){
34
        if(isEmpty()){
35
            throw new EmptyStackException("栈中元素为空");
36
        }
37
        return elem[usedSize - 1];
38
    }
39

40
    public boolean isEmpty(){
41
        return usedSize == 0;
42
    }
43

44
    public int search(int val){
45
        for (int i = usedSize - 1;i >= 0;i--) {
46
            if(elem[i] == val){
47
                // 返回距离栈顶的距离。栈顶本身返回 1，其下方返回 2，以此类推
48
                return usedSize - i;
49
            }
50
        }
51
        return -1;
52
    }
53
}

1
public class MyQueue {
2

3
    static class ListNode {
4
        public int val;
5
        public ListNode prev;
6
        public ListNode next;
7

8
        public ListNode(int val) {
9
            this.val = val;
10
        }
11
    }
12
    public ListNode first = null;
13
    public ListNode last = null;
14
    public int usedSize = 0;
15

16
    // 入队列（尾入）
17
    public void offer(int val) {
18
        ListNode node = new ListNode(val);
19
        if(isEmpty()) {
20
            first = last = node;
21
        } else {
22
            last.next = node;
23
            node.prev = last;
24
            last = last.next;
25
        }
26
        usedSize++;
27
    }
28

29
    // 出队列（头出）
30
    public int poll() {
31
        if(isEmpty()) {
32
            return -1;
33
        }
34
        int val = first.val;
35
        first = first.next;
36
        if(first != null) {
37
            // 将first的前驱置空
38
            first.prev = null;
39
        }
40
        usedSize--;
41
        return val;
42
    }
43

44
    // 获取队头元素
45
    public int peek() {
46
        if(isEmpty()) {
47
            return -1;
48
        }
49
        return first.val;
50
    }
51

52
    public boolean isEmpty() {
53
        return usedSize == 0;
54
    }

1
// 使用不浪费空间方法
2
class MyCircularQueue{
3
    public int front;
4
    public int rear;
5
    public int[] elem;
6
    private boolean isFullFlg;
7
    public MyCircularQueue(int k) {
8
        elem = new int[k];
9
        front = 0;
10
        rear = 0;
11
        isFullFlg = false;
12
    }
13
    // 入队
14
    public boolean enQueue(int value) {
15
        if(isFull()) {
16
            return false;
17
        }
18
        elem[rear] = value;
19
        rear = (rear + 1) % elem.length;    // rear往后移一位
20
        if(rear == front) {
21
            isFullFlg = true;
22
        }
23
        return true;
24
    }
25
    // 出队
26
    public boolean deQueue() {
27
        if(isEmpty()) {
28
            return false;
29
        }
30
        front = (front + 1) % elem.length;  // front往后移一位
31
        isFullFlg = false;  // 只要成功出队，则队列不可能满
32
        return true;
33
    }
34

35
    // 返回front指向的元素
36
    public int Front() {
37
        if(isEmpty()) return -1;
38
        return elem[front];
39
    }
40

41
    // 返回rear指向的元素
42
    public int Rear() {
43
        if(isEmpty()) return -1;
44
        int index = (rear == 0) ? elem.length - 1 : rear - 1;
45
        return elem[index];
46
    }
47

48
    public boolean isEmpty() {
49
        return (rear == front) && !isFullFlg;
50
    }
51

52
    public boolean isFull() {
53
        return isFullFlg;
54
    }
55
}