栈和队列--DS

1. 栈(Stack)

1.1 栈的定义

**栈是一种特殊的线性表，其只允许在固定的一端(栈顶)进行元素插入和删除元素操作。**进行数据插入和删除操作的一段称为栈顶，另一端则称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)原则。

1.2 栈的核心操作

1. 压栈(push): 对数据元素进行栈的插入操作叫做压栈/入栈，栈的操作都是针对栈的一端(栈顶)进行的。

public void push(int val) {  
    if(isFull()) {  
        this.elem = Arrays.copyOf(this.elem,elem.length*2);  
    }  
    this.elem[useSize++] = val;  
}  
private boolean isFull() {  
    return useSize == elem.length;  
}

在插入数据元素时，要注意判断栈的空间是否需要扩容，当栈空间满时需要对栈空间进行扩容。
2. 出栈(pop):栈的删除操作叫做出栈，栈的删除操作也是在栈顶执行的。

public int pop() {  
    if(isEmpty()) {  
        throw new EmptyException("栈为空，不能pop");  
    }  
    return this.elem[--useSize];  
}
public boolean isEmpty() {  
    return this.useSize == 0;  
}

当栈为空栈，即栈中没有元素时我们不能对栈进行删除操作，否则抛出异常中止运行，所以在进行栈的删除操作时需要先判定栈中元素是否为空。

1.3 栈的模拟实现

顺序表模拟实现栈

//MyStack.java
package stack;  
  
import java.util.Arrays;  
  
public class MyStack {  
    public int[] elem;  
    public int useSize;  
  
    public MyStack() {  
        this.elem = new int[10];  
    }  
    public void push(int val) {  
        if(isFull()) {  
            this.elem = Arrays.copyOf(this.elem,elem.length*2);  
        }  
        this.elem[useSize++] = val;  
    }  
    private boolean isFull() {  
        return useSize == elem.length;  
    }  
    public int pop() {  
        if(isEmpty()) {  
            throw new EmptyException("栈为空，不能pop");  
        }  
        return this.elem[--useSize];  
    }  
    public int peek() {  
        if(isEmpty()) {  
            throw new EmptyException("栈为空，不能peek");  
        }  
        return this.elem[this.useSize - 1];  
    }  
    public boolean isEmpty() {  
        return this.useSize == 0;  
    }  
    public int size() {  
        return this.useSize;  
    }  
  
}

2. 队列(Queue)

2.1 队列的定义

队列是只允许在一端进行插入操作，在另一端进行数据删除操作的特殊线性表。队列中允许进行插入操作的一端称为队尾(Tail/Rear),进行数据删除操作的一端称为队头(Head/Front).

2.2 队列的核心操作

1. 入队列(offer):对于数据的插入操作，我们从队尾入队列。

public void offer(int val) {  
    ListNode newNode = new ListNode(val);  
    if(this.head == null) {  
        this.head = this.tail = newNode;  
        return ;    
    }  
    this.tail.next = newNode;  
    newNode.pre = this.tail;  
    this.tail = this.tail.next;  
}

对于入队列操作，我们这里是利用链表来实现的队列，因此在进行插入操作的时候要特别注意队列为空时的操作。
2. 出队列(poll): 我们从队头进行数据的删除操作。

public int poll() {  
    if(isEmpty()) {  
        throw new EmptyException("队列为空，不能poll");  
    }  
    int val = this.head.val;  
    this.head = this.head.next;  
    if(this.head == null) {  
        this.tail = this.head;  
    }else {  
        this.head.pre = null;  
    }  
    return val;  
}

需要特别注意判别队列是否为空，当队列为空时删除操作是没有意义的。

2.3 队列的模拟实现

链表模拟实现队列

public class MyQueue {  
    static class ListNode {  
        public int val;  
        public ListNode next;  
        public ListNode pre;  
  
        public ListNode(int val) {  
            this.val = val;  
        }  
  
        @Override  
        public String toString() {  
            return "ListNode{" +  
                    "val=" + val +  
                    ", next=" + next +  
                    '}';  
        }  
    }  
    public ListNode head;  
    public ListNode tail;  
    //入队列  
    public void offer(int val) {  
        ListNode newNode = new ListNode(val);  
        if(this.head == null) {  
            this.head = this.tail = newNode;  
            return ;        }  
        this.tail.next = newNode;  
        newNode.pre = this.tail;  
        this.tail = this.tail.next;  
    }  
    //出队列  
    public int poll() {  
        if(isEmpty()) {  
            throw new EmptyException("队列为空，不能poll");  
        }  
        int val = this.head.val;  
        this.head = this.head.next;  
        if(this.head == null) {  
            this.tail = this.head;  
        }else {  
            this.head.pre = null;  
        }  
        return val;  
    }  
    //获取队头元素  
    public int peek() {  
        if(isEmpty()) {  
            throw new EmptyException("队列为空，不能peek");  
        }  
        return this.head.val;  
    }  
    //获取队列中有效元素个数  
    public int size() {  
        ListNode cur = this.head;  
        int len = 0;  
        while(cur != null) {  
            len++;  
            cur = cur.next;  
        }  
        return len;  
    }  
    public boolean isEmpty() {  
        return this.head == null;  
    }  
  
  
}

原文地址：https://blog.csdn.net/2302_79249715/article/details/142743148

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！