目录
栈概念
栈的使用方法
栈的操作
栈的模拟实现
用队列实现栈
队列概念
队列的操作
用栈实现队列
循环队列
如何判满（标记队头队尾）
循环队列有效长度的通用公式
循环队列的实现
双端队列
栈
栈，是一种数据结构，遵循先进后出的原则，
只能在一端进行入栈，出栈操作，进行操作的是栈顶，另一端是栈底；
入栈即插入数据，出栈即删除数据
例子：在生活中，羽毛球桶就是一个栈
栈的使用方法
栈的操作
//创建一个只存储整数的栈
Stack<Integer> s = new Stack();
//进行插入
s.push(1);
s.push(2);
s.push(3);
s.push(4);
//获取栈中元素个数 4
System.out.println(s.size());
//查询栈顶元素 4
System.out.println(s.peek());
//出栈 4弹出，栈中余 1 2 3，栈顶为3
s.pop();
栈的模拟实现
Stack 是继承了Vector(线程安全的)，可以用数组实现
public class Mystack{
int []array;
int size;
//用构造方法初始化
public Mystack{
array=new int [3];
}
//入栈
public int push(int e){
//检查当前的空间
ensureCapacity();
//将e赋值到数组的最后一个
array[size++]=e;
return e;
}
//出栈
public int push(int e){
int e=peek();
size--;
return e;
}
//查询
public int peek(int e){
//先判断栈是否为空，为空则无法查询
if(empty()){
return -1;
}
return array[size-1];
}
//判断 当前使用的空间和容量 的关系
public void ensureCapacity(){
//进行扩容，一般为原来的两倍
if(size==array.length)
array=Arrays.copyOf(array,size*2);
}
}
用队列实现栈
栈是先进后出，用两个队列实现，一个 实现入栈，另一个实现出栈（将入栈的数据再 入栈到 实现出栈的队列中）
class Mystack{
//创建两个队列
Queue <Integer>q1;
Queue <Integer>q2;
//对队列初始化
public Mystack{
//队列创建对象时，可以用LinkedList对象
q1= new LinkedList<Integer>();
q2= new LinkedList<Integer>();
}
//入栈
public void push(int x) {
q2.offer(x);
while(!q1.isEmpty()){
//将q1中的元素到q2，直到为空
q2.offer(q1.poll());
}
Queue<Integer> tmp=q1;//交换队列位置
q1=q2;
q2=tmp;
}
//出栈
public int pop() {
return q1.poll();
}
//查询
public int top() {
return q1.peek();
}
public boolean empty() {
return q1.isEmpty();
}
}
队列
队列，是先进先出，在队尾进，在队头出
是接口，底层通过链表实现的，lterable<--collection<--queue
常用方法
用栈实现队列
入队列操作时间复杂度为O(1)
出队列操作的平均时间复杂度为 O(1)，最坏的是O（n）
class MyQueue {
Stack<Integer> s1;//输入栈
Stack<Integer> s2;//输出栈
public MyQueue() {//初始化
s1=new Stack<Integer>();
s2=new Stack<Integer>();
}
public void push(int x) {
s1.push(x);
}
public int pop() {
if(s2.isEmpty()){
while(!s1.isEmpty()){
s2.push(s1.pop());
}
}
return s2.pop();
}
public int peek() {
if(s2.isEmpty()){
while(!s1.isEmpty()){
s2.push(s1.pop());
}
}
return s2.peek();
}
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}
循环队列
循环队列可以充分使用所有空间
如何判满（标记队头队尾）
当q.head==q.tail时，队为空的
q.head+1=q.tail，队满
循环队列有效长度的通用公式
为(rear - front + N) % N。
当rear >= front时，(rear - front + N) % N = rear - front；
当rear < front时，(rear - front + N) % N = N - front + rear。
循环队列的实现
class MyCircularQueue {
int len;//长度
int h,t;//队首和队尾
int []arr;
public MyCircularQueue(int k) {
len=k;
arr=new int[k];//创建k个空间大小的数组
}
public boolean enQueue(int value) {//存入目标值
if(isFull())return false;
arr[t%len]=value;
t++;
return t>=0;
}
public boolean deQueue() { //弹出队列头部元素
if(isEmpty()){
return false;
}
h++;
return h>=0;
}
public int Front() { //返回队头元素
if( isEmpty())return -1;
return arr[h%len];
}
public int Rear() { //返回队尾元素
if(isEmpty())return -1;
return arr[(t-1)%len];
}
public boolean isEmpty() {
if(h==t)return true;
return false;
}
public boolean isFull() {
int nums=t-h;
if(nums==len)return true;
return false;
}
}
双端队列
双端队列（deque），允许两端进行入出队的操作，
双端队列是一个接口，使用时必须创建LinkedList的对象
