栈的概念（Stack）
栈是常见的线性数据结构，栈的特点是以先进后出的形式，后进先出，先进后出，分为栈底和栈顶
栈应用于内存的分配，表达式求值，存储临时的数据和方法的调用等。
例如这把枪，第一发子弹是最后发射的，第一发子弹在栈底，而最新安装上去的子弹在栈的顶部，只有将上面的子弹打完（栈顶的数据走完），最后一发子弹才会射出。
栈的实现
栈的实现是基于简单的数组形成的，我们可以将它想象成连续的数组，而栈的顺序是由后放到前放
模拟实现栈的方法:push（放入一个元素到栈中)
pop(提取栈顶的一个元素，并将在其栈中消除)
peek(查看栈顶的元素)
size(查看栈中的大小)
empty(栈中是否为空)
full(栈是否满了)
import java.util.Arrays;
public class MyStack implements IStack {
private int[] elem;
private int top;//数组的栈顶,以及数组栈中存放元素的数量
private static final int DEFAULT_CAPACITY = 10;//这里是初始容量
public MyStack() {
elem = new int[DEFAULT_CAPACITY];
top = -1;//数组下标从0开始
}
@Override
public void push(int item) {
if (full()) {
//如果满了就扩容
elem = Arrays.copyOf(elem, 2 * elem.length);
}
elem[++top] = item;
}
@Override
public int pop() throws RuntimeException {
try {
if (empty()) {
throw new RuntimeException("栈为空");
}
} catch (RuntimeException e) {
e.printStackTrace();
}
return elem[top--];//return返回后删除栈顶的元素
}
@Override
public int peek() {
if (empty()) {
throw new RuntimeException("栈为空");
}
return elem[top];//返回栈顶元素
}
@Override
public int size() {
return top+1;//去除数组0
}
@Override
public boolean empty() {
return top == -1;
}
@Override
public boolean full() {
return top == elem.length;//count==当前的elem的总长度为true
}
}
队列（Queue）
队列是由先进先出的线性数据结构，采用的是先进先出，后进后出，如果要插入元素的话就是从入队尾巴方向插入，而删除作为出队要在头尾删除。
队列的方法
模拟实现队列(双链表实现)
public class MyQueue implements IQueue{
static class Queue{
public int elem;
public Queue next;
public Queue prev;
public Queue(int elem) {
this.elem = elem;
}
}
public Queue head;
public Queue last;
public int size=0;
@Override
public void offer(int val) {
Queue queue = new Queue(val);
if (this.head == null) {
this.head = queue;
this.last = queue;
++size;
return;
}
this.last.next=queue;
this.last.prev=this.head;
this.last=last.next;
++size;
}
@Override
public int poll() {
if(this.head==null){
throw new RuntimeException("没有要丢掉的队列");
}
Queue cur =this.head;
if(this.head.next==null){
return -1;
}
this.head=this.head.next;
this.head.prev=null;
size--;
return cur.elem;
}
@Override
public int peek() {
if(this.head!=null){
return this.head.elem;
}
return 0;
}
@Override
public int size() {
return size;
}
}
循环队列（循环数组实现）
数组实现队列的循环需要引入一个公式（目前的下标值+1）%当前数组的长度
(index+1)%array.length,下标值从0开始少一个数，当index+1就是当前的总长度时，公式后的值一定为下标0。
private int[] array;
private int front;
private int rear;
public MyCircularQueue(int k) {
array=new int[k+1];
front=0;//初始位置
rear=0;
}
public boolean enQueue(int value) {
//入列
if(isFull()){
//这里如果容量已经满了，需要先删除后在进行插入
return false;
}
array[rear]=value;//rear下标获取元素
rear=(rear+1)%array.length;//rear最终循环为0下标
return true;
}
public boolean deQueue() {
//出列
if(isEmpty()){
//为空返回false
return false;
}
front=(front+1)%array.length;//front只需要往后走
return true;
}
public int Front() {
if(isEmpty()){
return -1;
}
return array[front];
}
public int Rear() {
if(isEmpty()){
return -1;
}
//这里三木操作符判断是否为0如果为0，将rear回退到最后一个位置，不为0则-1
int temp = (rear==0)?array.length-1:rear-1;
return array[temp];
}
public boolean isEmpty() {
return front==rear;
}
public boolean isFull() {
return (rear+1)%array.length==front;
}
}
用栈来实现队列
栈来实现队列，栈是先进后出的顺序，而队列是先进先出的顺序
将push都放到a栈中当我们peek或者是要删除的时候，我们都将a栈的元素pop给b栈，这样b栈已经有了我们的元素
但是我们还需要考虑的是丢掉元素后如果在一起添加元素到a栈呢，这里我们给一个条件，如果b的栈不为空时，我们仍然用b栈的队列
如果a为空，这两个栈都是空的说明没有元素直接返回-1，如果a不为空的话且b没有新的元素b继续捕获新的a栈中所有的元素
class MyQueue {
StackA;
StackB;
public MyQueue() {
A=new Stack<>();
B=new Stack<>();
}
public void push(int x) {
A.push(x);
}
public int pop() {
int check=peek();
B.pop();
return check;
}
public int peek() {
//先判断b是否是空的，如果不是空的直接返回，是空才可以往下走
if(!B.isEmpty())return B.peek();
//因为b还不是空的，所以不需要将a栈放到b中
if(A.isEmpty())return -1;
while(!A.isEmpty()){
B.push(A.pop());//将所有的a放到b中
}
return B.peek();
}
public boolean empty() {
return A.isEmpty()&&B.isEmpty();
//a和b都为空才为空
}
}
总结
栈分为栈顶和栈底，最先进的为栈底，最后进的为栈顶。
队列分为队头和队尾，最先进的为队头，最后进的为队尾。
————————————————
原文链接：https://blog.csdn.net/weixin_60489641/article/details/143723419
换一换
