Zero, preface,

1. You should be used to call methods inside methods, have you ever wondered how computers recognize 2. You can certainly sense that the last method always returns first, and then continues to calculate 3 in the last method. Last in, first out. That might seem unfair in the real world, but it seems to be true in the computer world, and it makes a big difference. I hope you can and I at Github together to witness: the birth and growth of DS4Android, welcome to star

1. The final operation effect of the stack:

2. Introduction to stack structure:
The stack is a linear data structure: only the top elements are visible, LIFO operation: push the stack, pop the stack, peek, view the top elementsCopy the code

The interface to define the stack: IStack

Stack is a very simple data structure, the method is very few, but the flexible use of personal sense stack is very pure, simple, but not simple.

/** * Author: Zhang Feng Jiete Lie * Time: 2018/8/17 0017:12:49 * Email: [email protected] * Description: Public interface IStack<T> {/** * Number of stack elements * @returnInt size(); /** * Stack element volume * @returnInt capacity(); /** * Is null * @return*/ Boolean isEmpty(); /** * push @param el element */ void push(T el); /** * stack * @returnElement */ T pop(); /** * Take out element * @returnElement */ T peek(); }Copy the code

Two, the stack of a variety of implementation

Similarly, the stack is also an abstract concept, need to achieve, this article will use the previous written array table and single linked list to achieve the stack note: double linked list and single linked list to achieve the stack is basically the same, from the simplicity of the structure of the single linked list has some advantages, so no double linked list

1. Array table stack:

In fact, the array table has all the functions of the stack, here is just to implement the stack interface call, the bottom layer is the array implementation

/** * Author: Zhang Feng Jiete Lie * Time: 2018/8/17 0017:12:56 * Email: [email protected] * Description: */ public class ArrayChartStack<T> implements IStack<T> {private ArrayChart<T> array; Public ArrayChartStack(int capacity) {array = new ArrayChart<>(capacity); } publicArrayChartStack() {
        array = new ArrayChart<>();
    }

    @Override
    public int size() {
        return array.size();
    }

    @Override
    public int capacity() {
        return array.capacity();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    @Override
    public T pop() {
        return array.remove();
    }

    @Override
    public void push(T el) {
        array.add(el);
    }

    @Override
    public T peek() {
        returnarray.get(size() - 1); }}Copy the code

Push of the stack: The insertion of an element to the top of the stack, i.e., the blue element (note: the stack specification —- all constraints except the top of the stack are invisible and inoperable)

Look at the top element of the stack:

Pop of stack: To pop the top element of the stack out of the stack

2. Single linked list stack structure:
/** * Author: Zhang Feng Jiete Lie * Time: 2018/11/230017 :22:40 * Email: [email protected] * Description: */ public class SingleLinkedStack<E> implements IStack<E> {private SingleLinkedChart<E> mSingleLinkedChart; publicSingleLinkedStack() {
        mSingleLinkedChart = new SingleLinkedChart<>();
    }


    @Override
    public int size() {
        return mSingleLinkedChart.size();
    }

    @Override
    public int capacity() {
        return mSingleLinkedChart.size();
    }

    @Override
    public boolean isEmpty() {
        return mSingleLinkedChart.isEmpty();
    }

    @Override
    public void push(E el) {
        mSingleLinkedChart.add(el);
    }

    @Override
    public E pop() {
        return mSingleLinkedChart.remove();
    }

    @Override
    public E peek() {
        returnmSingleLinkedChart.get(0); }}Copy the code

If you think the stack is very simple, you can study [with stack balance symbol], [postfix expression], [recursive method call] these three are the classic application of the stack, the next opportunity to write a special to describe, this article is limited to the implementation of the stack structure, do not extend.

Three, linked list and array table stack comparison

1. Array table stack: ArrayChartStack test
Method \ quantity 1000 times 10000 times 10 w 100 w 1000 w
push 0.0011 seconds 0.0034 seconds 0.0158 seconds 0.0726 seconds 1.020 seconds
pop 0.0006 seconds 0.0025 seconds 0.0085 seconds 0.0280 seconds 0.1751 seconds
2. Linked list stack: SingleLinkedStack test
Method \ quantity 1000 times 10000 times 10 w 100 w 1000 w
push 0.0005 seconds 0.0027 seconds 0.0075 seconds 0.3817 seconds 3.1550 seconds
pop 0.0004 seconds 0.0022 seconds 0.0050 seconds 0.0223 seconds 0.1267 seconds

Visible lower number list seem to have more advantages, for a start table array will often expansion, the expansion of the number of the lower Under the high frequency of 1000 w time array list will seem good, but it may take up more space Because if the super-popular around 1000 w, 500 w blank space, the list is not, It’s a little slower by two seconds, but it’s still acceptable that the stack structure of the linked list implementation is better overall.

Four, view drawing method

This feels rather short, so let me draw a picture

1. Drawing ideas:

At the beginning, it was very frustrating, because the stack could not access the elements at the top of the stack, so it was impossible to draw the elements at the bottom of the stack using a single stack method. I also wanted to use the stack method to test, so I made a compromise, and used an ArrayList to synchronously hold the stack, and drew both the entry and popup animations. In order to distinguish, I used two ValueAnimators to control, and the member variables below

private Point mCoo = new Point(300, 200); // Private grid Picture; // Canvas element private Path mPath; // Private Paint mPaint; // Private Paint mTxtPaint; // Private Paint mBoderPaint; // Private Paint mCtrlPaint; Private IStack<StackBox<E>> mStackBoxes = new ArrayChartStack<>(); Private IStack<StackBox<E>> mStackBoxes = new SingleLinkedStack<>(); Private List<StackBox<E>> mUnSeeStackItemBox = new ArrayList<>(); private OnCtrlClickListener<StackView<E>> mOnCtrlClickListener; Private ValueAnimator mInAnimator; Private ValueAnimator mOutAnimator; Private Boolean canAdd =true; Private static final int OFFSET_OF_TXT_Y = 10; private static final int OFFSET_OF_TXT_Y = 10; Private static final Point[] CTRL_POS = new Point[]{new Point(-120, 100),// add new Point(-120, 100) 300 + 50),// remove new Point(-120, 500 + 100),// check the top of the stack}; Private static int[] CTRL_COLOR = new int[]{// add 0xff1EF519,// add 0xffB946F4,// delete 0xff2992F2,// Check the stack top}; Private static final String[] CTRL_TXT = new String[]{// Control button text"push"/ / added"pop"/ / removed"peek",// check the top of the stack}; private static final int CTRL_RADIUS = 70; Private static final int BOTTOM_OF_STACK = 700; Private static final int WIDTH_OF_STACK = 300; Private static final int STACK_X = 400; Private static final int STACK_Y = 100; Private static final int LEN_ABOVE_STACK = 200; Private int mCurStackTopLine = BOTTOM_OF_STACK; // Top line of the current stackCopy the code
2. Initialize some members
private void init() {// Initialize the main paintbrush. MPaint = new Paint(paint.anti_alias_flag); mPaint.setColor(Color.BLUE); mPaint.setStrokeWidth(5); mPaint.setTextAlign(Paint.Align.CENTER); mPaint.setTextSize(50); // Initialize the main Path mPath = new Path(); // Initialize the text brush mTxtPaint = new Paint(paint.anti_alias_flag); mTxtPaint.setColor(Color.WHITE); mTxtPaint.setTextAlign(Paint.Align.CENTER); mTxtPaint.setTextSize(50); MBoderPaint = new Paint(paint.anti_alias_flag); mBoderPaint.setColor(Color.BLACK); mBoderPaint.setStrokeWidth(4); mBoderPaint.setStyle(Paint.Style.STROKE); mGridPicture = HelpDraw.getGrid(getContext()); // Initialize the ball button paintbrush mCtrlPaint = new Paint(paint.anti_alias_flag); mCtrlPaint.setColor(Color.RED); mCtrlPaint.setTextAlign(Paint.Align.CENTER); mCtrlPaint.setTextSize(30); ValueAnimator mInAnimator = valueAnimator.offloat (0, 1); mInAnimator.setRepeatCount(-1); mInAnimator.setDuration(2000); mInAnimator.setRepeatMode(ValueAnimator.REVERSE); mInAnimator.setInterpolator(new LinearInterpolator()); mInAnimator.addUpdateListener(animation -> { updateBall(); Invalidate (); }); MOutAnimator = valueAnimator.offloat (0, 1); // Initialize the time stream ValueAnimator-- Remove mOutAnimator = valueAnimator.offloat (0, 1); mOutAnimator.setRepeatCount(-1); mOutAnimator.setDuration(2000); mOutAnimator.setRepeatMode(ValueAnimator.REVERSE); mOutAnimator.setInterpolator(new LinearInterpolator()); mOutAnimator.addUpdateListener(animation -> { updateOutBall(); Invalidate (); }); }Copy the code
3. Three core operations:

When joining the ArrayList, the x and y coordinates of StackBox are initially calculated based on the number of elements: stackBox.y = STACK_Y – BOTTOM_OF_STACK + Cons.BOX_HEIGHT * mStackBoxes.size(); When the add animation starts, it is disabled until the animation is paused

/** * @param data */ public void addData(E data) {if(! canAdd) {return; } StackBox<E> stackBox = new StackBox<>(0, 0); stackBox.vY = 18; stackBox.data = data; stackBox.color = ColUtils.randomRGB(); stackBox.x = STACK_X; stackBox.y = STACK_Y - BOTTOM_OF_STACK + Cons.BOX_HEIGHT * mStackBoxes.size(); mStackBoxes.push(stackBox); mUnSeeStackItemBox.add(stackBox); StackBox box = mStackBoxes.peek(); Box-x = STACK_X; box.y = STACK_Y - LEN_ABOVE_STACK; mInAnimator.start(); canAdd =false; } /** * view the top element */ public EfindData() {
    if (mStackBoxes.isEmpty()) {
        Toast.makeText(getContext(), "Stack is empty", Toast.LENGTH_SHORT).show();
    }
    if (mStackBoxes.size() > 0) {
        return mStackBoxes.peek().data;
    }
    returnnull; } /** * Stack */ public voidremoveData() {
    if (mStackBoxes.isEmpty()) {
        Toast.makeText(getContext(), "Stack is empty", Toast.LENGTH_SHORT).show();
    }
    if (mStackBoxes.size() > 0) {
        mOutAnimator.start();
        canAdd = false; }}Copy the code
4. Push and exit animation

This is a key step in dynamically determining and correcting the position of the top of the stack

/** * Push animation */ private voidupdateBall() {
    if (mStackBoxes.size() > 0) {
        StackBox ball = mStackBoxes.peek();
        ball.x += ball.vX;
        ball.y += ball.vY;
        if(ball.y > mCurStackTopLine) { ball.y = mCurStackTopLine; mInAnimator.pause(); mCurStackTopLine = BOTTOM_OF_STACK - (mUnSeeStackItemBox.size()) * Cons.BOX_HEIGHT; // Update the stack top line canAdd =true; } /** * Private voidupdateOutBall() {
    if (mStackBoxes.size() > 0) {
        StackBox ball = mStackBoxes.peek();
        ball.x += ball.vX;
        ball.y -= ball.vY;
        if (ball.y < -Cons.BOX_HEIGHT) {
            mStackBoxes.pop();
            mUnSeeStackItemBox.remove(mUnSeeStackItemBox.size() - 1);
            mOutAnimator.pause();
            mCurStackTopLine += Cons.BOX_HEIGHT;
            canAdd = true; }}}Copy the code
5. Core drawing method:
/** @param canvas */ private void dataView(canvas canvas) {mPath. MoveTo (STACK_X, STACK_Y); mPath.rLineTo(0, BOTTOM_OF_STACK); mPath.rLineTo(WIDTH_OF_STACK, 0); mPath.rLineTo(0, -BOTTOM_OF_STACK); canvas.drawPath(mPath, mBoderPaint); mPaint.setColor(Color.GRAY);for (StackBox<E> box : mUnSeeStackItemBox) {
        canvas.drawRect(box.x, box.y,
                box.x + WIDTH_OF_STACK, box.y + Cons.BOX_HEIGHT,
                mPaint);
        canvas.drawRect(box.x, box.y,
                box.x + WIDTH_OF_STACK, box.y + Cons.BOX_HEIGHT,
                mBoderPaint);
        canvas.drawText((String) box.data, box.x + WIDTH_OF_STACK / 2,
                box.y + Cons.BOX_HEIGHT / 2 + 5, mTxtPaint);
    }
    mPaint.setColor(Color.BLUE);
    if(mStackBoxes.size() > 0) { StackBox<E> peek = mStackBoxes.peek(); canvas.drawRect(peek.x, peek.y, peek.x + WIDTH_OF_STACK, peek.y + Cons.BOX_HEIGHT, mPaint); canvas.drawText((String) peek.data, peek.x + WIDTH_OF_STACK / 2, peek.y + Cons.BOX_HEIGHT / 2 + 5, mTxtPaint); }}Copy the code

Further updates in this series link collection :(dynamic updates)

  • Visible data structures: the introduction to the Android version
  • Array Tables for Android (Data Structures)
  • Android Array Table (View Section)
  • Visible data structure Android version of the single linked list
  • Visible data structure Android version of the double Linked list
  • Visible data structure stack for Android version
  • Visible data structure of the Android version of the queue article
  • Visible data structure Android version of the binary search tree
  • More data structures – more on that later

Postscript: Jie wen standard

2. Growth records and errata of this paper
Program source code The date of note
V0.1 – making 2018-11-23 Visible data structure The Android version of the stack structure implementation
3. More about me
Pen name QQ WeChat hobby
Zhang Feng Jie te Li 1981462002 zdl1994328 language
My lot My Jane books I’m the nuggets Personal website
4. A statement

1—- this article is originally written by Zhang Feng Jetelie, please note 2—- all programming enthusiasts are welcome to communicate with each other 3—- personal ability is limited, if there is any error, you are welcome to criticize and point out, will be modest to correct 4—- See here, I thank you here for your love and support