一、栈
(一)概念
栈:是一种特殊的线性表,其只允许在固定的一段进行插入和删除元素操作,进行数据插入和删除操作的一端称为栈顶,另一端称为栈底,栈中的数据元素遵守后进先出的原则
压栈:栈的插入操作叫做进栈,入数据在栈顶
出栈:栈的删除操作叫做出栈,出数据在栈顶
栈在现实生活中的例子:
(二)栈的使用
我们可以看到Java中的Stack给了如下方法
import java.util.Stack;
public class test {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(12);
stack.push(23);
stack.push(34);
System.out.println(stack.peek());//看一下栈顶的元素但是不删除
System.out.println(stack.pop());//删除栈顶元素
System.out.println(stack.peek());//看一下栈顶的元素但是不删除
System.out.println(stack.isEmpty());//判断栈是否为空
System.out.println(stack.size());//栈中元素个数
}
}
//输出结果
34
34
23
false
2
Process finished with exit code 0
(三)栈的模拟实现
栈的底层实际上就是一个数组,接下来我们来实现一下其中的操作
添加元素
//往栈中添加元素
public void push(int val){
if (isFull()){
elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize] = val;
this.usedSize++;
}
判断是否为空栈
public boolean isEmpty(){
return usedSize == 0;
}
弹出元素
public int pop(){
if (isEmpty()){
throw new no();
}
int oldVal = elem[usedSize-1];
usedSize--;
return oldVal;
}
返回栈顶元素
public int peek(){
if (isEmpty()){
throw new no();
}
return elem[usedSize-1];
}
(四)利用栈的特性逆序打印链表
在一个链表中,我们可以利用栈的特性,先进后出,来逆序打印这个链表
public void reservePrintList(){
Stack<ListNode> stack = new Stack<>();
ListNode cur = head;
while (cur != null){
stack.push(cur);
cur = cur.next;
}
while (!stack.isEmpty()){
ListNode top = stack.pop();
System.out.print(top.val + " ");
}
}
二、队列
(一)概念
队列:只允许在一段进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出的特征
入队列:进行插入操作的一端叫做队尾
出队列:进行删除操作的一端称为队头
(二)队列的使用
public static void main(String[] args) {
Queue<Integer> queue1 = new LinkedList<>();//单向队列
Deque<Integer> queue2 = new LinkedList<>();//双端队列
queue1.offer(1);
queue1.offer(2);
queue1.offer(3);//从队尾入队列
System.out.println(queue1.poll());//从队头出队列
System.out.println(queue1.peek());//看一眼队头元素
System.out.println(queue1.isEmpty());//判断队列是否为空
}
//输出结果
1
2
false
Process finished with exit code 0
(三)队列的模拟实现
队列中既然可以存储元素,那么底层肯定要有能够保存元素的空间,通过前面线性表的学习了解到常见的空间类型有两种:顺序结构和链式结构,从实际情况来看,链式结构操作队列相对简单一些
插入元素
//头插法
public void offer(int x){
ListNode node = new ListNode(x);
if (front == null){
front = rear = node;
}else {
node.next = front;
front.prev = node;
front = node;
}
usedSize++;
}
删除元素
//出队列
public int poll() {
if (front == null) {
return -1;
}
int ret = front.val;
if (front == rear) {
front = null;
rear = null;
usedSize--;
return ret;
}
front = front.next;
front.prev = null;
usedSize--;
return ret;
}
获取队头元素
public int peek(){
if (front == null){
return -1;
}
return front.val;
}
求出队列长度
public int getUsedSize(){
return usedSize;
}
判断是否为空
public boolean isEmpty(){
return usedSize == 0;
}
三、循环队列
环形队列通过循环利用存储空间,避免了普通队列中因元素出队而导致的空间浪费问题。在普通队列中,当队列头部的元素被移除后,前面的存储空间无法再被利用,而环形队列则可以将这些空闲的空间重新用于存储新的元素
循环队列的方法
public class MuCircularQueue {
private int[] elem;
private int front;
private int rear;
public MuCircularQueue(int k){
//采用浪费一个位置来判断是否为满,所以要多开辟一个格子的空间
this.elem = new int[k+1];
}
public boolean isEmpty(){
return front == rear;
}
public boolean isFull(){
if ((rear+1)%elem.length == front){
return true;
}
return false;
}
//入队操作
public boolean enQueue(int value){
if (isFull()){
return false;
}
elem[rear] = value;
rear = (rear+1)%elem.length;
return true;
}
//出队操作
public boolean deQueue(){
if (isEmpty()){
return false;
}
front = (front+1)%elem.length;
return true;
}
//得到队头元素
public int Front(){
if (isEmpty()){
return -1;
}
return elem[front];
}
//得到队尾元素
public int Rear(){
if (isEmpty()){
return -1;
}
int index = (rear == 0)?elem.length-1:rear-1;
return index;
}
}
四、双端队列
双端队列是指允许两端都可以进行入队和出队操作的队列,那就说明元素可以从队头出队和入队,也可以从队尾出队和入队
Deque是一个接口,使用时必须创建LinkedList的对象
在实际工程中,使用Deque接口是比较多的,栈和队列均可以使用该接口
public class demo {
public static void main(String[] args) {
Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现
stack.push(1);
stack.pop();
queue.offer(1);
queue.poll();
}
}