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

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

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

public class StackS { 
  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 stack = new StackS(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 { 
  private linkedList datas; 
   
  public StackSS() { 
    datas = new linkedList(); 
  } 
   
  // 入栈 
  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 stack = new StackS(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 stack = new StackSS(); 
    char[] charArray = word.toCharArray(); 
    int len = charArray.length; 
    for (int i = 0; i 

打印：

反转后：社会式株 





模拟队列(一般队列、双端队列、优先级队列)

队列：

先进先出，处理类似排队的问题，先排的，先处理，后排的等前面的处理完了，再处理

对于插入和移除操作的时间复杂度都为O(1)，从后面插入，从前面移除

双端队列：

即在队列两端都可以insert和remove：insertLeft、insertRight，removeLeft、removeRight

含有栈和队列的功能，如去掉insertLeft、removeLeft，那就跟栈一样了；如去掉insertLeft、removeRight，那就跟队列一样了

一般使用频率较低，时间复杂度 O(1)

优先级队列：

内部维护一个按优先级排序的序列。插入时需要比较查找插入的位置，时间复杂度O(N)， 删除O(1)

 

 
public class QueueQ { 
  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 queue = new QueueQ(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()); 
    } 
  } 
   
} 



 
public class QueueQT { 
  private linkedList list; 
 
  public QueueQT() { 
    list = new linkedList(); 
  } 
 
  // 插入队头 
  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); 
     
  } 
   
}