下面展示一些 链表定义。
public static class Node{
public int value;
public Node next;
public Node(int data){
value = data;
}
}
//双向链表定义
public static class DoubleNode{
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(){}
public DoubleNode(int data){
value = data;
}
}
1、删除链表定值
下面展示一些 内联代码片。
//单链表删除定值
public static Node removeValue(Node head,int num){
while (head != null){
if (head.value != num){
break;
}
head = head.next;
}
Node pre = head;
Node cur = head;
while (cur != null){
if (cur.value != num){
pre = cur;
} else {
pre.next = cur.next;
}
cur = cur.next;
}
return head;
}
//双向链表删除定值
public static DoubleNode removeValue2(DoubleNode head,int num){
while(head != null){
if (head.value !=num){
break;
}
head = head.next;
}
DoubleNode pre = head;
DoubleNode cur = head;
while (cur != null){
if (cur.value == num){
pre.next = cur.next;
cur.next.last = pre;
}else {
pre = cur;
}
cur = cur.next;
}
return head;
}
}
2、链表反转
//单链表反转
public static Node reversLinkedList(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;
}
二、自定义栈和队列
1用链表实现代码如下(示例):
public class DoubleEndsQueueToStackAndQueue {
public static class Node{
public T value;
public Node next;
public Node last;
public Node(T data){
value = data;
}
}
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 addFromTail(T value){
Node cur = new Node(value);
if (head == null){
head = cur;
tail = cur;
}else{
tail.next = cur;
cur.last = tail;
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 popFromTail(){
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.popFromTail();
}
//判断是否为空
public boolean isEmpty(){
return queue.isEmpty();
}
}
public static boolean isEqual(Integer o1, Integer o2) {
if (o1 == null && o2 != null) {
return false;
}
if (o1 != null && o2 == null) {
return false;
}
if (o1 == null && o2 == null) {
return true;
}
return o1.equals(o2);
}
//for test
public static void main(String[] args) {
int oneTestDataNum = 100;
int value = 10000;
int testTimes = 100000;
for (int i = 0; i < testTimes; i++) {
MyStack myStack = new MyStack<>();
MyQueue myQueue = new MyQueue<>();
Stack stack = new Stack<>();
Queue queue = new LinkedList<>();
for (int j = 0; j < oneTestDataNum; j++) {
int nums = (int) (Math.random() * value);
if (stack.isEmpty()) {
myStack.push(nums);
stack.push(nums);
} else {
if (Math.random() < 0.5) {
myStack.push(nums);
stack.push(nums);
} else {
if (!isEqual(myStack.pop(), stack.pop())) {
System.out.println("oops!");
}
}
}
int numq = (int) (Math.random() * value);
if (stack.isEmpty()) {
myQueue.push(numq);
queue.offer(numq);
} else {
if (Math.random() < 0.5) {
myQueue.push(numq);
queue.offer(numq);
} else {
if (!isEqual(myQueue.poll(), queue.poll())) {
System.out.println("oops!");
}
}
}
}
}
System.out.println("finish!");
}
}
2用数组实现
//用数组实现栈和队列
public class RingArray {
public static class MyQueue{
private int[] arr;
private int pushi; //end
private int polli; //first
private int size;
private final int limit;
public MyQueue(int[] arr, int pushi, int polli, int size, int limit) {
this.arr = arr;
this.pushi = pushi;
this.polli = polli;
this.size = size;
this.limit = limit;
}
public MyQueue(int limit){
arr = new int[limit];
pushi = 0;
polli = 0;
size = 0;
this.limit = limit;
}
//下标一直在[0,limit-1]中循环
private int nextIndex(int i){
return i < limit-1 ? i+1 : 0;
}
//队列、进队列
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 value = arr[polli];
polli = nextIndex(polli);
return value;
}
}
public static class MyStack{
private int[] arr;
private int size;
private int index;
private final int limit;
public MyStack(int limit) {
arr = new int[limit];
size = 0;
index = 0;
this.limit = limit;
}
//进栈
public void push(int value){
if (size == limit){
throw new RuntimeException("栈满了,不能在放了");
}
size++;
arr[index] = value;
index++;
}
//出栈
public int pop(){
if (size == 0){
throw new RuntimeException("栈为空,不能在拿了");
}
int value = arr[index];
index--;
size--;
return value;
}
}
}
用两个队列实现栈
public class TwoQueueImplementStack {
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(){
if (queue.isEmpty()){
throw new RuntimeException("栈为空");
}
while (queue.size() >1){
help.offer(queue.poll());
}
T value = queue.poll();
//将queue和help队列交换,
Queue tmp = queue;
queue = help;
help = tmp;
return value;
}
//取出栈顶值,但是不去除栈顶值
public T peek(){
if (queue.isEmpty()){
throw new RuntimeException("栈为空");
}
while (queue.size() >1){
help.offer(queue.poll());
}
T value = queue.poll();
help.offer(value);
Queue tmp = queue;
queue = help;
help = tmp;
return value;
}
//判断栈是否为空
public boolean isEmpty(){
return queue.isEmpty();
}
}
public static void main(String[] args) {
System.out.println("test begin");
TwoQueueStack myStack = new TwoQueueStack<>();
Stack test = new Stack<>();
int testTime = 1000000;
int max = 1000000;
for (int i = 0; i < testTime; i++) {
if (myStack.isEmpty()) {
if (!test.isEmpty()) {
System.out.println("Oops");
}
int num = (int) (Math.random() * max);
myStack.push(num);
test.push(num);
} else {
if (Math.random() < 0.25) {
int num = (int) (Math.random() * max);
myStack.push(num);
test.push(num);
} else if (Math.random() < 0.5) {
if (!myStack.peek().equals(test.peek())) {
System.out.println("Oops");
}
} else if (Math.random() < 0.75) {
if (!myStack.poll().equals(test.pop())) {
System.out.println("Oops");
}
} else {
if (myStack.isEmpty() != test.isEmpty()) {
System.out.println("Oops");
}
}
}
}
System.out.println("test finish!");
}
}
用两个栈实现队列
public class TwoStackImplementQueue {
public static class TwoStackQueue {
public Stack stackPush;
public Stack stackPop;
public TwoStackQueue() {
stackPush = new Stack();
stackPop = new Stack();
}
//push栈向pop栈倒入数据
private void pushToPop(){
if (stackPop.empty()){
while (!stackPush.empty()){
stackPop.push(stackPush.pop());
}
}
}
//向队列添加数据
public void add(int value){
stackPush.push(value);
pushToPop();
}
//取出数据
public int poll(){
if (stackPop.empty() && stackPush.empty()){
throw new RuntimeException("队列为空");
}
pushToPop();
return stackPop.pop();
}
public int peek(){
if (stackPop.empty() && stackPush.empty()){
throw new RuntimeException("队列为空");
}
pushToPop();
return stackPop.peek();
}
}
public static void main(String[] args) {
TwoStackQueue test = new TwoStackQueue();
test.add(1);
test.add(2);
test.add(3);
System.out.println(test.peek());
System.out.println(test.poll());
System.out.println(test.peek());
System.out.println(test.poll());
System.out.println(test.peek());
System.out.println(test.poll());
}
}



