算法基础三之链表、栈、队列、递归
public class DoubleNode {
public int value;
public DoubleNode pre;
public DoubleNode next;
public DoubleNode(int value) {
this.value = value;
}
}
单向链表和双向链表最简单的练习
链表相关的问题几乎都是 coding 问题
1）单链表和双链表怎么反转
package com.zh.class002;
public class ReverseList {
public static void main(String[] args) {
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
Node node = reverseLinkedList(head);
System.out.println(node.value);
System.out.println(node.next.value);
System.out.println(node.next.next.value);
}
public static Node reverseLinkedList(Node head) {
Node pre = null;
Node next = null;
while (head != null) {
next = head.next;
head.
next = pre;
pre = head;
head = next;
}
return pre;
}
public static DoubleNode reverseDoubleLinkedList(DoubleNode head) {
DoubleNode pre = null;
DoubleNode next = null;
while (head != null) {
next = head.next;
head.next = pre;
head.pre = next;
pre = head;
head = next;
}
return pre;
}
}
2）把给定值都删除
package com.zh.class002;
public class DeleteGivenValue {
public static void main(String[] args) {
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(2);
head.next.next.next = new Node(3);
Node node = removeValue(head, 2);
System.out.println(node);
}
public static Node removeValue(Node<Integer> head, int num) {
// head 来到第一个不需要删的位置
while (head != null) {
if (head.value == num) {
head = head.next;
} else {
break;
}
}
Node<Integer> pre = head;
Node<Integer> cur = head;
while (cur != null) {
if (cur.value == num) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return head;
}
}
栈和队列
====
逻辑概念
栈：数据先进后出，犹如弹匣
队列：数据先进先出，好似队列
栈和队列的实际实现：
package com.zh.class002.stackandqueue;
import com.zh.class002.DoubleNode;
public class DoubleEndsQueue<T> {
DoubleNode<T> head = null;
DoubleNode<T> tail = null;
public void addFromHead(T value) {
DoubleNode<T> cur = new DoubleNode<>(value);
if (head == null) {
head = cur;
tail = cur;
} else {
cur.next = head;
head.pre = cur;
head = cur;
}
}
public void addFromBottom(T value) {
DoubleNode<T> cur = new DoubleNode<>(value);
if (head == null) {
head = cur;
tail = cur;
} else {
tail.next = cur;
cur.pre = tail;
tail = cur;
}
}
public T popFromHead() {
if (head == null) {
return null;
}
DoubleNode<T> cur = head;
if (head == tail) {
head = null;
tail = null;
} else {
head = head.next;
cur.next = null;
head.pre = null;
}
return cur.value;
}
public T popFromBottom() {
if (head == null) {
return null;
}
DoubleNode<T> cur = tail;
if (head == tail) {
head = null;
tail = null;
} else {
tail = tail.pre;
tail.next = null;
cur.pre = null;
}
return cur.value;
}
public boolean isEmpty() {
return head == null;
}
}
双向链表实现
package com.zh.class002.stackandqueue;
public class MyStack<T> {
private DoubleEndsQueue<T> queue;
public MyStack() {
queue = new DoubleEndsQueue();
}
public void push(T value) {
queue.addFromHead(value);
}
public T pop() {
return queue.popFromHead();
}
public boolean isEmpty() {
return queue.isEmpty();
}
}
package com.zh.class002.stackandqueue;
public class MyQueue<T> {
private DoubleEndsQueue<T> queue;
public MyQueue() {
queue = new DoubleEndsQueue<T>();
}
public void push(T value) {
queue.addFromHead(value);
}
public T poll() {
return queue.popFromBottom();
}
public boolean isEmpty() {
return queue.isEmpty();
}
}
数组实现
package com.zh.class002.stackandqueue;
public class MyArrayStack {
public static void main(String[] args) {
MyArrayStack myArrayStack = new MyArrayStack(3);
myArrayStack.push(1);
myArrayStack.push(2);
myArrayStack.push(3);
System.out.println(myArrayStack.pop());
myArrayStack.push(4);
System.out.println(myArrayStack.pop());
}
private int[] arr;
int index = 0;
private final int limit;
public MyArrayStack(int limit) {
arr = new int[limit];
this.limit = limit;
}
public void push(int value) {
if (index == limit) {
throw new RuntimeException("栈满了，不能再加了");
}
arr[index ++] = value;
}
public int pop() {
if (index == 0) {
throw new RuntimeException("栈空了，不能再拿了");
}
return arr[--index];
}
public boolean isEmpty() {
return index == 0;
}
}
package com.zh.class002.stackandqueue;
public class MyArrayQueue {
private int[] arr;
private int pushi;
private int polli;
private int size;
private final int limit;
public MyArrayQueue(int limit) {
arr = new int[limit];
pushi = 0;
polli = 0;
size = 0;
this.limit = limit;
}
public void push(int value) {
if (size == limit) {
throw new RuntimeException("栈满了，不能再加了");
}
size++;
arr[pushi] = value;
pushi = nextIndex(pushi);
}
public int pop() {
if (size == 0) {
throw new RuntimeException("栈空了，不能再拿了");
}
size--;
int ans = arr[polli];
polli = nextIndex(polli);
return ans;
}
public boolean isEmpty() {
return size == 0;
}
// 如果现在的下标是 i，返回下一个位置
private int nextIndex(int i) {
return i < limit - 1 ? i + 1 : 0;
}
}
栈和队列的常见面试题
实现一个特殊的栈，在基本功能的基础上，再实现返回栈中最小元素的功能。
1）pop、push、getMin 操作的时间复杂度都是 O(1)。
2）设计的栈类型可以使用现成的栈结构。
实现一：双栈实现，一个栈存数据，另一个栈存最小值
package com.zh.class002;
import java.util.Stack;
public class GetMinStack {
public static void main(String[] args) {
GetMinStack getMinStack = new GetMinStack();
getMinStack.push(1);
getMinStack.push(2);
getMinStack.push(3);
System.out.println(getMinStack.getmin());
getMinStack.pop();
System.out.println(getMinStack.getmin());
getMinStack.pop();
System.out.println(getMinStack.getmin());
}
Stack<Integer> dataStack;
Stack<Integer> minStack;
public GetMinStack() {
this.dataStack = new Stack<>();
this.minStack = new Stack<>();
}
public void push(int newNum) {
if (minStack.isEmpty()) {
minStack.push(newNum);
} else if (newNum < minStack.peek()) {
minStack.push(newNum);
} else {
int newMin = minStack.peek();
minStack.push(newMin);
}
dataStack.push(newNum);
}
public int pop() {
if (this.dataStack.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
this.minStack.pop();
return this.dataStack.pop();
}
public int getmin() {
if (this.minStack.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
return this.minStack.peek();
}
}
面试题二：
1）如何用栈结构实现队列结构
2）如何用队列结构是实现栈结构
栈实现队列
package com.zh.class002;
import java.util.Stack;
public class TwoStacksImplementQueue {
public static void main(String[] args) {
TwoStacksImplementQueue twoStacksImplementQueue = new TwoStacksImplementQueue();
评论