数据结构——顺序队

本篇文章主要是用做代码分享。代码，注释都写得很清楚，不清楚的可以问我，如果有些不对的地方也可以提出来，以便我及时改正。

接口类

//顺序队接口类
public interface ISeqQueue {
boolean isEmpty();  //判空
boolean isFull();   //判满
boolean enQueue(Object element);    //入队
    Object deQueue();   //出队
    Object peek();  //查看队头元素
int getSize();  //队列长度
void display(); //遍历输出
void clear();   //清空
}

顺序队类_有三种方法的类

// 采用留空一位置的方法实现的循环顺序队列
public class SeqQueue01 implements ISeqQueue{
final int MAX_SIZE = 50;
private Object data[];
private int front;
private int rear;

public SeqQueue01(int size) {   //构造长度为size的空队列
this.data = new Object[Math.abs(size)];
this.front = 0;
this.rear = 0;
    }

public SeqQueue01(int front, int rear) {    //默认队列容量为MAX_SIZE
        data = new Object[MAX_SIZE];
this.front = 0;
this.rear = 0;
    }

@Override
public boolean isEmpty() {
// 判空
return front == rear;
    }

@Override
public boolean isFull() {
// 当front==(rear+1)% value.length时，队列已满，此时value数组中仍有一个空位置。
return (rear+1) % data.length == front;
    }

@Override
public boolean enQueue(Object element) {
// 当队列不满时，将element对象存放在rear位置作为新的队尾数据元素，rear循环加1。此时入队的数据元素是Element对象
if(isFull() || element == null)
return false;
        data[rear] = element;
        rear = (rear+1) % data.length;
return true;
    }

@Override
public Object deQueue() {
// 当队列不空时，取走front位置上的队首数据元素，front循环加1，front位置上的数据元素成为新的队首数据元素。此时出队的数据元素是Object对象
if(isEmpty())
return null;
        Object temp = data[front];
        front = (front+1) % data.length;
return temp;
    }

@Override
public Object peek() {
// 查看队头元素
if(isEmpty())
return null;
return data[front];
    }

@Override
public int getSize() {
// 求队队列长度
return (rear-front+data.length)%data.length;
    }

@Override
public void display() {
// 遍历输出
for(int i = front; i != rear; i = (i+1)%data.length)
            System.out.print(data[i] + " ");
        System.out.println();
    }

@Override
public void clear() {
// 清空
        front = rear = 0;
    }

}

//顺序循环队列：采用计数器的方式来实现
public class SeqQueue02 implements ISeqQueue{
private int maxSize = 50;   //数组默认容量
private Object[] data;  //对象数组
private int front;  //对头指针
private int rear;   //队尾指针
private int count;  //计数器

public SeqQueue02() {   //构造空队列
super();
this.data = new Object[maxSize];
this.front = 0;
this.rear = 0;
this.count = 0;
    }

public SeqQueue02(int n){   //构造方法，指定队列容量为n
super();
this.data = new Object[n];
this.front = 0;
this.rear = 0;
this.maxSize = data.length;
    }

@Override
public boolean isEmpty() {
// 判空
return count == 0;
    }

@Override
public boolean isFull() {
// 判满
return count == maxSize;
    }

@Override
public boolean enQueue(Object element) {
// 入队
if(!isFull() && element != null){
            data[rear] = element;
            rear = (rear+1) % maxSize;
            count++;
return true;
        }else
return false;
    }

@Override
public Object deQueue() {
// 出队
if(!isEmpty()){
            Object temp = data[front];
            front = (front+1) % maxSize;
            count--;
return temp;
        }else
return null;
    }

@Override
public Object peek() {
// 查看对头元素
if(!isEmpty())
return data[front];
return null;
    }

@Override
public int getSize() {
// 求队列长度
return count;
    }

@Override
public void display() {
// 遍历输出
// for(int i = front; i != rear; i = (i+1)%data.length)
// System.out.print(data[i] + " ");
// System.out.println();

for(int i = 0; i < count; i++){
            System.out.print(data[front] + " ");
            front = (front+1) % data.length;
        }
        System.out.println();
    }

@Override
public void clear() {
// 清空
        front = rear = 0;
    }

}

// 采用标志法的循环队列
public class SeqQueue03 implements ISeqQueue{
private final int MAX_SIZE=50;//数组的默认容量
private Object[] data;//对象数组
private int front;//队头指针
private int rear;//队尾指针

//被标志的变量
private boolean empty = true;

//构造方法
public SeqQueue03() {   //构造空队列
        data = new Object[MAX_SIZE];
        front=0;
        rear=0;
    }
public SeqQueue03(int size){
        data = new Object[size];
        front = 0;
        rear = 0;
    }

public boolean isEmpty(){   //判断队列是否为空
return empty;
    }

public boolean isFull(){    //判断队列是否已满
return rear == front && !empty ;
    }

@Override
public boolean enQueue(Object element) {
// 入队
if(!isFull() && element != null){
            data[rear]= element;
            rear=(rear+1) % MAX_SIZE;
            empty = false;
return true;
        }else
return false;
    }

public Object deQueue(){    //出队
if(!isEmpty()){
            Object temp = data[front];
            front = (front+1) % MAX_SIZE;
if(front == rear)
                empty = true;
return temp;
        }else
return null;
    }
public Object peek(){//取队头元素
/*if(!isEmpty()){
 return value[front];
 }
 return null;*/
if(isEmpty())
return null;
return data[front];
    }
//查询队列长度
public int getSize(){
/*if(rear > front)
 return rear - front;
 else
 return rear - front + 5;
 */
return (rear-front+data.length) % data.length;
    }

@Override
public void display() {
// 遍历输出
for(int i = front; i != rear; i = (i+1)%data.length)
            System.out.print(data[i] + " ");
        System.out.println();
    }
@Override
public void clear() {
// 清空
        front = rear = 0;
    }
}

测试类

public class TestSeqQueue01 {
    public static void main(String[] args) {
//      ISeqQueue q = new SeqQueue01(5); //采用留空法
        ISeqQueue q = new SeqQueue02(5); //采用计数法
//      ISeqQueue q = new SeqQueue03(5); //采用标志法
        System.out.println(q.isEmpty());
        q.enQueue("a");
        q.enQueue("b");
        q.enQueue("c");
        q.enQueue("d");
        System.out.println(q.isFull());
        q.enQueue("e");
        System.out.println(q.isFull());
        System.out.println("出队："+q.deQueue());
        System.out.println("队列长度："+q.getSize());
        System.out.println("查看："+q.peek());
        System.out.println("队列长度："+q.getSize());
        System.out.println("出队："+q.deQueue());
        System.out.println("出队："+q.deQueue());
        System.out.println("出队："+q.deQueue());
        System.out.println(q.isEmpty());

    }
}

范例

public class Dancer {
private String name;
private int sex;    //0--男，1--女

public Dancer(String name, int sex) {
super();
this.name = name;
this.sex = sex;
    }

public Dancer(){
this.name = Name.getName(sex);
this.sex = (int)(Math.random()*2);
    }

public String getName() {
return name;
    }

public void setName(String name) {
this.name = name;
    }

public int getSex() {
return sex;
    }

public void setSex(int sex) {
this.sex = sex;
    }

@Override
public String toString() {
return name;
    }   
}

范例测试类

import java.util.Scanner;

public class TestSeqQueue02 {
    public static void main(String[] args) {
    Scanner input =new Scanner(System.in);
    System.out.println("请输入总人数:");
    int n = input.nextInt();

    SeqQueue01 qboys = new SeqQueue01(n+1);
    SeqQueue01 qgirls = new SeqQueue01(n+1);

    for(int i = 0;i < n;i++){
        Dancer d = new Dancer();//随机生成一个来宾
        if(d.getSex()==0)
            qboys.enQueue(d);
        else
            qgirls.enQueue(d);
    }

    System.out.println("男队人数:"+qboys.getSize()+"女队人数:"+qgirls.getSize());
    qboys.display();
    qgirls.display();

    while(!qboys.isEmpty() && !qgirls.isEmpty())
        System.out.println(qboys.deQueue()+"-----"+qgirls.deQueue());

    if(!qboys.isEmpty())
        System.out.println("男队剩:"+qboys.getSize()+" 第一个是:"+qboys.peek());

    if(!qgirls.isEmpty())
        System.out.println("女队剩:"+qgirls.getSize()+" 第一个是:"+qgirls.peek());

    }   
}