栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

算法与数据结构基础学习一(栈和队列)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

算法与数据结构基础学习一(栈和队列)

算法与数据结构 栈和队列 一、链表的定义

下面展示一些 链表定义。

 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());
    }


}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/930625.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号