• 栈、队列——双向链表、数组表示以及相互表示

    一、双向链表表示栈、队列

    1. import java.util.*;
    2.  
    3. /**
    4.  * @author zhangchaoliang
    5.  * create 2022
    6.  */
    7. public class DoubleEndsQueueToStackAndQueue {
    8.     public static class Node{
    9.         public T value;
    10.         public Node last;
    11.         public Node next;
    12.  
    13.         public Node(T data){
    14.             value=data;
    15.         }
    16.     }
    17.  
    18.     public static class DoubleEndsQueue{
    19.         public Node head;
    20.         public Node tail;
    21.  
    22.         public void addFromHead(T value){
    23.             Node cur = new Node<>(value);
    24.             if (head==null){
    25.                 head=cur;
    26.                 tail=cur;
    27.             }else {
    28.                 cur.next=head;
    29.                 head.last=cur;
    30.                 head=cur;
    31.             }
    32.         }
    33.  
    34.         public void addFromBottom(T value){
    35.             Node cur = new Node<>(value);
    36.             if (head==null){
    37.                 head=cur;
    38.                 tail=cur;
    39.             }else {
    40.                 cur.last=tail;
    41.                 tail.next=cur;
    42.                 tail=cur;
    43.             }
    44.         }
    45.  
    46.         public T popFromHead(){
    47.             if (head==null)
    48.                 return null;
    49.             Node cur = head;
    50.             if (head==tail){
    51.                 head=null;
    52.                 tail=null;
    53.             }else {
    54.                 head=head.next;
    55.                 cur.next=null;
    56.                 head.last=null;
    57.             }
    58.             return cur.value;
    59.         }
    60.  
    61.         public T popFromBottom(){
    62.             if (head==null){
    63.                 return null;
    64.             }
    65.             Node cur = tail;
    66.             if (head==tail){
    67.                 head=null;
    68.                 tail=null;
    69.             }else {
    70.                 tail=tail.last;
    71.                 tail.next=null;
    72.                 cur.last=null;
    73.             }
    74.             return cur.value;
    75.         }
    76.  
    77.         public boolean isEmpty(){
    78.             return head==null;
    79.         }
    80.     }
    81.  
    82.     public static class MyStack{
    83.         private DoubleEndsQueue queue;
    84.  
    85.         public MyStack(){
    86.             queue=new DoubleEndsQueue<>();
    87.         }
    88.  
    89.         public void push(T value){
    90.             queue.addFromHead(value);
    91.         }
    92.  
    93.         public T pop(){
    94.             return queue.popFromHead();
    95.         }
    96.  
    97.         public boolean isEmpty(){
    98.             return queue.isEmpty();
    99.         }
    100.     }
    101.  
    102.     public static class MyQueue{
    103.         private DoubleEndsQueue queue;
    104.  
    105.         public MyQueue(){
    106.             queue=new DoubleEndsQueue<>();
    107.         }
    108.  
    109.         public void push(T value){
    110.             queue.addFromHead(value);
    111.         }
    112.  
    113.         public T poll(){
    114.             return queue.popFromBottom();
    115.         }
    116.  
    117.         public boolean isEmpty(){
    118.             return queue.isEmpty();
    119.         }
    120.     }
    121.  
    122.     public static boolean isEqual(Integer o1,Integer o2){
    123.         if (o1==null&&o2!=null)
    124.             return false;
    125.         if (o1!=null&&o2==null)
    126.             return false;
    127.         if (o1==null&&o2==null)
    128.             return true;
    129.         return o1.equals(o2);
    130.     }
    131.  
    132.     public static void main(String[] args) {
    133.         int oneTestDataNum=100;
    134.         int value = 10000;
    135.         int testTimes = 100000;
    136.         for (int i=0;i
    137.             MyStack myStack = new MyStack<>();
    138.             MyQueue myQueue = new MyQueue<>();
    139.             Stack stack = new Stack<>();
    140.             Queue queue = new LinkedList<>();
    141.             for (int j=0;j
    142.                 int nums = (int)(Math.random()*value);
    143.                 if (stack.isEmpty()){
    144.                     myStack.push(nums);
    145.                     stack.push(nums);
    146.                 }else {
    147.                     if (Math.random()<0.5){
    148.                         myStack.push(nums);
    149.                         stack.push(nums);
    150.                     }else {
    151.                         if (!isEqual(myStack.pop(),stack.pop()))
    152.                             System.out.println("Oops!");
    153.                     }
    154.                 }
    155.  
    156.                 int numq = (int)(Math.random()*value);
    157.                 if (queue.isEmpty()){
    158.                     myQueue.push(numq);
    159.                     queue.offer(numq);
    160.                 }else {
    161.                     if (Math.random()<0.5){
    162.                         myQueue.push(numq);
    163.                         queue.offer(numq);
    164.                     }else {
    165.                         if (!isEqual(myQueue.poll(),queue.poll()))
    166.                             System.out.println("Oops!");
    167.                     }
    168.                 }
    169.             }
    170.         }
    171.         System.out.println("finish!");
    172.     }
    173. }

    二、数组表示队列

    1. public class RingArray {
    2.     public static class MyQueue{
    3.         private int[] arr;
    4.         private int pushi;
    5.         private int polli;
    6.         private int size;
    7.         private final int limit;
    8.  
    9.         public MyQueue(int limit){
    10.             arr = new int[limit];
    11.             pushi=0;
    12.             polli=0;
    13.             size=0;
    14.             this.limit=limit;
    15.         }
    16.  
    17.         public void push(int value){
    18.             if (size==limit){
    19.                 throw new RuntimeException("队列满了，不能在加了！");
    20.             }
    21.             size++;
    22.             arr[pushi]=value;
    23.             pushi=nextIndex(pushi);
    24.         }
    25.         public int pop(){
    26.             if (size==0){
    27.                 throw new RuntimeException("队列空了，不能再拿了！");
    28.             }
    29.             size--;
    30.             int ans = arr[polli];
    31.             polli=nextIndex(polli);
    32.             return ans;
    33.         }
    34.  
    35.         public boolean isEmpty(){
    36.             return size==0;
    37.         }
    38.  
    39.         private int nextIndex(int i){
    40.             return i1?i+1:0;
    41.         }
    42.     }
    43.  
    44. }

    三、使用栈模拟队列

    1. public class TwoStacksImplementQueue {
    2.     public static class TwoStacksQueue{
    3.         public Stack stackPush;
    4.         public Stack stackPop;
    5.  
    6.         public TwoStacksQueue(){
    7.             stackPush=new Stack();
    8.             stackPop=new Stack();
    9.         }
    10.  
    11.         private void pushToPop(){
    12.             if (stackPop.isEmpty()){
    13.                 while (!stackPush.empty()){
    14.                     stackPop.push(stackPush.pop());
    15.                 }
    16.             }
    17.         }
    18.  
    19.         public void add(int pushInt){
    20.             stackPush.push(pushInt);
    21.             pushToPop();
    22.         }
    23.  
    24.         public int poll(){
    25.             if (stackPop.empty()&&stackPush.empty()){
    26.                 throw new RuntimeException("Queue is empty!");
    27.             }
    28.             pushToPop();
    29.             return stackPop.pop();
    30.         }
    31.  
    32.         public int peek(){
    33.             if (stackPop.empty()&&stackPush.empty()){
    34.                 throw new RuntimeException("Queue is empty!");
    35.             }
    36.             pushToPop();
    37.             return stackPop.peek();
    38.         }
    39.     }
    40.     public static void main(String[] args) {
    41.         TwoStacksQueue test = new TwoStacksQueue();
    42.         test.add(1);
    43.         test.add(2);
    44.         test.add(3);
    45.         System.out.println(test.peek());
    46.         System.out.println(test.poll());
    47.         System.out.println(test.peek());
    48.         System.out.println(test.poll());
    49.         System.out.println(test.peek());
    50.         System.out.println(test.poll());
    51.     }
    52. }

    四、使用队列模拟栈

    1. public class TwoQueueImplementStack {
    2.  
    3. 	public static class TwoQueueStack {
    4. 		public Queue queue;
    5. 		public Queue help;
    6.  
    7. 		public TwoQueueStack() {
    8. 			queue = new LinkedList<>();
    9. 			help = new LinkedList<>();
    10. 		}
    11.  
    12. 		public void push(T value) {
    13. 			queue.offer(value);
    14. 		}
    15.  
    16. 		public T poll() {
    17. 			while (queue.size() > 1) {
    18. 				help.offer(queue.poll());
    19. 			}
    20. 			T ans = queue.poll();
    21. 			Queue tmp = queue;
    22. 			queue = help;
    23. 			help = tmp;
    24. 			return ans;
    25. 		}
    26.  
    27. 		public T peek() {
    28. 			while (queue.size() > 1) {
    29. 				help.offer(queue.poll());
    30. 			}
    31. 			T ans = queue.poll();
    32. 			help.offer(ans);
    33. 			Queue tmp = queue;
    34. 			queue = help;
    35. 			help = tmp;
    36. 			return ans;
    37. 		}
    38.  
    39. 		public boolean isEmpty() {
    40. 			return queue.isEmpty();
    41. 		}
    42.  
    43. 	}
    44.  
    45. 	public static void main(String[] args) {
    46. 		System.out.println("test begin");
    47. 		TwoQueueStack myStack = new TwoQueueStack<>();
    48. 		Stack test = new Stack<>();
    49. 		int testTime = 1000000;
    50. 		int max = 1000000;
    51. 		for (int i = 0; i < testTime; i++) {
    52. 			if (myStack.isEmpty()) {
    53. 				if (!test.isEmpty()) {
    54. 					System.out.println("Oops");
    55. 				}
    56. 				int num = (int) (Math.random() * max);
    57. 				myStack.push(num);
    58. 				test.push(num);
    59. 			} else {
    60. 				if (Math.random() < 0.25) {
    61. 					int num = (int) (Math.random() * max);
    62. 					myStack.push(num);
    63. 					test.push(num);
    64. 				} else if (Math.random() < 0.5) {
    65. 					if (!myStack.peek().equals(test.peek())) {
    66. 						System.out.println("Oops");
    67. 					}
    68. 				} else if (Math.random() < 0.75) {
    69. 					if (!myStack.poll().equals(test.pop())) {
    70. 						System.out.println("Oops");
    71. 					}
    72. 				} else {
    73. 					if (myStack.isEmpty() != test.isEmpty()) {
    74. 						System.out.println("Oops");
    75. 					}
    76. 				}
    77. 			}
    78. 		}
    79.  
    80. 		System.out.println("test finish!");
    81.  
    82. 	}
    83.  
    84. }

    五、找出栈中的最小值

    1. public class GetMinStack {
    2.     public static class MyStack1{
    3.         private Stack stackData;
    4.         private Stack stackMin;
    5.  
    6.         public MyStack1(){
    7.             this.stackData=new Stack();
    8.             this.stackMin=new Stack();
    9.         }
    10.  
    11.         public void push(int newNum){
    12.             if (this.stackMin.isEmpty()){
    13.                 this.stackMin.push(newNum);
    14.             }else if (newNum<=this.getmin()){
    15.                 this.stackMin.push(newNum);
    16.             }
    17.             this.stackData.push(newNum);
    18.         }
    19.  
    20.         public int pop(){
    21.             if (this.stackData.isEmpty()){
    22.                 throw new RuntimeException("You stack is Empty.");
    23.             }
    24.             int value = this.stackData.pop();
    25.             if (value==this.getmin()){
    26.                 this.stackMin.pop();
    27.             }
    28.             return value;
    29.         }
    30.  
    31.         public int getmin(){
    32.             if (this.stackMin.isEmpty()){
    33.                 throw new RuntimeException("You stack is empty.");
    34.             }
    35.             return this.stackMin.peek();
    36.         }
    37.     }
    38.  
    39.     public static class MyStack2{
    40.         private Stack stackData;
    41.         private Stack stackMin;
    42.  
    43.         public MyStack2(){
    44.             this.stackData=new Stack();
    45.             this.stackMin=new Stack();
    46.         }
    47.  
    48.         public void push(int newNum){
    49.             if (this.stackMin.isEmpty()){
    50.                 throw new RuntimeException("You stack is empty.");
    51.             }else if (newNum<this.getMin()){
    52.                 this.stackMin.push(newNum);
    53.             }else {
    54.                 newNum=this.stackMin.peek();
    55.                 this.stackMin.push(newNum);
    56.             }
    57.             this.stackData.push(newNum);
    58.         }
    59.  
    60.         public int pop(){
    61.             if (this.stackData.isEmpty()){
    62.                 throw new RuntimeException("You stack is empty.");
    63.             }
    64.             this.stackMin.pop();
    65.             return this.stackData.pop();
    66.         }
    67.  
    68.         public int getMin(){
    69.             if (this.stackMin.isEmpty()){
    70.                 throw new RuntimeException("You stack is empty.");
    71.             }
    72.             return this.stackMin.peek();
    73.         }
    74.     }
    75.     public static void main(String[] args) {
    76.         MyStack1 stack1 = new MyStack1();
    77.         stack1.push(3);
    78.         System.out.println(stack1.getmin());
    79.         stack1.push(4);
    80.         System.out.println(stack1.getmin());
    81.         stack1.push(1);
    82.         System.out.println(stack1.getmin());
    83.         System.out.println(stack1.pop());
    84.         System.out.println(stack1.getmin());
    85.  
    86.         System.out.println("=============");
    87.  
    88.         MyStack1 stack2 = new MyStack1();
    89.         stack2.push(3);
    90.         System.out.println(stack2.getmin());
    91.         stack2.push(4);
    92.         System.out.println(stack2.getmin());
    93.         stack2.push(1);
    94.         System.out.println(stack2.getmin());
    95.         System.out.println(stack2.pop());
    96.         System.out.println(stack2.getmin());
    97.     }
    98. }

  • 相关阅读:
    Android 应用框架层 SQLite 源码分析
    DNS解析为什么不生效？DNS解析不生效原因分析
    数据结构-并查集刷题
    RestTemplate配置和使用
    MySQL—MySQL架构
    「从零单排canal 07」 parser模块源码解析
    非线性二分类——机器学习
    算法|最大堆、最小堆和堆排序的实现（JavaScript）
    “摸鱼”就能得出设计灵感？他的经验分享得看
    23种设计模式之 ： 模板方法设计模式
  • 原文地址：https://blog.csdn.net/z1171127310/article/details/126841788