寒光博客

[java] cc150 只用一个数组实现三个栈
cc150P 131 只用一个数组实现三个栈 先利用数组实现最普通的栈 并对其操作 类比法 把一个数组等分为三个栈...
扫描右侧二维码阅读全文
22
2019/10

[java] cc150 只用一个数组实现三个栈

cc150P 131 只用一个数组实现三个栈

先利用数组实现最普通的栈 并对其操作
类比法 把一个数组等分为三个栈

所以我设定了 三类变量 记录 栈头 尾 和元素个数

int s1l;//栈头 left
int s1r;//尾巴 right
int s1c = 0;//元素计数 count

在初始化对象的时候 就分配好了各自的 数据
我只写了push,写pop的话也是差不多的
和下面一个逻辑 划分清楚即可

                    first = s1l;//该栈 的头
                    end = s1r;//尾巴
                    if (s1c >= end - first + 1) {//满了
                        System.out.println("栈1满");
                        return;

                    } else if (arr[s1l] == 0) {//头元素
                        arr[s1l] = e;
                        s1c++;
                    } else {
                        while (arr[end] == 0) {//找到第一个逆序非空的元素
                            end--;
                        }
                        for (int i = end; i >= first; i--) {//从第一个逆序非空元素开始 都往后移动一个 并且已经解决满了的前提(一定是 小雨n-1个空间)
                            arr[i + 1] = arr[i];
                        }
                        arr[first] = e;//移动完成 目标元素放到 首部
                        s1c++;//计数+1
                    }

代码

package _09_Linear.Stack_QueuePractice;

import java.util.Arrays;

//只用一个数组实现三个栈 131
public class thereStack {

    static class Stack {
        int[] arr;
        int s1l;//栈头
        int s1r;//尾巴
        int s1c = 0;//元素计数

        int s2l;
        int s2r;
        int s2c = 0;
        int s3l;
        int s3r;
        int s3c = 0;

        Stack(int[] arr) {
            int start = 0;
            int end = arr.length - 1;
            this.arr = arr;
            //计算每个栈的头尾 假设arr[30]
            s1l = start;//0
            s1r = end / 3;//9

            s2l = end / 3 + 1;//10
            s2r = 2 * end / 3;//19

            s3l = 2 * end / 3 + 1;//20
            s3r = end;//29
        }

        /**
         * 对应桶里k放入指定元素
         *
         * @param k
         * @param e
         */
        public void push(int k, int e) {
            int first, end;
            switch (k) {
                case 0:
                    first = s1l;//该栈 的头
                    end = s1r;//尾巴
                    if (s1c >= end - first + 1) {//满了
                        System.out.println("栈1满");
                        return;

                    } else if (arr[s1l] == 0) {//头元素
                        arr[s1l] = e;
                        s1c++;
                    } else {
                        while (arr[end] == 0) {//找到第一个逆序非空的元素
                            end--;
                        }
                        for (int i = end; i >= first; i--) {//从第一个逆序非空元素开始 都往后移动一个 并且已经解决满了的前提(一定是 小雨n-1个空间)
                            arr[i + 1] = arr[i];
                        }
                        arr[first] = e;//移动完成 目标元素放到 首部
                        s1c++;//计数+1
                    }

                    break;
                case 1:
                    first = s2l;
                    end = s2r;
                    if (s2c >= end - first + 1) {//满了
                        System.out.println("栈2满");
                        return;

                    } else if (arr[s2l] == 0) {//头元素
                        arr[s2l] = e;
                        s2c++;
                    } else {
                        while (arr[end] == 0) {//找到第一个逆序非空的元素
                            end--;
                        }
                        for (int i = end; i >= first; i--) {
                            arr[i + 1] = arr[i];
                        }
                        arr[first] = e;
                        s2c++;
                    }
                    break;
                case 2:
                    first = s3l;
                    end = s3r;
                    if (s3c >= end - first + 1) {//满了
                        System.out.println("栈3满");
                        return;

                    } else if (arr[s3l] == 0) {//头元素
                        arr[s3l] = e;
                        s3c++;
                    } else {
                        while (arr[end] == 0) {//找到第一个逆序非空的元素
                            end--;
                        }
                        for (int i = end; i >= first; i--) {
                            arr[i + 1] = arr[i];
                        }
                        arr[first] = e;
                        s3c++;
                    }
                    break;
            }
        }
    }
    public static void main(String[] args) {
        int arr[] = new int[15];
        Stack s = new Stack(arr);
        s.push(0, 1);
        s.push(0, 1);
        s.push(0, 1);
        s.push(0, 1);
        s.push(0, 1);
        s.push(0, 1);

        s.push(1, 2);
        s.push(1, 3);
        s.push(1, 4);
        s.push(1, 5);
        s.push(1, 6);
        s.push(1, 7);

        s.push(2, 90);
        s.push(2, 90);
        s.push(2, 90);
        s.push(2, 90);
        s.push(2, 91);
        s.push(2, 92);


        System.out.println(Arrays.toString(arr));

    }
}
本文作者:Author:     文章标题:[java] cc150 只用一个数组实现三个栈
本文地址:https://dxoca.cn/java/304.html       百度未收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:October 23rd, 2019 at 11:55 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment