转载请标明出处，谢谢！
https://www.jianshu.com/p/8cb602ef4e21
关联文章
冒泡、选择排序 https://www.jianshu.com/p/176b0b892591
栈和队列 https://www.jianshu.com/p/8cb602ef4e21
顺序表、单双链表 https://www.jianshu.com/p/3aeb5998e79e
二叉树 https://www.jianshu.com/p/de829eab944c
图论 https://www.jianshu.com/p/cf03e51a3ca2
栈和队列
栈：只允许在表的末端进行插入和删除的线性表。基于数组存储表示的栈称为 顺序栈，基于链表的存储表示的栈称为链栈
image
栈的存储特性可以理解成子弹压入弹夹中。先压入的子弹总数在最后才弹出。因此栈也称为先进后出(LIFO, Last In First Out) 的线性表
下面用代码表示下：采用链式栈的方式
public class Node<T> {
T data;//结点数据
Node next;//指针
private Node(T data) {
this.data = data;
}
public Node() {
}
}
public class Stack {
private Node stackTop; //栈顶
private Node stackBottom; //栈底
public Stack(Node stackTop, Node stackBottom) {
this.stackTop = stackTop;
this.stackBottom = stackBottom;
}
private Stack() {
}
}
入栈：将原本栈顶指向的节点交由新节点来指向，栈顶指向新加入的节点
/**
* 入栈
*
* @param stack 原本的栈
* @param newNode 新的结点
*/
public void pushToStack(Stack stack, Node newNode) {
/*新节点变成栈顶*/
newNode.next = stack.stackTop;
stack.stackTop = newNode;
}
空栈：如果栈顶和栈底指向相同，说明是空栈
/**
* 判断是否是空栈
*
* @param stack
* @return
*/
public boolean isEmpty(Stack stack) {
return stack.stackTop == stack.stackBottom;
}
遍历：栈顶指针不断向下移，直到到达栈底。为了避免影响原栈，使用临时结点指向stackTop并且随之一起移动。
/**
* 栈的遍历
*
* @param stack
*/
public void traverse(Stack stack) {
Node temp = stack.stackTop;
/*如果空栈不执行*/
if (isEmpty(stack)) {
System.out.println("空栈");
return;
}
while (!isEmpty(stack) && temp != null) {
System.out.println(temp.data);
temp = temp.next;
}
}
出栈：将栈顶指针向下移动一位
/**
* 出栈
*
* @param stack
*/
public void popStack(Stack stack) {
if (isEmpty(stack)) {
return;
}
stack.stackTop = stack.stackTop.next;
}
清空栈：实际上就是不断的出栈，直到到达栈底
/**
* 清空栈
*
* @param stack
*/
public void clearStack(Stack stack) {
if (isEmpty(stack)) {
return;
}
while (!isEmpty(stack)) {
popStack(stack);
}
}
测试：
@Test
public void test() {
Stack stack = new Stack();
for (int i = 0; i < 5; i++) {
pushToStack(stack, new Node("我是结点" + i));
}
System.out.println("栈的长度 = "+ getLength(stack));
traverse(stack);
popStack(stack);
popStack(stack);
popStack(stack);
System.out.println("------出栈后-------");
traverse(stack);
clearStack(stack);
System.out.println("------清空栈-------");
traverse(stack);
}
image.png
队列
队列：队列是限定数据存储位置的一种线性表，它允许在一端插入，再另一端删除。允许插入的一端叫队尾，允许删除的一端叫做队头。
image
队列基于数组的存储表示称为顺序队列。是利用一个一维数组 array[maxLength]表示存储的.并且利用了2个指针front和rear分别表示队头和队尾的位置。
如图表示：当front等于rear时，此队列不是还剩一个元素，而是空队列。
image
当有数据插入的时候，数据插入的位置是当前rear的位置，而rear的值就要前进一位，因为rear永远指向下一个数据的存储位置。
image
当数据删除的时候 首先要把当前front指向位置的数据记录下来，然后front的指向位置就要+1，最后把记录的元素返回。因为front指向的位置永远都是对头元素
image
那么问题来了，rear永远指向下一个位置元素的存储位置，那么如果出现上图的情况不就是存储的内存溢出了吗？ 实际上这个溢出是”假溢出“
因为我们可以发现 再数据的前面实际上还有空位置可以利用。根据这种情况，为了充分利用资源空间从而引出了循环队列
image
用2个公式表示
队头指针进1 ： front = (front+1)%maxLength ;
队尾指针进1 ： rear = (rear+1)%maxLength ;
如果循环队列读取元素的速度大于存入的速度，队头指针很快就赶上队尾指针，一旦front == rear 则变成空队列，反之，如果存入元素的速度大于读取的，队尾指针赶上队头指针，如果队列满就不能再添加数据了。为了区分空队列和满队列，用(rear+1)%maxLength == front来表示满队列，用 rear== front表示空队列。
同样的用代码测试一下：用顺序队列表示下
private final static int MAX_LENGTH = 5;
public class Queue {
public String[] array;
public int front;
public int rear;
public Queue() {
front = 0;
rear = 0;
array = new String[MAX_LENGTH];
}
}
判断是否满队列 ：用公式rear = (rear+1)%maxLength ==front;
/**
* 判断是否满队列
*
* @param queue
* @return
*/
public boolean isFull(Queue queue) {
return (queue.rear + 1) % MAX_LENGTH == queue.front;
}
判断是否是空队列：用公式 rear== front
/**
* 判断是否是空队列
*
* @param queue
* @return
*/
public boolean isEmpty(Queue queue) {
return queue.rear == queue.front;
}
入队列 ：数据插入的位置是当前rear的位置，而rear的值就要前进一位，因为rear永远指向下一个数据的存储位置。
/**
* 添加数据
*
* @param queue
* @param data
*/
public void enQueue(Queue queue, String data) {
if (isFull(queue)) {
System.out.println("满队列");
return;
}
queue.array[queue.rear] = data;
queue.rear = (queue.rear + 1) % MAX_LENGTH;
}
删除数据 ：front的指向位置就要向前一位
/**
* 删除数据
*
* @param queue
*/
public void delQueue(Queue queue) {
if (isEmpty(queue)) {
System.out.println("空队列");
return;
}
queue.front = (queue.front + 1) % MAX_LENGTH;
}
清空队列：
/**
* 清空数据
*
* @param queue
*/
public void clear(Queue queue){
if (isEmpty(queue)) {
System.out.println("空队列");
return;
}
while (!isEmpty(queue)){
System.out.println(queue.array[queue.front]);
queue.front = (queue.front+1) % MAX_LENGTH;
}
}
遍历队列：使用临时变量防止破坏源数据
/**
* 遍历
*
* @param queue
*/
public void traverse(Queue queue) {
if (isEmpty(queue)) {
System.out.println("空队列");
return;
}
int tempFront = queue.front;
while (tempFront!= queue.rear) {
System.out.println(queue.array[tempFront]);
tempFront = (tempFront + 1) % MAX_LENGTH;
}
}
测试一下：
@Test
public void test() {
Queue queue = new Queue();
enQueue(queue, "1");
enQueue(queue, "2");
enQueue(queue, "3");
traverse(queue);
System.out.println("删除一个数据后");
delQueue(queue);
traverse(queue);
System.out.println("清空数据后");
clear(queue);
traverse(queue);
}
image.png
网友评论