代码实现如下:
- package com.wjy.Data_Structure.queue;
- public interface Queue {
- /**
- * 返回队列的大小
- *
- * @return
- */
- public int getSize();
- /**
- * 判断队列是否为空
- *
- * @return
- */
- public boolean isEmpty();
- /**
- * 数据元素 e 入队
- *
- * @param e
- */
- public void enqueue(Object e);
- /**
- * 队首元素出队
- *
- * @return
- */
- public Object dequeue() throws QueueEmptyException;
- /**
- * 取队首元素
- *
- * @return
- */
- public Object peek() throws QueueEmptyException;
- }
异常类定义
- package com.wjy.Data_Structure.queue;
- public class QueueEmptyException extends RuntimeException {
- private static final long serialVersionUID = 1L;
- public QueueEmptyException(String err) {
- super(err);
- }
- }
代码实现如下:
- package com.wjy.Data_Structure.queue;
- public class QueueArray implements Queue {
- private static final int CAP = 7; // 队列默认大小
- private Object[] elements; // 数据元素数组
- private int capacity; // 数组的大小
- private int front; // 队首指针,指向队首
- private int rear; // 队尾指针,指向队尾后一个位置
- public QueueArray() {
- this(CAP);
- }
- public QueueArray(int cap) {
- capacity = cap + 1;
- elements = new Object[capacity];
- front = rear = 0;
- }
- private void expandSpace() {
- Object[] a = new Object[elements.length * 2];
- int i = front, j = 0;
- while (i != rear) {
- a[j++] = elements[i];
- i = (i + 1) % capacity;
- }
- elements = a;
- capacity = elements.length;
- front = 0;
- rear = j;
- }
- @Override
- public int getSize() {
- return (rear - front + capacity) % capacity;
- }
- @Override
- public boolean isEmpty() {
- return front == rear;
- }
- @Override
- public void enqueue(Object e) {
- if (getSize() == capacity - 1)
- expandSpace();
- elements[rear] = e;
- rear = (rear + 1) % capacity;
- }
- @Override
- public Object dequeue() throws QueueEmptyException {
- if (isEmpty())
- throw new QueueEmptyException("错误:队列为空");
- Object obj = elements[front];
- elements[front] = null;
- front = (front + 1) % capacity;
- return obj;
- }
- @Override
- public Object peek() throws QueueEmptyException {
- if (isEmpty())
- throw new QueueEmptyException("错误:队列为空");
- return elements[front];
- }
- }
代码实现如下:
- package com.wjy.Data_Structure.queue;
- import com.wjy.Data_Structure.linearlist.common.SLNode;
- public class QueueSLinked implements Queue {
- private SLNode front; // 队首指针
- private SLNode rear; // 队尾指针
- private int size; // 元素个数
- public QueueSLinked() {
- this.front = new SLNode();
- this.rear = front;
- this.size = 0;
- }
- @Override
- public int getSize() {
- return size;
- }
- @Override
- public boolean isEmpty() {
- return size == 0;
- }
- @Override
- public void enqueue(Object e) {
- SLNode p = new SLNode(e, null);
- rear.setNext(p);
- rear = p;
- size++;
- }
- @Override
- public Object dequeue() throws QueueEmptyException {
- if (size < 1)
- throw new QueueEmptyException("错误:队列为空");
- SLNode p = front.getNext();
- front.setNext(p.getNext());
- size--;
- if (size < 1)
- rear = front; // 如果队列为空,rear指向头结点
- return p.getData();
- }
- @Override
- public Object peek() throws QueueEmptyException {
- if (size < 1)
- throw new QueueEmptyException("错误:队列为空");
- return front.getNext().getData();
- }
- }
来源: