循环队列(数据结构实训)

题目：

标准输入输出
题目描述：
根据给定的空间构造顺序循环队列，规定队满处理方法为少用一个元素空间。例如，给定5个元素空间构造循环队列，则只能存放4个元素。试根据入队及出队操作判断队列最后的元素存放情况，并输出最后队列中的元素值，即完成给定入队及出列操作后一次性全部出队的元素值。要求采用顺序队列完成。
输入：
输入的第一行为一个自然数n，表示要求构造的顺序循环队列空间数。第二行为操作次k，接下来k行为出队入队操作，每行各代表一次操作。入队用in表示，出队用out表示，如果是入队，则in隔一空格后为一整数，表示入队元素值。

输出：
输出完成所有入队出队操作后，一次性出队元素。用一个空格隔开。可以假定队在完成所有操作后不为空。

输入样例：
4
7
in 1
in 2
in 5
in 6
out
out
in 8

输出样例：
5 8

代码：

方法一(模拟队列)：

import java.util.*;

public class Xingyuxingxi {

    public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
	int a;
	a=sc.nextInt();
	int b=sc.nextInt();
	int []g=new int[a+1];//下标从1开始使用
	int n=0;
	int m=0;
	while(b--!=0)
	{
		String c=sc.next();
		if(c.equals("in"))
		{
			int d=sc.nextInt();
			if(n<a-1)//题目所储存的元素比空间少1
			{
				g[++n]=d;
				if(m==a-1)//如果删除元素下标到达最大储存下标则从头开始删除
				{
					m=0;
				}
			}
		}
		else
		{
			g[++m]=-1;//被删除的元素用-1表示
			if(n==a-1)//如果添加元素的下标到达最大储存下标则从头开始添加
			{
				n=0;
			}
		}
	}
		if(m==0)m++;
        //要求按入队顺序输出
		for (int i = m+1; i < a; i++) {//删除下标后面的元素即为先入队的
			System.out.print(g[i]+" ");
		}
		for (int i = 1; i <=m; i++) {//添加下标后面的元素即为后入队的
			if(g[i]!=-1)
			{
				System.out.print(g[i]+" ");
			}
		}
    }
}

方法二(队列)：

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Xingyuxingxi {
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        int a=sc.nextInt();
        Queue<Integer>dui = new ArrayDeque<Integer>();
        int b= sc.nextInt();
        while(b--!=0)
        {
            String c=sc.next();
            if(c.equals("in"))
            {
                int d=sc.nextInt();
                if(dui.size()<a-1)
                {
                    dui.add(d);
                }
            }
            else
            {
                dui.poll();
            }
        }
        Object []x= dui.toArray();
        for (int i = 0; i < dui.size(); i++) {
            System.out.print(x[i]+" ");
        }
    }
}
/*
创建一个队列

这里使用实现类ArrayDeque
size()方法，返回队列长度
add()方法，将指定元素插入此队列的末尾。
poll()方法，删除队头元素，并获取该元素
toArray()方法，按顺序返回元素

以下为java1.6版本的Queue实现类
AbstractQueue,ArrayBlockingQueue,ArrayDeque,ConcurrentLinkedQueue,DelayQueue,LinkedBlockingDeque,LinkedBlockingQueue,LinkedList,PriorityBlockingQueue,PriorityQueue,SynchronousQueue

以下为java1.8版本的Queue实现类
AbstractQueue,ArrayBlockingQueue,ArrayDeque,ConcurrentLinkedDeque,ConcurrentLinkedQueue,DelayQueue,LinkedBlockingDeque,LinkedBlockingQueue,LinkedList,LinkedTransferQueue,PriorityBlockingQueue,PriorityQueue,SynchronousQueue
*/