设为首页收藏本站
开启辅助访问

在路上

 找回密码
 立即注册
在路上 › 站点首页 ›学习 › 查看内容

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

2016-7-29 15:41| 发布者: zhangjf| 查看: 575| 评论: 0

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

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

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

  2. public class StackS<T> {
  3. private int max;
  4. private T[] ary;
  5. private int top; //指针，指向栈顶元素的下标
  7. public StackS(int size) {
  8. this.max = size;
  9. ary = (T[]) new Object[max];
  10. top = -1;
  11. }
  13. // 入栈
  14. public void push(T data) {
  15. if (!isFull())
  16. ary[++top] = data;
  17. }
  19. // 出栈
  20. public T pop() {
  21. if (isEmpty()) {
  22. return null;
  23. }
  24. return ary[top--];
  25. }
  27. // 查看栈顶
  28. public T peek() {
  29. return ary[top];
  30. }
  32. //栈是否为空
  33. public boolean isEmpty() {
  34. return top == -1;
  35. }
  37. //栈是否满
  38. public boolean isFull() {
  39. return top == max - 1;
  40. }
  42. //size
  43. public int size() {
  44. return top + 1;
  45. }
  47. public static void main(String[] args) {
  48. StackS<Integer> stack = new StackS<Integer>(3);
  49. for (int i = 0; i < 5; i++) {
  50. stack.push(i);
  51. System.out.println("size:" + stack.size());
  52. }
  53. for (int i = 0; i < 5; i++) {
  54. Integer peek = stack.peek();
  55. System.out.println("peek:" + peek);
  56. System.out.println("size:" + stack.size());
  57. }
  58. for (int i = 0; i < 5; i++) {
  59. Integer pop = stack.pop();
  60. System.out.println("pop:" + pop);
  61. System.out.println("size:" + stack.size());
  62. }
  64. System.out.println("----");
  66. for (int i = 5; i > 0; i--) {
  67. stack.push(i);
  68. System.out.println("size:" + stack.size());
  69. }
  70. for (int i = 5; i > 0; i--) {
  71. Integer peek = stack.peek();
  72. System.out.println("peek:" + peek);
  73. System.out.println("size:" + stack.size());
  74. }
  75. for (int i = 5; i > 0; i--) {
  76. Integer pop = stack.pop();
  77. System.out.println("pop:" + pop);
  78. System.out.println("size:" + stack.size());
  79. }
  80. }
  81. }
复制代码

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

  2. public class StackSS<T> {
  3. private LinkedList<T> datas;
  5. public StackSS() {
  6. datas = new LinkedList<T>();
  7. }
  9. // 入栈
  10. public void push(T data) {
  11. datas.addLast(data);
  12. }
  14. // 出栈
  15. public T pop() {
  16. return datas.removeLast();
  17. }
  19. // 查看栈顶
  20. public T peek() {
  21. return datas.getLast();
  22. }
  24. //栈是否为空
  25. public boolean isEmpty() {
  26. return datas.isEmpty();
  27. }
  29. //size
  30. public int size() {
  31. return datas.size();
  32. }
  34. public static void main(String[] args) {
  35. StackS<Integer> stack = new StackS<Integer>(3);
  36. for (int i = 0; i < 5; i++) {
  37. stack.push(i);
  38. System.out.println("size:" + stack.size());
  39. }
  40. for (int i = 0; i < 5; i++) {
  41. Integer peek = stack.peek();
  42. System.out.println("peek:" + peek);
  43. System.out.println("size:" + stack.size());
  44. }
  45. for (int i = 0; i < 5; i++) {
  46. Integer pop = stack.pop();
  47. System.out.println("pop:" + pop);
  48. System.out.println("size:" + stack.size());
  49. }
  51. System.out.println("----");
  52. for (int i = 5; i > 0; i--) {
  53. stack.push(i);
  54. System.out.println("size:" + stack.size());
  55. }
  56. for (int i = 5; i > 0; i--) {
  57. Integer peek = stack.peek();
  58. System.out.println("peek:" + peek);
  59. System.out.println("size:" + stack.size());
  60. }
  61. for (int i = 5; i > 0; i--) {
  62. Integer pop = stack.pop();
  63. System.out.println("pop:" + pop);
  64. System.out.println("size:" + stack.size());
  65. }
  66. }
  67. }
复制代码

例，单词逆序，使用Statck结构

  2. public class WordReverse {
  4. public static void main(String[] args) {
  5. reverse("株式会社");
  6. }
  8. static void reverse(String word) {
  9. if (word == null) return;
  10. StackSS<Character> stack = new StackSS<Character>();
  11. char[] charArray = word.toCharArray();
  12. int len = charArray.length;
  13. for (int i = 0; i <len; i++ ) {
  14. stack.push(charArray[i]);
  15. }
  16. StringBuilder sb = new StringBuilder();
  17. while (!stack.isEmpty()) {
  18. sb.append(stack.pop());
  19. }
  20. System.out.println("反转后：" + sb.toString());
  21. }
  22. }
复制代码

打印：

  2. 反转后：社会式株
复制代码


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

  2. /*
  3. * 队列 先进先出，一个指针指示插入的位置，一个指针指示取出数据项的位置
  4. */
  5. public class QueueQ<T> {
  6. private int max;
  7. private T[] ary;
  8. private int front; //队头指针 指示取出数据项的位置
  9. private int rear; //队尾指针 指示插入的位置
  10. private int nItems; //实际数据项个数
  12. public QueueQ(int size) {
  13. this.max = size;
  14. ary = (T[]) new Object[max];
  15. front = 0;
  16. rear = -1;
  17. nItems = 0;
  18. }
  19. //插入队尾
  20. public void insert(T t) {
  21. if (rear == max - 1) {//已到实际队尾，从头开始
  22. rear = -1;
  23. }
  24. ary[++rear] = t;
  25. nItems++;
  26. }
  27. //移除队头
  28. public T remove() {
  29. T temp = ary[front++];
  30. if (front == max) {//列队到尾了，从头开始
  31. front = 0;
  32. }
  33. nItems--;
  34. return temp;
  35. }
  36. //查看队头
  37. public T peek() {
  38. return ary[front];
  39. }
  41. public boolean isEmpty() {
  42. return nItems == 0;
  43. }
  45. public boolean isFull() {
  46. return nItems == max;
  47. }
  49. public int size() {
  50. return nItems;
  51. }
  53. public static void main(String[] args) {
  54. QueueQ<Integer> queue = new QueueQ<Integer>(3);
  55. for (int i = 0; i < 5; i++) {
  56. queue.insert(i);
  57. System.out.println("size:" + queue.size());
  58. }
  59. for (int i = 0; i < 5; i++) {
  60. Integer peek = queue.peek();
  61. System.out.println("peek:" + peek);
  62. System.out.println("size:" + queue.size());
  63. }
  64. for (int i = 0; i < 5; i++) {
  65. Integer remove = queue.remove();
  66. System.out.println("remove:" + remove);
  67. System.out.println("size:" + queue.size());
  68. }
  70. System.out.println("----");
  72. for (int i = 5; i > 0; i--) {
  73. queue.insert(i);
  74. System.out.println("size:" + queue.size());
  75. }
  76. for (int i = 5; i > 0; i--) {
  77. Integer peek = queue.peek();
  78. System.out.println("peek:" + peek);
  79. System.out.println("size:" + queue.size());
  80. }
  81. for (int i = 5; i > 0; i--) {
  82. Integer remove = queue.remove();
  83. System.out.println("remove:" + remove);
  84. System.out.println("size:" + queue.size());
  85. }
  86. }
  88. }
复制代码
  2. /*
  3. * 双端队列<span style="white-space:pre"> </span>两端插入、删除
  4. */
  5. public class QueueQT<T> {
  6. private LinkedList<T> list;
  8. public QueueQT() {
  9. list = new LinkedList<T>();
  10. }
  12. // 插入队头
  13. public void insertLeft(T t) {
  14. list.addFirst(t);
  15. }
  17. // 插入队尾
  18. public void insertRight(T t) {
  19. list.addLast(t);
  20. }
  22. // 移除队头
  23. public T removeLeft() {
  24. return list.removeFirst();
  25. }
  27. // 移除队尾
  28. public T removeRight() {
  29. return list.removeLast();
  30. }
  32. // 查看队头
  33. public T peekLeft() {
  34. return list.getFirst();
  35. }
  37. // 查看队尾
  38. public T peekRight() {
  39. return list.getLast();
  40. }
  42. public boolean isEmpty() {
  43. return list.isEmpty();
  44. }
  46. public int size() {
  47. return list.size();
  48. }
  50. }
复制代码
  2. /*
  3. * 优先级队列 队列中按优先级排序，是一个有序的队列
  4. */
  5. public class QueueQP {
  6. private int max;
  7. private int[] ary;
  8. private int nItems; //实际数据项个数
  10. public QueueQP(int size) {
  11. this.max = size;
  12. ary = new int[max];
  13. nItems = 0;
  14. }
  15. //插入队尾
  16. public void insert(int t) {
  17. int j;
  18. if (nItems == 0) {
  19. ary[nItems++] = t;
  20. } else {
  21. for (j = nItems - 1; j >= 0; j--) {
  22. if (t > ary[j]) {
  23. ary[j + 1] = ary[j]; //前一个赋给后一个 小的在后 相当于用了插入排序，给定序列本来就是有序的，所以效率O(N)
  24. } else {
  25. break;
  26. }
  27. }
  28. ary[j + 1] = t;
  29. nItems++;
  30. }
  31. System.out.println(Arrays.toString(ary));
  32. }
  33. //移除队头
  34. public int remove() {
  35. return ary[--nItems]; //移除优先级小的
  36. }
  37. //查看队尾 优先级最低的
  38. public int peekMin() {
  39. return ary[nItems - 1];
  40. }
  42. public boolean isEmpty() {
  43. return nItems == 0;
  44. }
  46. public boolean isFull() {
  47. return nItems == max;
  48. }
  50. public int size() {
  51. return nItems;
  52. }
  54. public static void main(String[] args) {
  55. QueueQP queue = new QueueQP(3);
  56. queue.insert(1);
  57. queue.insert(2);
  58. queue.insert(3);
  59. int remove = queue.remove();
  60. System.out.println("remove:" + remove);
  62. }
  64. }
复制代码


收藏 邀请
上一篇：Java实现冒泡排序与双向冒泡排序算法的代码示例下一篇：Java仿12306图片验证码

最新评论

相关分类

小黑屋|在路上 ( 蜀ICP备15035742号-1 )  

;

GMT+8, 2025-5-6 12:40

Copyright 2015-2025 djqfx

返回顶部