(四) 链栈
一、什么是链栈？
使用链式存储的栈，就是链栈。
插入和删除操作在栈顶进行，也就是链表的尾端。
存储单元由2部分组成：数据域 data 和指针域 next 。
使用top栈顶指针用于指向栈尾
二、链栈类 【LinkStack】
package data.linear_table.stack_queue; import data.linear_table.node.Node; //链栈类 public class LinkStack implements IStack { private Node top ; //栈顶元素的引用 //将栈置空 @Override public void clear() { top = null ; } //判断链栈是否为空 @Override public boolean isEmpty() { return top == null ; } //求链栈的长度 @Override public int length() { //{...} return 0 ; } //取栈顶元素并返回其值 @Override public Object peek() { //栈如果不为空 if (!isEmpty()) { //返回栈顶元素 return top.data ; }else { return null ; } } //入栈 @Override public void push(Object x) throws Exception { //{...} } //出栈 @Override public Object pop() { // {...} return null ; } //输出栈中所有数据元素（从栈顶元素到栈底元素） public void display() { Node p = top ; //初始化，p指向栈顶元素 while (p != null ) { //输出所有非空结点的数据元素值 System.out.print(p.data.toString()+" "); p = p.next ; //p指针向后移 } } }
注： 代码中 ” {....}“ 处，会在后面单独进行讲解。
1. public class LinkStack { 2. private Node top; //栈顶指针 3. }
算法：链栈的长度
//求链栈的长度 @Override public int length() { Node p = top ; //初始化,p指向栈顶元素 int length = 0 ; //length为计数器 //从栈顶元素开始向后查找，直到p为空 while (p != null ) { p = p.next ; //p指向后继结点 length++ ; //长度增加1 } return length ; }
算法：入栈
public void push(Object x) { Node p = new Node(x); // 创建新结点p p.next = top; // 1.p的指针域指向栈顶元素 top = p; // 2.栈顶指针top指向新结点p }
算法：出栈
public Object pop() { if(top == null) { //空栈 isEmpty() return null; } else { Node p = top; // 1 存放栈顶元素 top = top.next; // 2 将top指向栈顶的下一个元素 return p.data; // 3 返回栈顶元素数据 } }
(五) 队列
一、什么是队列？
队列是一个特殊的线性表。
只允许在队尾进行插入操作
只允许在队首进行删除操作
----------------------------------------------------------------------------
二、队列的相关术语？
队尾rear：进行插入操作的一端。
队首front :进行删除操作的一端
入队offer : 进行插入操作，称为入队
出队 poll : 进行删除操作 ， 称为出队
三、 队列有哪两种存储方式 ？
使用顺序存储的称为顺序队列 。
使用链式存储的称为链队列 。
----------------------------------------------------------------------------
四、队列的抽象数据类型Java接口【IQueue】
package data.linear_table.stack_queue; //队列的抽象数据类型Java接口 public interface IQueue { public void clear() ; //置队成空队列 public boolean isEmpty() ; //判断队列是否为空 public int length() ; //队列中数据元素的个数 public Object peek() ; //取队列首元素 public void offer(Object x) throws Exception; //将元素x插入到队列中使用成为新的队尾元素 public Object poll() ; //删除对首元素并返回其值。若队列为空，则返回null }
(六) 顺序队列
一、什么是顺序队列？
· 顺序队列的存储结构中，需要分配一块地址连续的存储区域来一次存放队列中从队首到队尾的所有元素。
二、关于队列的那些操作？
front表示队首，进行出队操作时，front进行计数。
rear表示队尾，进行入队操作时，rear进行计数。
front == rear == 0 为空队列。
入队操作：
出队操作：
三、队列存在的问题“假溢出”
因为顺序队列的多次入队和出队操作后出现有存储空间，但是又不能顺序入队的溢出现象，称为“假溢出”。
假溢出，数组的最后一个元素已经添加数据，但队列没有满 。
解决方案：使用循环队列解决“假溢出”问题。将顺序队列所使用的存储空间看成是一个逻辑上首尾相连的循环队列。
----------------------------------------------------------------------------
(七) 循环顺序队列
一、什么是循环顺序队列？
在逻辑上队首和队尾连接在一起。
存在的问题：队首front和队尾rear重叠时，无法区分队满还是队空。
解决方案 ：
方案1：设计一个计数器，出入队累计法。（整数变量num，入队+1，出队-1，如果num=0就是空）。判断条件为：num == 0 为队空；num > 0 && front == rear 为队满。
方案2：设计一个标识变量法。（flag=0出队，flag=1入队，重叠后0表示空，1表示满）。判断条件为：front == rear && flag == 0 为队空；front == rear && flag == 1 为队满。
方案3：少用一个存储单位。当顺序存储空间为maxSize时，只允许最多存放maxSize -1个数据元素。判断条件为：
// 队列空 front == rear; // 队列满 (rear + 1) % maxSize == front;
详解 front == (rear+1) % maxSize 为 队满 ：
