数据结构--栈和队列

1.栈(Stack)

1.1 介绍

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

1.2 栈的实现

栈可以通过自己写代码来模拟实现，或直接使用java.util包中的Stack类实现

1.2.1 模拟实现栈

• 压栈(入栈)：栈的插入操作，插入的数据在栈顶
• 出栈：栈的删除操作，出数据在栈顶

import java.util.Arrays;public class MyStack {public int[] elem;public int usedSize;public static final int DEFAULT_CAPACITY = 10;public MyStack() {elem = new int[DEFAULT_CAPACITY];}public void push(int val) { //入栈if (isFull()) {this.elem = Arrays.copyOf(elem, elem.length * 2);}elem[usedSize++] = val;}public int pop() { //出栈if (isEmpty()) {throw new StackEmptyException("当前栈为空");}usedSize--;return elem[usedSize];}public int peak() {if (isEmpty()) {throw new StackEmptyException("当前栈为空");}return elem[usedSize - 1];}public boolean isFull() {return elem.length == usedSize;}public boolean isEmpty() {return usedSize == 0;}
}

1.2.2 Stack类实现

Stack类实现了后进先出的栈结构，使用Stack类可以直接创建一个栈

import java.util.Stack;
public class Main {public static void main(String[] args) {//创建一个栈，栈中元素类型为Integer(int的包装类)Stack<Integer> stack = new Stack();}
}

1.3 栈的常用方法

方法	功能
Stack( )	构造一个空的栈
E push(E e)	将e入栈，并返回e
E pop( )	将栈定元素出栈并返回
E peek( )	获取栈定元素
int size( )	获取栈中有效元素个数
boolean empty( )	检测栈是否为空

1.4 栈，虚拟机栈和栈帧的区别

• 栈：一种数据结构
• 虚拟机栈：JVM中的一块内存
• 栈帧：方法调用过程中，在虚拟机栈上开辟的一块内存

2.队列(Queue)

2.1 介绍

队列也是一种特殊的线性表，不同于栈，队列只允许在一端进行插入数据操作，在另一端进行删除数据操作。进行插入操作的一端称为队尾，进行删除操作的一端称为队头。队列中的数据元素遵守先进先出的原则

2.2 队列的实现

队列也可以通过自己写代码来模拟实现，或使用Queue接口来实现

2.2.1 模拟实现队列

public class MyQueue {static class ListNode {int val;ListNode prev;ListNode next;public ListNode(int val) {this.val = val;}}ListNode head;ListNode last;public void offer(int val) { //入队ListNode node = new ListNode(val);if (head == null) {head = node;last = node;} else {last.next = node;node.prev = last;last = node;}}public int poll() { //出队if (head == null) {return -1;}int val = head.val;if (head.next == null) {head = null;last = null;return val;}head = head.next;head.prev = null;return val;}public int peek() {if (head == null) {return -1;}return head.val;}public boolean isEmpty() {return head == null;}
}

2.2.2 Queue接口实现

LinkedList(双链表)实现了Queue接口(底层通过链表实现)，可以使用LinkedList类来创建队列

import java.util.LinkedList;
import java.util.Queue;
public class Main {public static void main(String[] args) {Queue<Integer> queue = new LinkedList<>();}
}

2.3 队列的常用方法

方法	功能
boolean offer(E e)	入队列
E poll( )	出队列
E peek( )	获取队头元素
int size( )	获取队列中有效元素的个数
boolean isEmpty( )	检测队列是否为空