文章目录
- 一、栈的概念
- 二、栈的实现
- 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<>();//双端队列的链式实现
文章出处登录后可见！
