一、栈
1.栈的概念
- 栈： 一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
- 压栈： 栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
- 出栈： 栈的删除操作叫做出栈。出数据在栈顶。
2.栈的实现
- （1）利用顺序表实现，即使用尾插 + 尾删的方式实现
- （2）利用链表实现，则头尾皆可
相对来说，顺序表的实现上要更为简单一些，所以我们优先用顺序表实现栈。
// 基于数组实现链表
public class Stack<E> {
private E[] elementData; // 栈中的元素
private int size; // 当前栈中元素个数
public Stack() {
elementData = (E[]) new Object[10]; // 默认长度为10
}
public Stack(int initCap) {
elementData = (E[]) new Object[initCap]; // 初始长度
}
// 入栈
public void push(E value) {
// 扩容
if(size == elementData.length) {
int oldLength = elementData.length;
int newLength = oldLength << 1;
elementData = Arrays.copyOf(elementData, newLength);
}
// 在数组尾部添加元素
elementData[size++] = value;
}
// 出栈,返回原来的栈顶元素
public E pop () {
if(getSize() == 0) {
throw new NoSuchElementException("栈中没有元素！");
}
// 得到原来的栈顶元素位置
E oldVaule = elementData[size - 1];
size--;
elementData[size] = null;
return oldVaule;
}
// 查看栈顶元素
public E peek() {
if(getSize() == 0) {
throw new NoSuchElementException("栈中没有元素！");
}
return elementData[size - 1];
}
// 获取当前栈的长度
public int getSize() {
return size;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
for (int i = 0; i < size; i++) {
stringBuilder.append(elementData[i]);
if(i != size - 1) {
stringBuilder.append(",");
}
}
stringBuilder.append("]");
return stringBuilder.toString();
}
}二、队列
1.队列的概念
- 队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。
- 队列满足先进先出的性质（FIFO)，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个作为新的队首。
2.队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
/**
* 基于链表的队列实现
*/
public class LinkedQueue{
private Node head;
private Node tail;
private int size;
private class Node {
private int data;
private Node next;
public Node(int data) {
this.data = data;
}
}
// 入队
public void offer(int value) {
Node node = new Node(value);
if(head == null) {
head = tail = node;
} else {
tail.next = node;
tail = node;
}
size++;
}
// 出队(队首元素出队）
public int poll() {
if(size == 0) {
throw new NoSuchElementException("对列为空！");
} else {
int oldValue = head.data;
Node tempHead = head;
head = head.next;
tempHead.next = null;
size--;
return oldValue;
}
}
// 查看队首元素
public int peek() {
if(size == 0) {
throw new NoSuchElementException("对列为空！");
}
return head.data;
}
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("front[");
Node node = head;
while (node != null) {
stringBuilder.append(node.data);
if(node.next != null) {
stringBuilder.append(",");
}
node = node.next;
}
stringBuilder.append("]tail");
return stringBuilder.toString();
}
}3.循环队列的概念
- 实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现。
- 在顺序队列中，当下标走到队尾后，不能再往后走插入元素，但其实数组中还有位置，这叫做“假溢出”，为了解决这个问题提高数组利用率，就出现了循环队列。
- 实现循环对列，最重要的是如何判断队列为空还是为满。
4.循环队列的实现
如何区分循环队列的空与满：
- 通过 size 属性记录当前队列中的元素个数
- 保留一个位置，这个位置不能存储元素。这样当队满为 front == （rear+ 1）% length，队空为 front ==rear
- front：指向循环队列的第一个元素下标，rear：指向循环队列的最后一个元素的下一个下标
/**
* 循环队列
*/
public class LoopQueue implements IQueue {
// 指向循环队列的最后一个元素的下一个位置
private int tail;
// 队首元素，指向队列中的第一个元素索引
private int front;
// 有效元素个数
private int size;
private int[] data;
public LoopQueue(int k) {
data = new int[k + 1];
}
// 判断队列是否已满
public boolean isFull() {
if ((tail + 1) % data.length == front) {
return true;
}
return false;
}
// 判断队列是否为空
public boolean isEmpty() {
// if (front == tail) {
// return true;
// }
// return false;
return tail == front;
}
// 入队
public void offer(int value) {
if (isFull()) {
System.err.println("队列已满！");
return;
} else {
data[tail] = value;
tail = (tail + 1) % data.length;
size++;
}
}
// 出队
public int poll() {
if (isEmpty()) {
System.err.println("队列为空！");
return -1;
} else {
int value = data[front];
front = (front + 1) % data.length;
size--;
return value;
}
}
// 查看队首元素
public int peek() {
if (isEmpty()) {
System.err.println("队列为空！");
return -1;
}
return data[front];
}
// 查看队尾元素
public int getTail() {
if (isEmpty()) {
System.err.println("队列为空！");
return -1;
}
// 最后一个元素的下标
int index = tail == 0 ? data.length - 1 : tail - 1;
return data[index];
}
// 判断有效个数
public int getSize() {
return size;
}
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
// 最后一个元素的位置
int lastIndex = tail == 0 ? data.length - 1 : tail - 1;
for (int i = front; i != tail; ) {
stringBuilder.append(data[i]);
if (i != lastIndex) {
stringBuilder.append(",");
}
i = (i + 1) % data.length;
}
stringBuilder.append("]");
return stringBuilder.toString();
}
}5.双端队列的概念
双端队列(Deque:double ended queue)就是一个两端都是结尾的队列。队列的每一端都可以插入数据项和移除数据项。相对于普通队列，双端队列的入队和出队操作在两端都可进行。
6.双端队列的实现
我们使用最常用的顺序结构来存储双端队列，为了节省空间，把它首尾相连，构成循环队列。并且规定left指向左端的第一个元素，right指向右端的下一个位置。那么队空的判断则是left== right ，队满是(left-1+MAX)%MAX== right或者(right-left+MAX)%MAX==MAX。
class ListNode {
//数据域
public int val;
//指针
public ListNode next;
//初始化值
public ListNode(int val) {
this.val = val;
}
}
public class Deque {
public ListNode head;//头结点
public ListNode last;//尾节点
//在双端队列头那边添加节点变成新的头结点
//在第一个节点处添加一个节点
public void addFirst(int val) {
//创建对象初始化值建立新节点
ListNode node = new ListNode(val);
//判断尾节点是否为空
if (this.last == null) {
//若为空就是头结点尾节点都是这个新创建的节点
this.head = node;
this.last = node;
}
//node成为新的头节点
node.next = this.head;
this.head = node;
}
//在双端队列尾那边添加节点变成新的尾节点
//在节点的最后添加一个节点
public void addLast(int val) {
//创建对象初始化值建立新节点
ListNode node = new ListNode(val);
//判断尾节点是否为空
if (this.last == null) {
//若为空就是头结点尾节点都是这个新创建的节点
this.head = node;
this.last = node;
}
//node成为新的尾节点
this.last.next = node;
this.last = node;
}
//从头结点那边拿出Deque的一个节点
public int offerFirst() {
//判断头节点是否为空，如果是就输出！
if (this.head == null) {
System.out.println("!");
return -1;
}
//如果不为空，把头结点指向的值拿出来
int oldValue = this.head.val;
//判断头结点尾节点是否重合，如果重合就表明双端队列为空
if (this.head == this.last) {
this.head = null;
this.last = null;
} else {
//没有重合就接着找下一个节点变成新的头结点
this.head = this.head.next;
}
return oldValue;
}
//从尾结点那边拿出Deque的一个节点
public int offerLast() {
//判断尾节点是否为空，如果就输出！
if (this.last == null) {
System.out.println("!");
return -1;
}
// //如果不为空，把尾结点指向的值拿出来
int oldValue = this.last.val;
//判断头结点尾节点是否重合，如果重合就表明双端队列为空
if (this.head == this.last) {
this.last = null;
this.head = null;
} else {
//遍历找到新的尾节点
ListNode cur = this.head;
while (cur.next != last) {
cur = cur.next;
}
//把找到的最后一个节点做为尾节点
this.last = cur;
//尾节点.next=null
this.last.next = null;
}
return oldValue;
}
//获取Deque处第一个节点的值
public int peekFirst() {
//判断头结点是否为空，是就输出！
if (this.head == null) {
System.out.println("!");
return -1;
}
//返回头结点值
return this.head.val;
}
//获取Deque上最后一个节点的值
public int peekLast() {
//判断尾结点是否为空，是就输出！
if (this.last == null) {
System.out.println("!");
return -1;
}
//返回尾结点值
return this.last.val;
}
//Check whether the Deque is empty
public boolean empty() {
return this.head == null;
}
public void display(){
ListNode cur =head;
while (cur!=last) {
System.out.println(cur.val);
cur = cur.next;
}
System.out.println(cur.val);
}
}三、java 中的栈和队列
1.Java集合框架
Java集合框架图：
2.Java中的Stack（栈）
Stack的方法及说明（Stack继承了Vecter,自己独有的方法只有以下5个）：
| 方法 | 解释 |
|---|---|
| Object push(Object item) | 将元素推送到堆栈顶部 |
| Object pop() | 移除并返回堆栈的顶部元素；如果我们在调用堆栈为空时调用pop（）,则抛出’EmptyStackException’异常 |
| Object peek() | 返回堆栈顶部的元素，但不删除它 |
| boolean empty() | 如果堆栈为空，即顶部没有任何内容，则返回true；否则，返回false |
| int search(Object element) | 确定对象是否存在于堆栈中，如果找到该元素，它将从堆栈顶部返回元素的位置；否则，它返回-1 |
3.Java中的Queue（队列）
Queue的方法及说明：
| 方法 | 解释 |
|---|---|
| offer() | 将指定的元素插入此队列，插入成功返回 true；否则返回 false |
| add() | 将指定的元素插入此队列，当使用有容量限制插入失败时抛出一个 IllegalStateException异常 |
| poll() | 获取并移除此队列的头，如果此队列为空，则返回 null |
| remove() | 获取并移除此队列的头，如果此队列为空，则抛出NoSuchElementException异常 |
| peek() | 返回队列的头元素但不删除，如果此队列为空，则返回 null |
| element() | 返回队列的头元素但不删除，如果此队列为空，方法会抛出NoSuchElementException异常 |
4.Java中的Deque（双端队列）
Deque的方法及说明：
| 方法 | 解释 |
|---|---|
| addFirst() | 向队头插入元素，如果元素为空，则发生NPE(空指针异常) |
| addLast() | 向队尾插入元素，如果为空，则发生NPE |
| offerFirst() | 向队头插入元素，如果插入成功返回true，否则返回false |
| offerLast() | 向队尾插入元素，如果插入成功返回true，否则返回false |
| removeFirst() | 返回并移除队头元素，如果该元素是null，则发生NoSuchElementException |
| removeLast() | 返回并移除队尾元素，如果该元素是null，则发生NoSuchElementException |
| pollFirst() | 返回并移除队头元素，如果队列无元素，则返回null |
| pollLast() | 返回并移除队尾元素，如果队列无元素，则返回null |
| getFirst() | 获取队头元素但不移除，如果队列无元素，则发生NoSuchElementException |
| getLast() | 获取队尾元素但不移除，如果队列无元素，则发生NoSuchElementException |
| peekFirst() | 获取队头元素但不移除，如果队列无元素，则返回null |
| peekLast() | 获取队尾元素但不移除，如果队列无元素，则返回null |
声明：本站所有资源，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
