欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java模拟栈和队列数据结构的基本示例讲解

程序员文章站 2024-03-11 14:16:37
栈和队列: 一般是作为程序员的工具,用于辅助构思算法,生命周期较短,运行时才被创建; 访问受限,在特定时刻,只有一个数据可被读取或删除; 是一种抽象的结构,内部的实现...

栈和队列:
一般是作为程序员的工具,用于辅助构思算法,生命周期较短,运行时才被创建;
访问受限,在特定时刻,只有一个数据可被读取或删除;
是一种抽象的结构,内部的实现机制,对用户不可见,比如用数组、链表来实现栈。

模拟栈结构
同时,只允许一个数据被访问,后进先出
对于入栈和出栈的时间复杂度都为o(1),即不依赖栈内数据项的个数,操作比较快
例,使用数组作为栈的存储结构

public class stacks<t> { 
  private int max; 
  private t[] ary; 
  private int top;  //指针,指向栈顶元素的下标 
   
  public stacks(int size) { 
    this.max = size; 
    ary = (t[]) new object[max]; 
    top = -1; 
  } 
   
  // 入栈 
  public void push(t data) { 
    if (!isfull()) 
      ary[++top] = data; 
  } 
   
  // 出栈 
  public t pop() { 
    if (isempty()) { 
      return null; 
    } 
    return ary[top--]; 
  } 
   
  // 查看栈顶 
  public t peek() { 
    return ary[top]; 
  } 
   
  //栈是否为空 
  public boolean isempty() { 
    return top == -1; 
  } 
   
  //栈是否满 
  public boolean isfull() { 
    return top == max - 1; 
  } 
   
  //size 
  public int size() { 
    return top + 1; 
  } 
   
  public static void main(string[] args) { 
    stacks<integer> stack = new stacks<integer>(3); 
    for (int i = 0; i < 5; i++) { 
      stack.push(i); 
      system.out.println("size:" + stack.size()); 
    } 
    for (int i = 0; i < 5; i++) { 
      integer peek = stack.peek(); 
      system.out.println("peek:" + peek); 
      system.out.println("size:" + stack.size()); 
    } 
    for (int i = 0; i < 5; i++) { 
      integer pop = stack.pop(); 
      system.out.println("pop:" + pop); 
      system.out.println("size:" + stack.size()); 
    } 
     
    system.out.println("----"); 
     
    for (int i = 5; i > 0; i--) { 
      stack.push(i); 
      system.out.println("size:" + stack.size()); 
    } 
    for (int i = 5; i > 0; i--) { 
      integer peek = stack.peek(); 
      system.out.println("peek:" + peek); 
      system.out.println("size:" + stack.size()); 
    } 
    for (int i = 5; i > 0; i--) { 
      integer pop = stack.pop(); 
      system.out.println("pop:" + pop); 
      system.out.println("size:" + stack.size()); 
    } 
  } 
} 

上面的例子,有一个maxsize的规定,因为数组是要规定大小的,若想无限制,可以使用其他结构来做存储,当然也可以new一个新的长度的数组。
例,使用linkedlist存储来实现栈

public class stackss<t> { 
  private linkedlist<t> datas; 
   
  public stackss() { 
    datas = new linkedlist<t>(); 
  } 
   
  // 入栈 
  public void push(t data) { 
    datas.addlast(data); 
  } 
   
  // 出栈 
  public t pop() { 
    return datas.removelast(); 
  } 
   
  // 查看栈顶 
  public t peek() { 
    return datas.getlast(); 
  } 
   
  //栈是否为空 
  public boolean isempty() { 
    return datas.isempty(); 
  } 
   
  //size 
  public int size() { 
    return datas.size(); 
  } 
   
  public static void main(string[] args) { 
    stacks<integer> stack = new stacks<integer>(3); 
    for (int i = 0; i < 5; i++) { 
      stack.push(i); 
      system.out.println("size:" + stack.size()); 
    } 
    for (int i = 0; i < 5; i++) { 
      integer peek = stack.peek(); 
      system.out.println("peek:" + peek); 
      system.out.println("size:" + stack.size()); 
    } 
    for (int i = 0; i < 5; i++) { 
      integer pop = stack.pop(); 
      system.out.println("pop:" + pop); 
      system.out.println("size:" + stack.size()); 
    } 
     
    system.out.println("----"); 
    for (int i = 5; i > 0; i--) { 
      stack.push(i); 
      system.out.println("size:" + stack.size()); 
    } 
    for (int i = 5; i > 0; i--) { 
      integer peek = stack.peek(); 
      system.out.println("peek:" + peek); 
      system.out.println("size:" + stack.size()); 
    } 
    for (int i = 5; i > 0; i--) { 
      integer pop = stack.pop(); 
      system.out.println("pop:" + pop); 
      system.out.println("size:" + stack.size()); 
    } 
  } 
} 

例,单词逆序,使用statck结构

public class wordreverse { 
   
  public static void main(string[] args) { 
    reverse("株式会社"); 
  } 
   
  static void reverse(string word) { 
    if (word == null) return; 
    stackss<character> stack = new stackss<character>(); 
    char[] chararray = word.tochararray(); 
    int len = chararray.length; 
    for (int i = 0; i <len; i++ ) { 
      stack.push(chararray[i]); 
    } 
    stringbuilder sb = new stringbuilder(); 
    while (!stack.isempty()) { 
      sb.append(stack.pop()); 
    } 
    system.out.println("反转后:" + sb.tostring()); 
  } 
} 

打印:

反转后:社会式株 


模拟队列(一般队列、双端队列、优先级队列)
队列:
先进先出,处理类似排队的问题,先排的,先处理,后排的等前面的处理完了,再处理
对于插入和移除操作的时间复杂度都为o(1),从后面插入,从前面移除
双端队列:
即在队列两端都可以insert和remove:insertleft、insertright,removeleft、removeright
含有栈和队列的功能,如去掉insertleft、removeleft,那就跟栈一样了;如去掉insertleft、removeright,那就跟队列一样了
一般使用频率较低,时间复杂度 o(1)
优先级队列:
内部维护一个按优先级排序的序列。插入时需要比较查找插入的位置,时间复杂度o(n), 删除o(1)
 

/* 
 * 队列  先进先出,一个指针指示插入的位置,一个指针指示取出数据项的位置 
 */ 
public class queueq<t> { 
  private int max; 
  private t[] ary; 
  private int front; //队头指针 指示取出数据项的位置 
  private int rear; //队尾指针 指示插入的位置 
  private int nitems; //实际数据项个数 
   
  public queueq(int size) { 
    this.max = size; 
    ary = (t[]) new object[max]; 
    front = 0; 
    rear = -1; 
    nitems = 0; 
  } 
  //插入队尾 
  public void insert(t t) { 
    if (rear == max - 1) {//已到实际队尾,从头开始 
      rear = -1; 
    } 
    ary[++rear] = t; 
    nitems++; 
  } 
  //移除队头 
  public t remove() { 
    t temp = ary[front++]; 
    if (front == max) {//列队到尾了,从头开始 
      front = 0; 
    } 
    nitems--; 
    return temp; 
  } 
  //查看队头 
  public t peek() { 
    return ary[front]; 
  } 
   
  public boolean isempty() { 
    return nitems == 0; 
  } 
   
  public boolean isfull() { 
    return nitems == max; 
  } 
   
  public int size() { 
    return nitems; 
  } 
   
  public static void main(string[] args) { 
    queueq<integer> queue = new queueq<integer>(3); 
    for (int i = 0; i < 5; i++) { 
      queue.insert(i); 
      system.out.println("size:" + queue.size()); 
    } 
    for (int i = 0; i < 5; i++) { 
      integer peek = queue.peek(); 
      system.out.println("peek:" + peek); 
      system.out.println("size:" + queue.size()); 
    } 
    for (int i = 0; i < 5; i++) { 
      integer remove = queue.remove(); 
      system.out.println("remove:" + remove); 
      system.out.println("size:" + queue.size()); 
    } 
     
    system.out.println("----"); 
     
    for (int i = 5; i > 0; i--) { 
      queue.insert(i); 
      system.out.println("size:" + queue.size()); 
    } 
    for (int i = 5; i > 0; i--) { 
      integer peek = queue.peek(); 
      system.out.println("peek:" + peek); 
      system.out.println("size:" + queue.size()); 
    } 
    for (int i = 5; i > 0; i--) { 
      integer remove = queue.remove(); 
      system.out.println("remove:" + remove); 
      system.out.println("size:" + queue.size()); 
    } 
  } 
   
} 
/* 
 * 双端队列<span style="white-space:pre"> </span>两端插入、删除 
 */ 
public class queueqt<t> { 
  private linkedlist<t> list; 
 
  public queueqt() { 
    list = new linkedlist<t>(); 
  } 
 
  // 插入队头 
  public void insertleft(t t) { 
    list.addfirst(t); 
  } 
 
  // 插入队尾 
  public void insertright(t t) { 
    list.addlast(t); 
  } 
 
  // 移除队头 
  public t removeleft() { 
    return list.removefirst(); 
  } 
 
  // 移除队尾 
  public t removeright() { 
    return list.removelast(); 
  } 
 
  // 查看队头 
  public t peekleft() { 
    return list.getfirst(); 
  } 
 
  // 查看队尾 
  public t peekright() { 
    return list.getlast(); 
  } 
 
  public boolean isempty() { 
    return list.isempty(); 
  } 
 
  public int size() { 
    return list.size(); 
  } 
 
} 

/* 
 * 优先级队列  队列中按优先级排序,是一个有序的队列 
 */ 
public class queueqp { 
  private int max; 
  private int[] ary; 
  private int nitems; //实际数据项个数 
   
  public queueqp(int size) { 
    this.max = size; 
    ary = new int[max]; 
    nitems = 0; 
  } 
  //插入队尾 
  public void insert(int t) { 
    int j; 
    if (nitems == 0) { 
      ary[nitems++] = t; 
    } else { 
      for (j = nitems - 1; j >= 0; j--) { 
        if (t > ary[j]) { 
          ary[j + 1] = ary[j]; //前一个赋给后一个 小的在后    相当于用了插入排序,给定序列本来就是有序的,所以效率o(n) 
        } else { 
          break; 
        } 
      } 
      ary[j + 1] = t; 
      nitems++; 
    } 
    system.out.println(arrays.tostring(ary)); 
  } 
  //移除队头 
  public int remove() { 
    return ary[--nitems]; //移除优先级小的 
  } 
  //查看队尾 优先级最低的 
  public int peekmin() { 
    return ary[nitems - 1]; 
  } 
   
  public boolean isempty() { 
    return nitems == 0; 
  } 
   
  public boolean isfull() { 
    return nitems == max; 
  } 
   
  public int size() { 
    return nitems; 
  } 
   
  public static void main(string[] args) { 
    queueqp queue = new queueqp(3); 
    queue.insert(1); 
    queue.insert(2); 
    queue.insert(3); 
    int remove = queue.remove(); 
    system.out.println("remove:" + remove); 
     
  } 
   
}