我要评论一、队列的介绍
队列是一种常见的线性数据结构，遵循先进先出（fifo，first in first out）原则。也就是说，最先进入队列的元素会最先被移除。
从结构上看，队列通常包含两个重要指针：队头（front）和队尾（rear）。新元素总是从队尾进入队列，这个操作称为入队（enqueue）；而元素的删除只发生在队头，这个操作称为出队（dequeue）。
根据实现方式不同，队列主要有两种常见形式。第一种是顺序队列，基于数组实现，优点是结构简单、访问速度快，但容易出现“假溢出”问题，因此常配合循环队列优化使用。第二种是链式队列，基于链表实现，入队和出队都比较灵活，不容易出现容量浪费，但需要额外的指针空间。
二、循环队列的实现
public class mycircularqueue {
public int[] elem;
public int front;
public int rear;
public mycircularqueue(int k){
elem=new int[k+1];
}
public boolean enqueue(int val){
if(isfull()){
return false;
}
elem[rear]=val;
rear=(rear+1)%elem.length;
return true;
}
public boolean dequeue(){
if(isempty()){
return false;
}
front=(front+1)%elem.length;
return true;
}
public int front(){
if(isempty()){
return -1;
}
return elem[front];
}
public int rear(){
if(isempty()){
return -1;
}
int index=(rear==0)?elem.length-1:rear-1;
return elem[index];
}
public boolean isempty(){
return front==rear;
}
public boolean isfull(){
return (rear+1)%elem.length==front;
}
} 构造函数 mycircularqueue(int k) 的作用是初始化循环队列。这里创建了一个长度为 k+1 的数组，而不是 k。多出来的一个空间用于区分队列的“空”和“满”两种状态，否则仅靠 front == rear 无法判断。此时 front 和 rear 默认都为 0，表示队列为空。
enqueue(int val) 用于入队操作。首先判断队列是否已满，如果满了直接返回 false 表示入队失败。如果还有空间，就把新元素放入 rear 所指的位置，然后通过 (rear + 1) % elem.length 让队尾指针向后移动一位，并在到达数组末尾时自动回绕到开头，实现“循环”的效果。操作成功返回 true。
dequeue() 方法用于出队操作。它先调用 isempty() 判断队列是否为空，如果为空则返回 false。如果队列中有元素，并不会真正删除数组中的值，而是通过移动 front 指针来“跳过”原队头元素，即 front = (front + 1) % elem.length。
front() 方法用于获取队头元素但不删除。函数先判断队列是否为空，如果为空返回 -1；否则直接返回 elem[front]。
rear() 方法用于获取队尾元素。这里有一个容易出错的细节：rear 指针并不是指向最后一个元素，而是指向“队尾的下一个位置”。因此真正的队尾下标需要往前退一位。如果 rear == 0，说明队尾元素在数组最后一个位置；否则就是 rear - 1。计算出正确下标后返回对应元素。
isempty() 方法用于判断队列是否为空。判断条件是 front == rear。在这种循环队列设计中，只要两个指针重合，就说明当前没有有效元素。
isfull() 方法用于判断队列是否已满。判断条件是 (rear + 1) % elem.length == front，意思是如果队尾指针再向前移动一步就会追上队头，那么队列就满了。
三、链式队列的实现
import java.util.*;
public class mylinkqueue {
static class listnode{
public int val;
public listnode next;
public listnode prev;
public listnode(int val){
this.val=val;
}
}
public listnode head;
public listnode last;
public int usedsize;
public boolean offer(int val){
listnode node=new listnode(val);
if(head==null){
head=node;
last=node;
}else{
last.next=node;
node.prev=last;
last=last.next;
}
usedsize++;
return true;
}
public int poll(){
if(head==null){
return -1;
}
int retval=head.val;
if(head.next==null){
head=head.next;
head.prev=null;
return retval;
}
head=head.next;
head.prev=null;
usedsize--;
return retval;
}
public int peek(){
if(head==null){
return -1;
}
return head.val;
}
public boolean empty(){
return head==null;
}
public int size(){
return usedsize;
}
} 构造的内部类 listnode 是链式队列的节点结构。每个节点包含三个部分：val 用来存储数据，next 指向后继节点，prev 指向前驱节点。。
offer(int val) 方法用于入队操作。函数首先创建一个新节点，如果当前队列为空（即 head == null），说明这是第一个元素，此时需要同时让 head 和 last 都指向该节点。如果队列不为空，就把新节点接到当前队尾：先让原队尾的 next 指向新节点，再让新节点的 prev 指向原队尾，最后更新 last 指向新的尾节点。入队成功后，usedsize 自增并返回 true。
poll() 方法用于出队操作。函数先判断队列是否为空，如果为空直接返回 -1。否则先保存当前队头的值用于返回。接下来分情况处理：如果队列只有一个节点（head.next == null），把 head 和 last 都置为 null 表示队列清空；如果不止一个节点，则把 head 向后移动一位，并把新队头的 prev 置为 null，同时 usedsize--。最后返回原队头元素。
peek() 方法用于查看队头元素但不出队。函数先判断队列是否为空，如果为空返回 -1；否则直接返回 head.val。
empty() 方法用于判断队列是否为空。实现方式很直接，只要判断 head == null 即可。如果头节点不存在，说明队列中没有任何元素。
size() 方法用于返回当前队列中的有效元素个数。这里直接返回成员变量 usedsize。
四、使用栈实现队列
import java.util.*;
public class myqueue {
private stack<integer> s1;
private stack<integer> s2;
public myqueue(){
s1=new stack<>();
s2=new stack<>();
}
public void push(int x){
s1.push(x);
}
public int pop(){
if(empty()){
return -1;
}
if(s2.empty()){
while(!s1.empty()){
s2.push(s1.pop());
}
}
return s2.pop();
}
public int peek() {
if(empty()) {
return -1;
}
if(s2.empty()) {
while (!s1.empty()) {
s2.push(s1.pop());
}
}
return s2.peek();
}
public boolean empty(){
return s1.empty()&&s2.empty();
}
} 构造函数 myqueue() 的作用是初始化两个栈：s1 和 s2。其中，s1 作为输入栈，负责接收所有新入队的元素；s2 作为输出栈，负责出队和读取队头元素。通过两个栈之间的元素搬运，可以把栈的后进先出（lifo）特性转换成队列的先进先出（fifo）行为，这是本实现的核心思想。
push(int x) 方法用于入队操作。只需把元素压入输入栈 s1。这里没有立即调整顺序，而是把顺序反转的工作留到出队或取队头时再做。这样可以保证入队操作始终是 o(1) 时间复杂度，提高整体效率。
pop() 方法用于出队操作。函数首先调用 empty() 判断队列是否为空，如果为空返回 -1。否则检查输出栈 s2 是否为空：如果为空，就把输入栈 s1 中的所有元素依次弹出并压入 s2。这一过程会把元素顺序完全反转，使得最早进入队列的元素来到 s2 的栈顶。完成搬运后，直接从 s2 弹出并返回栈顶元素，即完成一次出队。
peek() 方法用于获取队头元素但不删除。逻辑与 pop() 基本一致：先判空，如果队列为空返回 -1；否则当 s2 为空时，把 s1 中的元素全部搬运到 s2，保证队头元素位于 s2 栈顶。不同之处在于这里调用的是 s2.peek()，只读取不弹出，因此不会改变队列中的元素个数。
empty() 方法用于判断队列是否为空。实现方式是同时检查两个栈：只有当 s1 和 s2 都为空时，队列才为空。
五、使用队列实现栈
import java.util.*;
public class mystack {
private queue<integer> qu1;
private queue<integer> qu2;
public mystack(){
qu1=new linkedlist<>();
qu2=new linkedlist<>();
}
public void push(int x){
if(!qu1.isempty()){
qu1.offer(x);
}else if(!qu2.isempty()){
qu2.offer(x);
}else{
qu1.offer(x);
}
}
public int pop(){
if(empty()){
return -1;
}
if(!qu1.isempty()){
int size=qu1.size();
for(int i=0;i<size-1;i++){
int x=qu1.poll();
qu2.offer(x);
}
return qu1.poll();
}else{
int size=qu2.size();
for(int i=0;i<size-1;i++){
int x=qu2.poll();
qu1.offer(x);
}
return qu2.poll();
}
}
public int top(){
if(empty()){
return -1;
}
if(!qu1.isempty()){
int size=qu1.size();
int x=-1;
for(int i=0;i<size;i++){
x=qu1.poll();
qu2.offer(x);
}
return x;
}else{
int size=qu2.size();
int x=-1;
for(int i=0;i<size;i++){
x=qu2.poll();
qu1.offer(x);
}
return x;
}
}
public boolean empty(){
return qu1.isempty()&&qu2.isempty();
}
} 构造函数 mystack() 的作用是初始化两个队列 qu1 和 qu2。这两个队列交替充当“数据队列”和“辅助队列”。由于队列本身是先进先出（fifo），而栈需要后进先出（lifo），因此必须借助队列之间的元素搬运来实现顺序反转。
push(int x) 方法用于入栈操作。实现策略是：始终把新元素加入当前非空的那个队列中。如果 qu1 不为空，就加入 qu1；否则如果 qu2 不为空，就加入 qu2；如果两个队列都为空（说明是第一个元素），默认加入 qu1。这样可以保证任意时刻只有一个队列存放有效数据，另一个作为辅助队列备用。
pop() 方法用于出栈操作。函数首先通过 empty() 判断栈是否为空，如果为空返回 -1。否则找到当前存有数据的队列，然后把其中前 size-1 个元素依次出队并加入另一个队列，只留下最后一个元素。这个最后留下的元素就是“栈顶元素”，直接出队返回即可。
top() 方法用于获取栈顶元素但不删除。实现思路与 pop() 类似，但有一个关键区别：需要把所有元素都搬运走，并记录最后一个被搬运的元素值作为栈顶。因为不能真正删除元素，所以最后一个元素也要放入辅助队列中。函数中用变量 x 保存每次出队的值，循环结束后 x 就是原栈顶元素。
empty() 方法用于判断栈是否为空。实现方式是同时检查两个队列：只有当 qu1 和 qu2 都为空时，栈才为空。
到此这篇关于java实现循环队列、栈实现队列、队列实现栈的方法的文章就介绍到这了,更多相关java循环队列内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！
发表评论