服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|JAVA教程|ASP教程|

服务器之家 - 编程语言 - JAVA教程 - Java模拟栈和队列数据结构的基本示例讲解

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

2020-04-17 11:19匆忙拥挤repeat JAVA教程

这篇文章主要介绍了Java模拟栈和队列数据结构的基本示例,栈的后进先出和队列的先进先出是数据结构中最基础的知识,本文则又对Java实现栈和队列结构的方法进行了细分,需要的朋友可以参考下

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

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
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存储来实现栈

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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结构

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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());
  }
}

打印:

?
1
反转后:社会式株


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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/*
 * 队列  先进先出,一个指针指示插入的位置,一个指针指示取出数据项的位置
 */
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());
    }
  }
   
}
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*
 * 双端队列<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();
  }
 
}
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
 * 优先级队列  队列中按优先级排序,是一个有序的队列
 */
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);
     
  }
   
}

 

延伸 · 阅读

精彩推荐