燕山楠的Homework 2

数据结构 JAVA

T1（核心是$main$函数）

本题代码为T1代码。核心代码为$main$函数。

import java.util.Scanner;
public class hw3_1
{
  public static class SqStack<Integer>
  {
    final int initcap=100;
    int cap;
    int[] data;
    int top;
    public SqStack()
    {
      cap=initcap;
      data=new int[initcap];
      top=-1;
    }
    public void updcap(int newcap)
    {
      cap=newcap;
      int[] newdata=new int[newcap];
      for(int i=0;i<=top;i++)
        newdata[i]=data[i];
      data=newdata;
    }
    public boolean empty()
    {
      return top==-1;
    }
    public void push(int x)
    {
      if(top==cap-1)
        updcap(cap<<1);
      top++;
      data[top]=x;
    }
    public int pop()
    {
      if(empty())
        throw new IllegalArgumentException("The stack is empty.\nstr is not legal!!!");
      int x=data[top];
      top--;
      if(cap>initcap&&top+1==cap/4)
        updcap(cap/2);
      return x;
    }
  }
  public static void main(String args[])
  /*函数思路：模拟题目中提到的操作。
              终端输入一个字符串，然后遍历该字符串。初始化一个空栈。
              若扫到“I”，则将1入栈；若扫到“0”，则将栈顶元素出栈（如果无元素可供出栈，直接报错并输出not legal）
              最后判断若栈非空，也输出not legal；否则输出legal。   、
*/
  {
    Scanner in=new Scanner(System.in);
    String s=in.nextLine();
    SqStack Q=new SqStack<Integer>();
    for(int i=0;i<s.length();i++)
      if(s.charAt(i)=='I') Q.push(1);
        else Q.pop();
    if(Q.empty()) System.out.println("str is legal!");
    else System.out.println("The stack is not empty in the end.\nstr is not legal!!!");
  }
}

T2（核心是$main$函数）

本题代码为T2代码。核心代码为$main$函数。

import java.util.Scanner;
public class hw3_2
{
  public static class SqStack<Integer>
  {
    final int initcap=100;
    int cap;
    int[] data;
    int top;
    public SqStack()
    {
      cap=initcap;
      data=new int[initcap];
      top=-1;
    }
    public void updcap(int newcap)
    {
      cap=newcap;
      int[] newdata=new int[newcap];
      for(int i=0;i<=top;i++)
        newdata[i]=data[i];
      data=newdata;
    }
    public boolean empty()
    {
      return top==-1;
    }
    public void push(int x)
    {
      if(top==cap-1)
        updcap(cap<<1);
      top++;
      data[top]=x;
    }
    public int pop()
    {
      if(empty())
        throw new IllegalArgumentException("The stack is empty.\nstr is not legal!!!");
      int x=data[top];
      top--;
      if(cap>initcap&&top+1==cap/4)
        updcap(cap/2);
      return x;
    }
  }
  public static void main(String args[])
  /*函数思路：先特判@是否在字符串正中间，若不在，显然可以直接判不合法并return。
              再把@前的字符按顺序入栈。
              然后依次出栈，并将出栈字符与序列中对应字符相比较，若有不同则不合法并return。
              若到最后都没问题则合法。
  */
  {
    Scanner in=new Scanner(System.in);
    String s=in.nextLine();
    int len=s.length();
    if(s.charAt(len/2)!='@') 
    {
      System.out.println("Not legal!!!");
      return;
    }
    SqStack Q=new SqStack<Integer>();
    for(int i=0;i<len/2;i++)
      Q.push(s.charAt(i));
    for(int i=len/2+1;i<len;i++)
      if(Q.pop()!=s.charAt(i))
      {
        System.out.println("Not legal!!!");
        return;
      }
    System.out.println("Legal!");
  }
}

T3（核心是$main$函数）

本题代码为T3代码。核心代码为$main$函数。

输入的第一行是初始队列里元素个数。
输入的第二行是初始队列里的元素。

import java.util.Scanner;
public class hw3_3
{
  public static class SqStack<Integer>
  {
    final int initcap=100;
    int cap;
    int[] data;
    int top;
    public SqStack()
    {
      cap=initcap;
      data=new int[initcap];
      top=-1;
    }
    public void updcap(int newcap)
    {
      cap=newcap;
      int[] newdata=new int[newcap];
      for(int i=0;i<=top;i++)
        newdata[i]=data[i];
      data=newdata;
    }
    public boolean empty()
    {
      return top==-1;
    }
    public void push(int x)
    {
      if(top==cap-1)
        updcap(cap<<1);
      top++;
      data[top]=x;
    }
    public int pop()
    {
      if(empty())
        throw new IllegalArgumentException("The stack is empty.\nstr is not legal!!!");
      int x=data[top];
      top--;
      if(cap>initcap&&top+1==cap/4)
        updcap(cap/2);
      return x;
    }
  }
  public static class CSqQueue<Integer>
  {
    final int mxsize=100;
    int[] data;
    int front,tail;
    public CSqQueue()
    {
      data=new int[mxsize];
      front=tail=0;
    }
    public boolean empty()
    {
      return front==tail;
    }
    public void push(int x)
    {
      if((tail+1)%mxsize==front) 
        throw new IllegalArgumentException("The queue is full!!!");
      tail=(tail+1)%mxsize;
      data[tail]=x;
    }
    public int pop()
    {
      if(empty())
        throw new IllegalArgumentException("The queue is empty!!!");
      front=(front+1)%mxsize;
      return data[front];
    }
  }
  public static void main(String args[])
  /*函数思路：先用输入的数据创建初始队列Q（循环队列）。
              然后依次将Q中元素出队并入栈S。
              当出队完成后再一一将栈中元素出栈并入队,同时输出。
              （栈在过程中起到逆序的作用）
   */
  {
    Scanner in=new Scanner(System.in);
    CSqQueue Q=new CSqQueue<Integer>();
    SqStack S=new SqStack<Integer>();
    int n=in.nextInt();
    for(int i=0;i<n;i++)
    {
      int x=in.nextInt();
      Q.push(x);
    }
    for(int i=0;i<n;i++)
      S.push(Q.pop());
    System.out.print("The new queue:");
    for(int i=0;i<n;i++)
    {
      int x=S.pop();
      Q.push(x);
      System.out.print(x+" ");
    }
    System.out.println();
  }
}

T4（核心是$main$函数）

本题代码为T4代码。核心代码为$main$函数。

输入的第一行是原数组里元素个数。
输入的第二行是原数组的元素。

import java.util.Scanner;
public class hw3_4
{
  public static class CSqQueue<Integer>
  {
    final int mxsize=100;
    int[] data;
    int front,tail;
    public CSqQueue()
    {
      data=new int[mxsize];
      front=tail=0;
    }
    public boolean empty()
    {
      return front==tail;
    }
    public void push(int x)
    {
      if((tail+1)%mxsize==front) 
        throw new IllegalArgumentException("The queue is full!!!");
      tail=(tail+1)%mxsize;
      data[tail]=x;
    }
    public int pop()
    {
      if(empty())
        throw new IllegalArgumentException("The queue is empty!!!");
      front=(front+1)%mxsize;
      return data[front];
    }
  }
  public static void main(String args[])
  /*函数思路：先建立两个循环队列：用来存偶数的队列Q2和用来存奇数的队列Q1。
              然后把输入数据中的奇数位入队Q1，偶数位入队Q2。
              再将Q1里的元素一一出队Q1并入队Q2。
              最后Q2即为题目所求。
  */
  {
    Scanner in=new Scanner(System.in);
    CSqQueue Q1=new CSqQueue<Integer>(),Q2=new CSqQueue<Integer>();
    int n=in.nextInt();
    for(int i=0;i<n;i++)
    {
      int x=in.nextInt();
      if(i%2==0) Q1.push(x);
      else Q2.push(x);//修改了这个判断语句
    }
    while(!Q1.empty())
    {
      Q2.push(Q1.pop());
    }
    System.out.print("The new queue:");
    for(int i=0;i<n;i++)
      System.out.print(Q2.pop()+" ");
    System.out.println();
  }
}

T5

本题代码为T5代码。

输入的第一行是队列里元素个数。
输入的第二行是队列里的元素。

import java.util.Scanner;
public class hw3_5
{
  public static class CSqQueue<Integer>
  {
    final int MaxSize=10;//初始设定队列大小
    int[] data;
    int front,rear;
    boolean tag;
    public CSqQueue()
    {
      data=new int[MaxSize];
      front=rear=0;
      tag=false;
    }
    public boolean empty()
    //判断队列是否为空
    {
      return front==rear&&!tag;
    }
    public boolean full()
    //判断队列是否为满
    {
      return front==rear&&tag;
    }
    public int size()
    //返回队列大小
    {
      int x=(rear-front+MaxSize)%MaxSize;
      if(x==0&&tag) return MaxSize;
      return x;
    }
    public void push(int x)
    //入队操作，若队满则报错。注意入队完后，若front=rear，需改tag为true。
    {
      if(full()) 
        throw new IllegalArgumentException("The queue is full!!!");
      rear=(rear+1)%MaxSize;
      if(front==rear) tag=true;
      data[rear]=x;
    }
    public int pop()
    //出队操作，若队空则报错。注意出队前，若front=rear，需改tag为false。
    {
      if(empty())
        throw new IllegalArgumentException("The queue is empty!!!");
      if(front==rear) tag=false;
      front=(front+1)%MaxSize;
      return data[front];
    }
    public int top()
    //查询队首操作，若队空则提示并返回-1
    {
      if(empty()) 
      {
        System.out.println("The queue is empty!There is no top!");
        return -1;
      }
      return data[(front+1)%MaxSize];
    }
  }
  public static void main(String args[])
  //尝试每一个队列的基本运算并输出结果
  {
    Scanner in=new Scanner(System.in);
    CSqQueue Q=new CSqQueue<Integer>();
    int n=in.nextInt();
    for(int i=0;i<n;i++)
      Q.push(in.nextInt());
    for(int i=0;i<n;i++)
      System.out.println("full():"+Q.full()+" "+"pop():"+Q.pop()+" "+"top():"+Q.top()+" "+"size:"+Q.size()+" "+"empty():"+Q.empty());
  }
}

T6

本题代码为T6代码。

输入的第一行是队列里元素个数。
输入的第二行是队列里的元素。

import java.util.*;
public class hw3_6
{
  public static class SqQueue//注意如果类里只用一种数据类型，就不用加泛型标志
  {
    Stack<Integer> S1,S2;
    public SqQueue()
    {
      S1=new Stack<Integer>();
      S2=new Stack<Integer>();
    }
    public boolean empty()
    //判断队列是否为空
    {
      return S1.empty()&&S2.empty();
    }
    public int size()
    //返回队列内元素个数
    {
      return S1.size()+S2.size();
    }
    public void push(int x)
    //整数x入队操作。只入栈S1。
    {
      S1.push(x);
    }
    public int pop()
    //出队操作。若队列空则报错。
   //接着若S2空了，则将S1内元素全部出栈并入栈S2。
   //最后对S2执行一次出栈操作。
    {
      if(empty()) throw new IllegalArgumentException("The queue is empty!!!");
      if(S2.empty())
        while(!S1.empty()) S2.push(S1.pop());
      return S2.pop();
    }
    public int top()
    //取队首操作。若队列空则输出错误信息并返回-1。
    //接下来操作与出队很像，只是最后对S2执行的是取队首操作。
    {
      if(empty()) 
      {
        System.out.println("The queue is empty!There is no top!");
        return -1;
      }
      if(S2.empty())
        while(!S1.empty()) S2.push(S1.pop());
      return S2.peek();
    }
  }
  public static void main(String args[])
  //尝试每一个队列的基本运算并输出结果
  {
    Scanner in=new Scanner(System.in);
    SqQueue Q=new SqQueue();
    int n=in.nextInt();
    for(int i=0;i<n;i++)
      Q.push(in.nextInt());
    for(int i=0;i<n;i++)
      System.out.println("pop():"+Q.pop()+" "+"top():"+Q.top()+" "+"size:"+Q.size()+" "+"empty():"+Q.empty());
  }
}

T7

本题代码为T7代码。

输入的第一行是栈的元素个数。
输入的第二行是栈里的元素。

import java.util.*;
public class hw3_7
{
  public static class SqStack
  {
    Queue<Integer> Q1,Q2;
    public SqStack()
    {
      Q1=new LinkedList<Integer>();//注意Queue初始化的特殊性
      Q2=new LinkedList<Integer>();
    }
    public boolean empty()
    //判断栈是否为空
    {
      return Q1.isEmpty()&&Q2.isEmpty();
    }
    public int size()
    //返回栈内元素个数
    {
      return Q1.size()+Q2.size();
    }
    public void push(int x)
    //使整数x入栈，若二队列皆空则入队Q1，若队列Q1空则入队列Q2，若队列Q2空则入队列Q1
    {
      if(Q2.isEmpty()) Q1.offer(x);
      else Q2.offer(x);
    }
    public int pop()
    //出栈操作。若栈空则报错。
    //否则把非空队列元素依次出队并入队另一队列；当最后一个元素出队后，直接返回，不再入队。
   {
      int x=0;
      if(empty()) throw new IllegalArgumentException("The stack is empty!!!");
      if(Q2.isEmpty())
        while(!Q1.isEmpty())
        {
          x=Q1.poll();
          if(Q1.isEmpty()) return x;
          Q2.offer(x);
        }
      else
        while(!Q2.isEmpty())
        {
          x=Q2.poll();
          if(Q2.isEmpty()) return x;
          Q1.offer(x);
        }
      return x;
    }
    public int top()
    //查询栈顶操作。若栈空，输出错误信息并返回-1；否则先出栈以取出栈顶，再入栈。
    {
      if(empty()) 
      {
        System.out.println("The stack is empty!There is no top!");
        return -1;
      }
      int x=pop();
      push(x);
      return x;
    }
  }
  public static void main(String args[])
  //尝试每一个栈的基本运算并输出结果
  {
    Scanner in=new Scanner(System.in);
    SqStack S=new SqStack();
    int n=in.nextInt();
    for(int i=0;i<n;i++)
      S.push(in.nextInt());
    for(int i=0;i<n;i++)
      System.out.println("pop():"+S.pop()+" "+"top():"+S.top()+" "+"size:"+S.size()+" "+"empty():"+S.empty());
  }
}