preface

In the previous two articles, we learned about arrays and linked lists in linear lists. Arrays and linked lists are the most basic data structures. Many data structures are implemented based on data or linked lists. So today we are going to look at a very simple data structure called the stack. The use of stack is very extensive, such as our Java function call, browser forward and backward functions will use the stack.

What is a stack

So let’s draw a picture of what the stack looks like. As shown below:

As you can see from the diagram, the stack is somewhat special. Operations on the stack are restricted to one end (the top), that is, data operations are not allowed in the middle of the stack, but only at the top of the stack (i.e. inserting and deleting data).

Think: What’s the use of a “restricted” stack?

A particular data structure must be used in a particular way. Stacks are less flexible than arrays or linked lists (data can only be manipulated on one side of the stack), but they can be very efficient when adding or deleting data because only one side of the stack is involved.

How do we understand stacks? In fact, it is very simple, a word can be summarized the characteristics of the stack: advanced after out, commonly known as “eat too much vomit”. Ha ha ~

Basic stack operations

Stacks are implemented in different ways, arrays based stacks are called sequential stacks. A stack based on a linked list implementation is called a chain stack. No matter how the stack is implemented, the principle is the same, don’t worry!

There are only two operations on the stack: push and pop.

  • Order of the stack

Let’s first implement a sequential stack based on an array, the code is as follows:

public class MyStack<E> {
    private Object[] data = null;  / / array
    private int maxSize = 0;  / / stack capacity
    private int top = -1;  // Top of stack pointer

    // Initialize the constructor
    MyStack(int initialSize) {
        if (initialSize >= 0) {
            this.maxSize = initialSize;
            data = new Object[initialSize];
            top = -1;
        } else {
            throw new RuntimeException("The initial size cannot be less than 0:"+ initialSize); }}// The default stack size of the initializer is 10
    public MyStack(a) {
        this(10);
    }

    // Push operation
    public boolean push(E e) {
        // First check if the stack is full
        if (top == maxSize - 1) {
            / / capacity
            resize();
        } 
        data[top] = e;
        top++;
        return true;
    }

    // Unstack
    public E pop(a) {
        // First check if the stack is empty
        if (top == -1) {
            throw new RuntimeException("Stack empty");
        } else {
            // Maintain the top pointer after returning the top element
            return(E) data[top--]; }}// View the top element of the stack
    public E peek(a) {
        if (top == -1) {
            throw new RuntimeException("Stack empty");
        } else {
            // The top of the stack element is not removed, so there is no need to maintain the top pointer
            return(E) data[top]; }}// Check whether the stack is empty
    public boolean isEmpty(a) {
        return maxSize == 0;
    }
    
    // Perform capacity expansion
    public void resize(a) {
        // Create a new array
        Object[] newArray = new Object[data.length * 2];
        System.arraycopy(data, 0, newArray, 0, data.length); data = newArray; }}Copy the code

In a sequential stack, the first element of the array is at the bottom of the stack and the last element is at the top. When top=-1, the stack is empty.

MaxSize is increased by one each time new data is pushed onto the stack, and decreased by one each time an element is removed from the stack pop. Because it is an implementation of the underlying array, sequential stacks involve a scaling situation.

  • Chain stack

Let’s look at a linked stack based on a linked list, the code is as follows:

public class MyStack<E> {
    StackNode<E> top = null; / / stack

    private class StackNode<E>{
        E data;
        StackNode next;
        StackNode(E data) {
            this.data=data; }}/** * push * First assign next to the data to be pushed to the top of the stack and then point the top pointer to the node to be pushed in@param data
     */
    public void push(E data) {
        StackNode<E> newNode = new StackNode<E>(data);
        newNode.next = top;
        top = newNode;
    }

    /** * out of the stack *@return* /
    public E pop(a) {
        if(this.isEmpty()) {
            throw new RuntimeException("Stack empty");
        }
        E data = top.data;
        top = top.next;
        return data;
    }

    /** * view the top element *@return* /
    public E peek(a) {
        if(isEmpty()) {
            throw new RuntimeException("Stack empty");
        }
        return top.data;
    }

    // Check whether the stack is empty
    public boolean isEmpty(a) {
        return top == null; }}Copy the code

In a chained stack, the head of a single linked list is the top of the stack, because the stack is advanced and out, so there is no need for a head node. Whenever new data is pushed onto the stack, the new node points to the top of the stack, and then the top points to the new node. Similarly, when deleting an element from the stack pop, only the top pointer on the stack points to the next pointer on the top element to complete the deletion.

conclusion

Stack as a restricted linear table, only allowed to operate on the top of the stack, that is, the so-called: in, out, last in, first out. In both sequential and chained stacks, data can be added or deleted only at the top of the stack, so the time complexity is O(1). Searching for data requires global traversal, so the time complexity is O(n). Sequential stack is based on array implementation, urine and feces have been fixed at initialization, subsequent expansion needs to be considered, while linked stack is based on linked list implementation, no expansion needs to be considered.