单链表和双链表
//单向链表节点结构
public class Node {
//内容 整型
public int value;
//next指针 Node型
public Node next;
//给内容赋值
public Node(int data) {
value = data;
}
}
//双向链表节点结构
public class DoubleNode {
//内容整型
public int value;
//last指针 DoubleNode型
public DoubleNode last;
//next指针 DoubleNode型
public DoubleNode next;
//给内容赋值
public DoubleNode(int data) {
value = data;
}
}
单链表和双链表如何反转
单链表反转：
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 reverseDoubleList(DoubleNode head) {
DoubleNode pre = null;
DoubleNode next = null;
while (head != null) {
next = head.next;
head.next = pre;
head.last = next;
pre = head;
head = next;
}
return pre;
}
单链表和双链表把给定值都删除
public static Node removeValue(Node head, int num) {
// 退出循环时，head来到第一个不需要删的位置
while (head != null) {
if (head.value != num) {
break;
}
head = head.next;
}
// 1 ) head == null
// 2 ) head != null
Node pre = head;
Node cur = head;
while (cur != null) {
if (cur.value == num) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return head;
}
}
栈和队列逻辑概念 ：
栈：数据先进后出
队列：数据先进先出
双链表实现栈和队列：
public static class DoubleEndsQueue{ public Node head; public Node tail; //新节点成为头 public void addFromHead(T value) { Node cur = new Node (value); if (head == null) { head = cur; tail = cur; } else { cur.next = head; head.last = cur; head = cur; } } //新节点成为尾 public void addFromBottom(T value) { Node cur = new Node (value); if (head == null) { head = cur; tail = cur; } else { cur.last = tail; tail.next = cur; tail = cur; } } //去掉头节点并返回节点值 public T popFromHead() { if (head == null) { return null; } Node cur = head; if (head == tail) { head = null; tail = null; } else { head = head.next; cur.next = null; head.last = null; } return cur.value; } //去掉尾节点并返回节点值 public T popFromBottom() { if (head == null) { return null; } Node cur = tail; if (head == tail) { head = null; tail = null; } else { tail = tail.last; tail.next = null; cur.last = null; } return cur.value; } //判空 public boolean isEmpty() { return head == null; } }
双向链表实现栈
//先进后出 public static class MyStack{ private DoubleEndsQueue 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(); } }
双向链表实现队列
//先进先出 public static class MyQueue{ private DoubleEndsQueue queue; public MyQueue() { queue = new DoubleEndsQueue (); } //在头部添加数据 头部属于后进 public void push(T value) { queue.addFromHead(value); } //在后面去除数据 尾部属于先出 public T poll() { return queue.popFromBottom(); } public boolean isEmpty() { return queue.isEmpty(); } }
怎么用数组实现不超过固定大小的队列和栈？
栈：正常使用
队列：环形数组
public static class MyQueue {
private int[] arr;
//最后加入数据下标 加数据的位置
private int pushi;// end
//最先加入数据下标 减数据的位置
private int polli;// begin
private int size;
private final int limit;
//起到记录的作用 limit是arr数组长度
public MyQueue(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++;
//pushi的位置加入数据
arr[pushi] = value;
//没到底部加1，到底部返回0
pushi = nextIndex(pushi);
}
public int pop() {
if (size == 0) {
throw new RuntimeException("队列空了，不能再拿了");
}
size--;
//从polli的位置减数据
int ans = arr[polli];
//没到底部加1，到底部返回0
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）设计的栈类型可以使用现成的栈结构。
思路：方法一：设计两个栈，一个是数据栈，一个是最小栈。数据栈正常放数据，最小栈判断加入的数据是否小于上次压入的数据，如果小于，压入这次数据，如果大于，不压入数据，弹出时，数据栈直接弹，判断弹出的数据栈的值和最小栈的最小值是否相等，如果相等弹出最小栈最小值，否则不弹出。
方法二：设计两个栈，一个是数据栈，一个是最小栈。数据栈正常放数据，最小栈判断加入的数据是否小于上次压入的数据，如果小于，压入这次数据，如果大于，压入上次压入的数据。同步加，同步弹。
//方法一：
public static class MyStack1 {
private Stack stackData;
private Stack stackMin;
public MyStack1() {
this.stackData = new Stack();
this.stackMin = new Stack();
}
//压入新数据
public void push(int newNum) {
//判断最小栈是否为空，如果为空直接加入，否则判断压入的数和当前最小栈的最小值的大小
if (this.stackMin.isEmpty()) {
this.stackMin.push(newNum);
} else if (newNum <= this.getmin()) {
//压入的数小于当前最小栈的最小值，压入新数据
this.stackMin.push(newNum);
}
//数据栈压入数据
this.stackData.push(newNum);
}
public int pop() {
//判断数据栈是否为空
if (this.stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
//记录数据栈弹出的数据
int value = this.stackData.pop();
//判断弹出的数据和最小值是否相等
if (value == this.getmin()) {
this.stackMin.pop();
}
return value;
}
public int getmin() {
//判断最小栈是否为空
if (this.stackMin.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
//返回最小值，无需取出
return this.stackMin.peek();
}
}
//方法二：
public static class MyStack2 {
private Stack stackData;
private Stack stackMin;
public MyStack2() {
this.stackData = new Stack();
this.stackMin = new Stack();
}
public void push(int newNum) {
if (this.stackMin.isEmpty()) {
this.stackMin.push(newNum);
} else if (newNum < this.getmin()) {
this.stackMin.push(newNum);
} else {
int newMin = this.stackMin.peek();
this.stackMin.push(newMin);
}
this.stackData.push(newNum);
}
public int pop() {
if (this.stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
this.stackMin.pop();
return this.stackData.pop();
}
public int getmin() {
if (this.stackMin.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
return this.stackMin.peek();
}
}
（1）如何用栈结构实现队列结构
创建两个栈：push和pop栈
push栈倒入pop栈，要一次性倒完
看pop栈空不空，空了push栈才能倒
public static class TwoStacksQueue {
public Stack stackPush;
public Stack stackPop;
//创建两个栈
public TwoStacksQueue() {
stackPush = new Stack();
stackPop = new Stack();
}
// push栈向pop栈倒入数据
private void pushToPop() {
//判断pop栈是否为空
if (stackPop.empty()) {
//判断push栈是否非空
while (!stackPush.empty()) {
//将push栈的数据全部转移到pop栈中
stackPop.push(stackPush.pop());
}
}
}
//加数据时往push栈中加，然后判断能不能往pop栈中倒
public void add(int pushInt) {
stackPush.push(pushInt);
pushToPop();
}
//弹数据时，判断能不能往pop栈中倒，然后在pop栈中弹，
public int poll() {
//push和pop栈同时为空
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
}
pushToPop();
return stackPop.pop();
}
public int peek() {
//push和pop栈同时为空
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
}
pushToPop();
return stackPop.peek();
}
}
（2）如何用队列结构实现栈结构
思路：队列654321 栈后入先出弹出6
队列1：6 队列2：54321
队列1弹出6
Queue
tmp = queue; queue = help;
help = tmp;
相当于使两个队列相互换名字，数据永远从queue中弹出
public static class TwoQueueStack{ //两个队列 public Queue queue; public Queue help; public TwoQueueStack() { queue = new LinkedList<>(); help = new LinkedList<>(); } //插入数据 public void push(T value) { queue.offer(value); } //弹出数据 public T poll() { //判断queue的长度是否大于1 while (queue.size() > 1) { //将queue中的数据弹出，放到help中，直到queue中的数据只有1个 help.offer(queue.poll()); } //ans记录queue弹出的数 T ans = queue.poll(); //tmp指向queue Queue tmp = queue; //queue指向help queue = help; //help指向tmp help = tmp; //返回queue弹出的数据 return ans; } public T peek() { while (queue.size() > 1) { help.offer(queue.poll()); } T ans = queue.poll(); help.offer(ans); Queue tmp = queue; queue = help; help = tmp; return ans; } public boolean isEmpty() { return queue.isEmpty(); } }
