栈
栈是一种特殊的线性表，只能在一端进行操作，往栈中添加元素的操作，一般叫做push，入栈，从栈中移除元素的操作，一般叫做pop，出栈(只能移除栈顶元素，也叫做弹出栈顶元素)，并且栈遵循后进先出，例如下图：
入栈
入栈操作
出栈
出栈操作
栈的接口设计
int size();//元素的数量
boolean isEmpty();//是否为空
void push(E element);//入栈
E pop();//出栈
E top();//获取栈顶元素
void clear();//清空
代码实现图
stack实现图
这个Stack是基于动态数组的操作
栈的应用
浏览器的前进和后退
实现模式：
输入jd.com->qq.com->baidu.com
浏览器前进后退实现图
队列(Queue)
队列是一种特殊的线性表，只能在头尾两端进行操作，队尾(rear)只能从队尾添加元素，一般叫做enQueue，入队，队头(front)只能从队头移除元素，一般叫做deQueue，出队，遵循先进先出的原则,First In First Out,FIFO,队列如下图表现形式：
队列
单端队列的接口设计
int size();//元素的数量
boolean isEmpty();//是否为空
void clear();//清空
void enQueue(E element);//入队
E deQueue();//出队
E front();//获取队列的头元素
单端队列的设计代码
单端队列的设计
双端队列(Deque)
双端队列和单端队列的不同之处是多了队尾出队和队头入队
接口设计如下
int size();//元素的数量
boolean isEmpty();//是否为空
void clear();//清空
E deQueueFront();//从队头出队
void enQueueFrong(E element);//从队头入队
E deQueueRear();//从队尾出队
E front();//获取队列的头元素
E rear();//获取队列的尾元素
代码设计图
代码设计图
循环队列
循环队列只是在队列的基础之上添加多了一个front节点，这个节点就是代表可以循环队列长度，整个流程大概如下：
循环队列图1
循环队列图2
接口设计
int size();
void clear();
void enQueue(E element);
E deQueue();
下面看看代码实现图：
队列中真实索引
扩大容量
这里扩大容量之后，要将front重置等于0，是因为扩容之后，顺序会被按照先后的插入书序在队列中存储好，所以队列中的0节点元素也就是队头，所以要设置front等于0
出栈
出栈之后size的值要减去1，并且front要指向下一个元素，而至于front为什么不用front--，这是因为涉及到前面节点有空，但是后面节点又满了，这个时候需要往前面插入，所以这个front要通过那样的算法去获取
进栈
进栈相对出栈相对来说简单点，就是一个扩容赋值操作，然后进行size++就可以了
清除元素
删除直接将元素置空就可以了
循环双端队列
循环双端队列和循环单端队列其实就多了两个方法，就是从尾部出队和从头部入队两种方法
代码图：
从尾部入队
从头部出队
从头部入队
从尾部出队
可以看到从尾部入队和从头部出队和单循环队列是没有区别的，而另外两个方法从实现看上去也是很简单的，从头部入队，就是重新计算front，然后赋值给front索引的下标即可，至于为什么是index(-1)这个原因是从巨人的想法中承接下来的，我只会拿来用而已，的确是可以实现，搞不清楚的可以画个图自己实现一下，至于尾部出队，则就是找到尾部的索引，然后将元素赋值为null就可以了，或者有人说那个index(int index)方法，也就是获取真实索引的那个方法，为什么不通过%运算符来实现，那是因为%运算符，除法，乘法，浮点数等运算效率都会比较低，所以才用上面写的那种方式的(https://crazyjvm.iteye.com/blog/1725508)，好了，队列和栈就到此为止
网友评论