This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money

“Welcome to the discussion in the comments section. The excavation authorities will draw 100 nuggets in the comments section after project Diggnation. See the event article for details.”

Introduction to the

The stack should be a very simple and useful data structure. The stack is characterized by fifo or LIFO.

In fact, many virtual machines are stacked. Because stack is very efficient in implementing function calls.

Today we are going to look at the structure and usage of the stack.

The composition of the stack

An ordered linear table in which only one end can be inserted or deleted. This end is called the top end.

To define a stack, we need to implement two functions, one is push, or push, and one is pop, or push.

Of course, we can also define some other helper functions, such as top: get the topmost node on the stack. IsEmpty: checks whether the stack isEmpty. IsFull: checks whether the stack isFull and so on.

Let’s look at the loading animation first:

Now look at the animation of the stack exit:

The realization of the stack

How can a stack with such functionality be implemented?

In general, stacks can be implemented as arrays or linked lists.

Use arrays to implement stacks

If we implement the stack using an array, we can use the last node of the array as the head of the stack. So when you push and pop the stack, you only need to change the last node in the array.

We also need a topIndex to hold the position of the last node.

The implementation code is as follows:

public class ArrayStack {

    // The array that actually stores the data
    private int[] array;
    / / the capacity of the stack
    private int capacity;
    // Stack header pointer position
    private int topIndex;

    public ArrayStack(int capacity){
        this.capacity= capacity;
        array = new int[capacity];
        // By default, topIndex is -1, indicating that the stack is empty
        topIndex=-1;
    }

    /** * whether the stack is empty *@return* /
    public boolean isEmpty(a){
        return topIndex == -1;
    }

    /** * If the stack is full *@return* /
    public boolean isFull(a){
        return topIndex == array.length -1 ;
    }

    public void push(int data){
        if(isFull()){
            System.out.println("Stack is full, do not insert.");
        }else{ array[++topIndex]=data; }}public int pop(a){
        if(isEmpty()){
            System.out.println("Stack is empty");
            return -1;
        }else{
            returnarray[topIndex--]; }}}Copy the code

Use dynamic arrays to implement stacks

In the example above, our array size is fixed. So the stack has a capacity limit.

What if we want to build an infinite stack?

Very simple, when we push, if the stack is full, we just expand the underlying array.

The implementation code is as follows:

public void push(int data){
        if(isFull()){
            System.out.println("Stack is full, Stack is expanded.");
            expandStack();
        }
        array[++topIndex]=data;
    }

    // Expand the stack. Here we simply use the multiply method
    private void expandStack(a){
        int[] expandedArray = new int[capacity* 2];
        System.arraycopy(array,0, expandedArray,0, capacity);
        capacity= capacity*2;
        array= expandedArray;
    }
Copy the code

Of course, there are many ways to expand an array, and in this case we’ve chosen multiplication.

Use linked lists to do this

Instead of using arrays, we can use linked lists to create stacks.

When using a linked list, we only need to operate on the head node of the list. Insert and delete are both handled by the head node.

public class LinkedListStack {

    private Node headNode;

    class Node {
        int data;
        Node next;
        //Node's constructor
        Node(intd) { data = d; }}public void push(int data){
        if(headNode == null){
            headNode= new Node(data);
        }else{
            Node newNode= newNode(data); newNode.next= headNode; headNode= newNode; }}public int top(a){
        if(headNode ==null) {return -1;
        }else{
            returnheadNode.data; }}public int pop(a){
        if(headNode ==null){
            System.out.println("Stack is empty");
            return -1;
        }else{
            int data= headNode.data;
            headNode= headNode.next;
            returndata; }}public boolean isEmpty(a){
        return headNode==null; }}Copy the code

The code address of this article:

learn-algorithm

This article is available at www.flydean.com/10-algorith…

The most popular interpretation, the most profound dry goods, the most concise tutorial, many tips you didn’t know waiting for you to discover!

Welcome to pay attention to my public number: “procedures those things”, understand technology, more understand you!