本文主要是介绍Java的栈与队列实现代码解析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J...
栈的概念（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 intjs pop() throws RuntimeException { try { if (empty()) { throw neChina编程w 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];
}
pu编程blic 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;
}
}用队列实现栈
因为队列是先进先出的，而我们的栈是先进后出的，两种线性结构的关系是颠倒的，一个队列是不能完成的，我们需要两个队列互相工作来完成
辅助队列先获取数值，保证辅助队列是最后一个拿到值的，然后将主队列的值给到辅助队列，在交换两个队列的数值，因为队列关系先进先出，每一次最后一个值就是队列先出的数值
主队列不为空，将主队列的元素都poll出放到辅助栈中，使用一个tmp来将主队列（这里主队列已经遍历完）和辅助队列交换
Queue<Integer> q1;//主队列
Queue<Integer> q2;//辅助队列
public MyStack() {
q1=new LinkedList<>();//构造方法
q2=new LinkedList<>();
}
public void push(int x) {
q2.offer(x);
while(!q1.isEmpty()){//主队列不为空，则将主队列出列给到辅助队列
q2.offer(q1.poll());
}
//走到这里主队列是为空
Queue tmp=q1;
q1=q2;
q2=tmp;
//将两个队列交换
}
public int pop() {
return q1.poll();
}
public int top() {
return q1.peek();
}
public boolean empty() {
return q1.isEmpty();
}
}用栈来实现队列
栈来实现队列，栈是先进后出的顺序，而队列是先进先出的顺序
将push都放到a栈中当我们peek或者是要删除的时候，我们都将a栈的元素pop给b栈，这样b栈已经有了我们的元素
但是我们还需要考虑的是丢掉元素后如果在一起添加元素到a栈呢，这里我们给一个条件，如果b的栈不为空时，我们仍然用b栈的队列
如果a为空，这两个栈都是空的说明没有元素直接返回-1，如果a不为空的话且b没有新的元素b继续捕获新的a栈中所有的元素
class MyQueue {
Stack<Integer> A;
Stack<Integer> B;
public MyQueue() {
A=new Stack<>();
B=new Stack<>();
}
publwww.chinasem.cnic void push(int x) {
A.push(x);
}
public int pop() {
int check=peek();
China编程 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都为空才为空
}
}总结
栈分为栈顶和栈底，最先进的为栈底，最后进的为栈顶。
队列分为队头和队尾，最先进的为队头，最后进的为队尾。
到此这篇关于Java的栈与队列实现代码解析的文章就介绍到这了,更多相关java栈和队列内容请搜索编程China编程(www.chinasem.cn)以前的文章或继续浏览下面的相关文章希望大家以后多多支持China编程(www.chinasem.cn)！
这篇关于Java的栈与队列实现代码解析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
