跟左神学算法_3 基础数据结构(队列和栈)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了跟左神学算法_3 基础数据结构(队列和栈)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5051字，纯文字阅读大概需要8分钟。

内容图文

内容：

1、数组实现队列和栈

2、返回栈中最小元素

3、对列与栈

4、猫狗队列问题

 

 

 

1、数组实现队列和栈

 1 // 用数组实现基本的栈和队列 并在异常时抛出提示信息
 2 public class Array_To_Stack_Queue {
 3     // 数组实现栈
 4     public static class ArrayStack {
 5         private Integer[] arr;
 6         private Integer index;
 7         
 8         public ArrayStack(int initSize){
 9             // 栈的构造    initSize指定栈大小
10             if(initSize<0){
11                 throw new IllegalArgumentException("The init index is less than 0");
12             }
13             arr = new Integer[initSize];
14             index = 0;
15         }
16         
17         public Integer peek(){
18             // 返回栈顶
19             if(index==0){
20                 return null;
21             }
22             return arr[index-1];
23         }
24         
25         public void push(int obj){
26             // 压数入栈
27             if(index==arr.length){
28                 throw new ArrayIndexOutOfBoundsException("The stack is full!");
29             }
30             arr[index++] = obj;
31         }
32         
33         public Integer pop(){
34             // 弹出栈顶
35             if(index==0){
36                 throw new ArrayIndexOutOfBoundsException("The stack is empty!");
37             }
38             return arr[--index];
39         }
40         
41     }
42     
43     // 数组实现队列
44     public static class ArrayQueue{
45         private Integer[] arr;
46         private Integer size;
47         private Integer start;
48         private Integer end;
49         
50         public ArrayQueue(int initSize){
51             if(initSize<0){
52                 throw new IllegalArgumentException("The init size is less than 0");
53             }
54             arr = new Integer[initSize];
55             size = 0;
56             start = 0;
57             end = 0;
58         }
59         
60         public Integer peek() {
61             // 返回顶部元素
62             if (size == 0) {
63                 return null;
64             }
65             return arr[start];
66         }
67         
68         public void push(int obj) {
69             // 向队列中加入元素
70             if (size == arr.length) {
71                 throw new ArrayIndexOutOfBoundsException("The queue is full");
72             }
73             size++;
74             arr[end] = obj;
75             // end如果到最后一个位置就跳回到0 否则+1
76             end = end == arr.length - 1 ? 0 : end + 1;
77         }
78 
79         public Integer poll() {
80             // 从队列出取出元素
81             if (size == 0) {
82                 throw new ArrayIndexOutOfBoundsException("The queue is empty");
83             }
84             size--;
85             int tmp = start;
86             // start如果到最后一个位置就跳回到0 否则+1
87             start = start == arr.length - 1 ? 0 : start + 1;
88             return arr[tmp];
89         }
90         
91     }
92     
93 }

 

 

2、返回栈中最小元素

题目描述：

实现一个特殊的栈 在实现栈的基本功能的基础上 再实现返回栈中最小元素的操作

要求: pop push getMin 操作的时间复杂度都是O(1) 设计的栈类型可以使用现成的栈结构

 

思路：

使用两个栈，一个data栈用于存放数据，一个min栈用于存放当前压入栈中的数的最小值

每次压栈都把数据压入data栈，如果min栈为空或min栈栈顶大于当前数据就把当前数据压入min栈

 

代码：

 1 public class GetMinStack {
 2     public static class MyStack1 {
 3         private Stack<Integer> stackData;
 4         private Stack<Integer> stackMin;
 5         
 6         public MyStack1() {
 7             this.stackData = new Stack<Integer>();
 8             this.stackMin = new Stack<Integer>();
 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             } else {
17                 int newMin = this.stackMin.peek();
18                 this.stackMin.push(newMin);
19             }
20             this.stackData.push(newNum);
21         }
22 
23         public int pop() {
24             if (this.stackData.isEmpty()) {
25                 throw new RuntimeException("Your stack is empty.");
26             }
27             this.stackMin.pop();
28             return this.stackData.pop();
29         }
30 
31         public int getmin() {
32             if (this.stackMin.isEmpty()) {
33                 throw new RuntimeException("Your stack is empty.");
34             }
35             return this.stackMin.peek();
36         }
37     }
38     
39     public static void main(String[] args) {
40         MyStack1 stack1 = new MyStack1();
41         stack1.push(3);
42         System.out.println(stack1.getmin());
43         stack1.push(4);
44         System.out.println(stack1.getmin());
45         stack1.push(1);
46         System.out.println(stack1.getmin());
47         System.out.println(stack1.pop());
48         System.out.println(stack1.getmin());
49     }
50     
51 }

 

 

3、对列与栈

 

 

4、猫狗队列问题

 

内容总结

以上是互联网集市为您收集整理的跟左神学算法_3 基础数据结构(队列和栈)全部内容，希望文章能够帮你解决跟左神学算法_3 基础数据结构(队列和栈)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---