赞
踩
一些算法基础知识点和leetcode题解,语言是Java。来源于这里。
队列:先入先出
单端队列:左边进右边出
双端队列:左边进右边出或者右边进左边出(不常用)
复杂度:
Java里面有个接口Queue,用来实现队列,然后告诉queue队列里的元素类型是Integer。
由于只是一个接口,所以还需要LinkedList作为对象(因为链表插入删除比较快,如果用ArrayList也可以,但是时间复杂度就会变)
Queue<Integer> queue = new LinkedLIst<>();
queue.add(1);
queue.add(2);
//[1,2,3]
System.out.println(queue.toString());
int temp1 = queue.peek();
//1
System.out.println(temp1);
int temp2 = queue.poll();
//1
System.out.println(temp2);
System.out.println(queue.isEmpty()); //false
System.out.println(queue.size()); //1
while (!queue.isEmpty()){
int temp = queue.poll(); //边删除边遍历
System.out.println(temp);
}
栈:先进后出
应用:浏览器的后对功能
复杂度:
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
//[1,2]
System.out.println(stack.toString());
int temp1 = stack.peek();
//2
System.out.println(temp1);
int temp2 = stack.pop();
//2
System.out.println(temp2);
System.out.println(stack.isEmpty()); //false
System.out.println(stack.size()); //1
while (!stack.isEmpty()){
int temp = stack.pop(); //边删除边遍历
System.out.println(temp);
}
class MyQueue { Stack<Integer> stackIn; Stack<Integer> stackOut; public MyQueue() { stackIn = new Stack<>(); stackOut = new Stack<>(); } public void push(int x) { //入队列 stackIn.push(x); } public int pop() { //从队列的开头移除并返回元素 //栈里面pop的是队尾的元素 if (stackOut.isEmpty()) { //如果 stackOut 为空,说明当前没有元素可以直接出队列或者查看队头元素 while (stackIn.isEmpty() == false) { //stackIn非空,压入stackOut中 stackOut.push(stackIn.pop()); } } return stackOut.pop(); } public int peek() { //返回队列开头的元素 if (stackOut.isEmpty()) { while (stackIn.isEmpty() == false) { stackOut.push(stackIn.pop()); } } return stackOut.peek(); } public boolean empty() { return stackIn.isEmpty() && stackOut.isEmpty(); } } /** * 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(); */
class MyStack { Queue<Integer> queue = new LinkedList<>(); public MyStack() { } public void push(int x) { //将元素 x 压入栈顶 queue.add(x); } public int pop() { //移除并返回栈顶(队列的尾部)元素 //把前面的size-1个元素都弹出来,剩下的就是栈顶元素 int size = queue.size(); while(size > 1){ queue.add(queue.poll()); size--; } return queue.poll(); } public int top() { //返回栈顶元素 int size = queue.size(); while(size > 1){ queue.add(queue.poll()); size--; } int top = queue.peek(); // 获取栈顶元素但不移除 queue.add(queue.poll()); return top; } public boolean empty() { return queue.isEmpty(); } } /** * Your MyStack object will be instantiated and called as such: * MyStack obj = new MyStack(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.top(); * boolean param_4 = obj.empty(); */
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。