数据结构——队列（Java实现）

水深无声 2022-07-14 00:28 220阅读 0赞

编程实现对循环链队列的入队和出队操作。

⑴根据输入的队列长度n和各元素值建立一个带头结点的循环链表表示的队列（循环链队列），并且只设一个尾指针来指向尾结点，然后输出队列中各元素值。

⑵将数据元素e入队，并输出入队后的队列中各元素值。

⑶将循环链队列的队首元素出队，并输出出队元素的值和出队后队列中各元素值。

public class CircleLinkQueue {
    	private Node front;
    	private Node rear;// 循环链队列的尾指针
    
    	// 构造方法
    	public CircleLinkQueue() {// 构造一个带头结点的空循环链队列
    		rear = new Node(); // 初始化头结点并用尾指针指向它
    		rear.setNext(rear);
    		front=rear;
    	}
    
    	public void offer(Object x) { // 将指定的元素x插入到带头结点的循环链队列中
    		Node p = new Node(x); // 生成新结点
    		p.setNext(rear.getNext());// 插入链队列的尾部
    		rear.setNext(p);
    		rear = p;
    	}
    
    	public Object poll() {
    		// 移除带头结点的循环链队列中的队首元素并返回其值，如果此队列为空，则返回 null
    		if (rear.getNext() == rear) // 队列为空
    			return null;
    		else {
    			Node p = rear.getNext().getNext();// p指向待删除的队首结点
    			if (p == rear) {// 被删结点是即是队首结点，又是队尾结点
    				rear = rear.getNext();
    				rear.setNext(rear); // 删除队首结点后，链队列变成了空循环链队列
    			} else
    				rear.getNext().setNext(p.getNext());// 删除队首结点
    			return p.getData();
    		}
    	}
    	public void display() throws Exception{
    		Node p=front.getNext();
    		if(rear==front)
    			throw new Exception("队列为空！");
    		while(p!=front){
    			System.out.print(p.getData() + " ");
    			p=p.getNext();
    		}
    		System.out.println();
    		
    		
    	}
    
    }
    
    
    public class LinkedQueueList {
    	public static void main(String[] args) throws Exception{
    		CircleLinkQueue C=new CircleLinkQueue();
    		System.out.println("入队之后");
    		C.offer(1);
    		C.offer(2);
    		C.offer(3);
    		C.display();
    		System.out.println("增加一个4");
    		C.offer(4);
    		C.display();
    		System.out.println("出列");
    		C.poll();
    		C.display();
    	}
    }

运行结果：

![Center][]

[Center]: /images/20220714/f4cb380d12f54ceda8fd8d1297f63e9f.png