用数组实现栈展开目录
实现栈太简单了,直接上代码
代码展开目录
- public class Stack {
- private Integer[] arr;
- private Integer idx;
- public Stack(int size) {
- if(size < 0)
- throw new StackOverflowError("please input again and input numer must more than 0");
- arr = new Integer[size];
- idx = 0;
- }
- public Integer peek() {
- if(idx == 0)
- return null;
- return arr[idx - 1];
- }
- public void push(int obj) {
- if(idx == arr.length)
- throw new StackOverflowError("The Stack is full");
- arr[idx++] = obj;
- }
- public Integer pop() {
- if(idx == 0)
- throw new StackOverflowError("The Stack is null");
- return arr[--idx];
- }
- public static void main(String[] args) {
- Stack stack = new Stack(5);
- stack.push(1);
- stack.push(2);
- stack.push(3);
- System.out.println(stack.pop());
- System.out.println(stack.pop());
- System.out.println(stack.pop());
- }
- }
用数组实现队列展开目录
题解展开目录
队列可能稍微有点复杂,定义队列的时候需要定义三个变量,分别是 end,start,size,先说说他们分别的作用,每次用户拿队中的元素,都从 start 下标位置取,每次进队都从 s=end 位置进,每次出队或者进队 size 都要 ++ 或 --
假设数组长度是 3,如果 size 没有到 3,进队时就把元素放到 end 的位置上,这是 end 和 size 之间的约束关系;如果 size 不等于 0,出队时就总出 start 位置,这是 start 和 size 之间的约束关系。end 本身还有一个约束,end 是控制进队的,所以每次进一个元素 end 就 ++,但在 ++ 前,如果 end== 数组长度,那么 end 就回到开头也就是 0 位置;同样的,start 也有这个约束
代码展开目录
- public class Queue {
- private int start = 0,end = 0,size = 0;
- private int[] arr;
- Queue(int size) {
- arr = new int[size];
- }
- public void push(int obj){
- if(size == arr.length)
- throw new ArrayIndexOutOfBoundsException("The Queue is full");
- size++;
- arr[end] = obj;
- end = end == arr.length - 1 ? 0 : end + 1;
- }
- public int pop(){
- if(size == 0)
- throw new ArrayIndexOutOfBoundsException("The Queue is full");
- size--;
- int tmp = start;
- start = start == arr.length - 1 ? 0 : start + 1;
- return arr[tmp];
- }
- public Integer peek() {
- if(size == 0)
- return null;
- return arr[start];
- }
- public static void main(String[] args) {
- Queue queue = new Queue(3);
- queue.push(3);
- queue.push(2);
- queue.push(1);
- System.out.println(queue.pop());
- System.out.println(queue.pop());
- System.out.println(queue.pop());
- }
- }
题目链接:LeetCode155展开目录
题解展开目录
如何在常数时间内检索到最小元素这是关键,可以开辟一个新的 min 栈,当 min 为空或者 push 的值比 min 的栈顶元素小时,就将该值 push 到 min 中去,否则就再次压入 min 栈的栈顶元素
同时如果用户调用了一次 pop () 函数,那么 min 栈也要跟着 pop
代码展开目录
- class MinStack {
- int[] data = new int[10000];
- int[] min = new int[10000];
- int idx_data,idx_min;
- public MinStack() {
- idx_data = 0;
- idx_min = 0;
- }
-
- public void push(int x) {
- data[idx_data++] = x;
- if(idx_min == 0 || x < min[idx_min - 1])
- min[idx_min++] = x;
- else
- min[idx_min++] = min[idx_min - 2];
- }
-
- public void pop() {
- idx_min--;
- idx_data--;
- }
-
- public int top() {
- return data[idx_data - 1];
- }
-
- public int getMin() {
- return min[idx_min - 1];
- }
- }
题目链接:LeeCode225展开目录
题解展开目录
这个题不要觉得很简单就不想写,很多地方有可能会用到,比方说图的深度优先遍历,别人不让你用栈去实现深度优先遍历,怎么办,其实就和这个道题的思路一样,用两个队列合成一个栈,然后再去遍历
那么说一下这道题的思路。假设现在有元素 12345 入队,要按照栈的方式弹出,应该怎么做,很简单,再设一个辅助队列 help,将 1234 全部弹出到 help 中,然后弹出 5 返回给用户即可
代码展开目录
- class MyStack {
- Queue<Integer> myQueue;
- public MyStack() {
- myQueue = new LinkedList();
- }
- /** Push element x onto stack. */
- public void push(int x) {
- int n= myQueue.size();
- Queue<Integer> tempQueue= new LinkedList();
- for(int i= 0; i<n; i++){
- tempQueue.add(myQueue.poll());
- }
- myQueue.add(x);
- for(int i= 0; i<n; i++){
- myQueue.add(tempQueue.poll());
- }
- }
-
- /** Removes and returns the element on top of the stack. */
- public int pop() {
- return (int)myQueue.poll();
- }
-
- /** Get the top element. */
- public int top() {
- return (int)myQueue.peek();
- }
-
- /** Returns whether the stack is empty. */
- public boolean empty() {
- return myQueue.isEmpty();
- }
- }
题目链接:LeetCode232展开目录
题解展开目录
用两个栈实现一个队列更简单,假设先在有两个栈 data 和 help,12345 首先进 data 栈,然后将 data 栈中的元素全部倒到 help 栈里,然后依次从 help 栈弹出即可,所以进元素全从 data 栈进,出元素全从 help 栈出,但是这两个栈交互的时候有两个条件:
- data 栈每次倒元素必须倒完
- 如果 help 栈里有东西,绝对不能将 data 栈的元素倒入 help 栈
代码展开目录
- class MyQueue {
-
- private Stack<Integer> data = new Stack<Integer>();
- private Stack<Integer> help = new Stack<Integer>();
- public MyQueue() {
- }
-
- /** Push element x to the back of queue. */
- public void push(int x) {
- data.push(x);
- }
-
- /** Removes the element from in front of queue and returns that element. */
- public int pop() {
- if(help.isEmpty())
- data_to_help();
- return help.pop();
- }
-
- /** Get the front element. */
- public int peek() {
- if(help.isEmpty())
- data_to_help();
- return help.peek();
- }
-
- /** Returns whether the queue is empty. */
- public boolean empty() {
- return data.isEmpty() && help.isEmpty();
- }
- public void data_to_help() {
- while(!data.isEmpty()) {
- help.push(data.pop());
- }
- }
- }
-
- /**
- * Your MyQueue object will be instantiated and called as such:
- * MyQueue obj = new MyQueue();
- * obj.push(x);
- * int param_2 = obj.pop();
- * int param_3 = obj.peek();
- * boolean param_4 = obj.empty();
- */