文章目录
- 一、栈的概念
- 二、栈的实现
- 2.1压栈(push)
- 2.2出栈(pop)
- 2.3获取栈顶元素(peek)
- 2.4判断栈是否为空(isEmpty)
- 栈的实现测试
- 三、队列的概念
- 四、队列的实现
- 4.1入队(offer)
- 4.2出队(poll)
- 4.3判断队列是否为空
- 4.4获取对头元素
- 队列的实现测试
- 五、循环队列
- 5.1入队
- 5.2出队
- 5.3获取队头元素
- 5.4获取队尾元素
- 5.5判断队列是否为空
- 六、双端队列
一、栈的概念
栈： 一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶
出栈：栈的删除操作叫做出栈。出数据在栈顶
二、栈的实现
栈是一个特殊的顺序表,所以采用链表和数组的方式都可实现,但是,一般采用数组的方式实现
创建一个类：
public class MyStack {//创建一个数组public int[] elem;//存放的元素个数public int usedSize;//默认的容量public static final int DEFAULT_CAPACITY = 5;public MyStack() {this.elem = new int[DEFAULT_CAPACITY];}}2.1压栈(push)
在入栈之前我们要判断栈是否满了，如果满了就要进行扩容
public boolean isFull() {return usedSize == elem.length;}public void push(int val) {//判断if(isFull()) {elem = Arrays.copyOf(elem,2*elem.length);}elem[usedSize] = val;usedSize++;}2.2出栈(pop)
同样在出栈的时候我们也要判断栈是否为空，为空就抛一个异常
public int pop() {//判断if(isEmpty()) {throw new EmptyStackException("栈为空");}int ret = elem[usedSize-1];usedSize--;return ret;}2.3获取栈顶元素(peek)
在获取栈顶元素时也要判断栈是否为空
public int peek() {//判断if (isEmpty()) {throw new EmptyStackException("栈为空");}return elem[usedSize-1];}2.4判断栈是否为空(isEmpty)
public boolean isEmpty() {return usedSize == 0;}栈的实现测试
public class Test {public static void main(String[] args) {MyStack myStack = new MyStack();myStack.push(12);myStack.push(23);myStack.push(34);myStack.push(45);//压栈int ret = myStack.pop();//出栈System.out.println(ret);System.out.println("*****");int num = myStack.peek();//获取栈顶元素System.out.println(num);System.out.println("*****");System.out.println(myStack.isEmpty());//判断栈是否为空}}
三、队列的概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）
四、队列的实现
要想实现一个队列,可以采用链表和数组两种存储数据的方式,那么到底应该用哪种方式实现
对于数组来说,入队列和出队列操作都相对简单,但是可能会造成空间大量浪费，那么我们就可以选择使用链表来实现
创建一个类：
public class MyQueue {static class ListNode{public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;}4.1入队(offer)
因为是链表所以在入队时不用考虑扩容的问题，代码执行时动态分配空间
public void offer(int val) {ListNode node = new ListNode(val);if(head == null) {head = last = node;}else {last.next = node;node.prev = last;last = node;}}4.2出队(poll)
出队时要判断队头是否为空
public int poll() {//判断if(head == null) {return -1;}int val = -1;if(head.next == null) {val = head.val;head = null;last = null;return val;}val = head.val;head = head.next;head.prev = null;return val;}4.3判断队列是否为空
public boolean empty() { return head == null;}4.4获取对头元素
public int peek() {if(head == null) {return -1;}return head.val;}队列的实现测试
public class Test {public static void main(String[] args) {MyQueue queue = new MyQueue();queue.offer(12);queue.offer(23);queue.offer(34);queue.offer(45);//入队int ret = queue.poll();//出队System.out.println(ret);System.out.println("*****");System.out.println(queue.empty());//判断队列是否为空System.out.println("*****");int num = queue.peek();//获取队头元素System.out.println(num);}}
五、循环队列
实际中我们有时还会使用一种队列叫循环队列,循环队列通常使用数组实现。
利用数组实现一个队列可能会浪费大量的空间,那么,就可以使用循环队列,也能解决资源浪费的问题.
循环队列其本质也是一个数组
那我们如何区分空与满呢
1.通过添加 size 属性记录
2.保留一个位置
3.使用标记
这里我们使用第二种方式
5.1入队
因为是使用数组来实现的，所以在入队之前我们要判断队列是否满了
public boolean isFull() {return (rear+1)% elem.length == front;}入队操作
public boolean enQueue(int value) {//判断if (isFull()) {elem = Arrays.copyOf(elem,2*elem.length);}elem[rear] = value;rear = (rear+1)%elem.length;return true;}5.2出队
在进行出队操作时要判断队列是否为空
public boolean deQueue() {if (isEmpty()) {return false;}front = (front+1)%elem.length;return true;}5.3获取队头元素
public int Front() {if (isEmpty()) {return -1;}return elem[front];}5.4获取队尾元素
public int Rear() { if (isEmpty()) { return -1; } return elem[rear];}5.5判断队列是否为空
front和rear相遇了就为空
public boolean isEmpty() {return front == rear;}六、双端队列
双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。
那就说明元素可以从队头出队和入队，也可以从队尾出队和入队
Deque是一个接口，使用时必须创建LinkedList的对象
Deque接口比较多，栈和队列都可以使用该接口
Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现