One, foreword

In this article, we will focus on the application of linear structures: stacks and queues

If there is something wrong, I hope you can understand and correct it. If there is a better way to understand, I hope you can leave a message in the comments, so that you can learn to learn ~

Data structure [stack] is that simple

2.1 Introduction to data structure [Stack]

The stack length of the data structure looks like this:

It’s actually pretty straightforward to think of a stack as a box

• Putting things into bins is called pushing
• Getting things out of boxes is called making stacks
• The bottom of the box is called the bottom of the stack
• The top of the box is called the top of the stack

When it comes to the characteristics of the stack, there must be a classic phrase to summarize: LIFO, Last In First Out.

• If you want to take out the apples from the bottom of the box, you have to take out the apples from the top of the box

2.2 Data structure [stack] code implementation

There are two types of stacks:

• Static stack (array implementation)
• Dynamic stack (linked list implementation)

From the last article to write a linked list I realized how bad my algorithm is, ordinary single linked list operation can also put me around the dizzy.

Because my linked list is not very familiar, stack is not very difficult, so I use the linked list to create dynamic stack!

Since we are using linked lists, let’s take the code from the previous article:

public class Node {

    / / data domain
    public int data;

    // pointer field, pointing to the next node
    public Node next;

    public Node(a) {}public Node(int data) {
        this.data = data;
    }

    public Node(int data, Node next) {
        this.data = data;
        this.next = next; }}Copy the code

To use a linked list to represent a stack, this time there are two Pointers:

• To the top of the stack
• The bottom of the stack

public class Stack {

    public Node stackTop;
    public Node stackBottom;

    public Stack(Node stackTop, Node stackBottom) {
        this.stackTop = stackTop;
        this.stackBottom = stackBottom;
    }

    public Stack(a) {}}Copy the code

2.2.1 into the stack

The top of the stack points to the new node, and the top points to the newly added node

    /** * push **@paramStack stack *@paramValue Specifies the element to be pushed */
    public static void pushStack(Stack stack, int value) {

        // Encapsulate data into nodes
        Node newNode = new Node(value);


        // The node that was pointed to at the top of the stack is pointed to by the new node
        newNode.next = stack.stackTop;

        // The top pointer points to the new node
        stack.stackTop = newNode;

    }
Copy the code

2.2.2 traversal stack

As long as the pointer to the top element does not point to the bottom of the stack, the traversal result is always printed:

    /** * traverses the stack (prints as long as the top pointer does not point to the bottom pointer) **@param stack
     */
    public static void traverse(Stack stack) {
        Node stackTop = stack.stackTop;

        while(stackTop ! = stack.stackBottom) { System.out.println("Follow public account: Java3y:"+ stackTop.data); stackTop = stackTop.next; }}Copy the code

Testing:

    public static void main(String[] args) {

        // Initialize stack (no element)
        Stack stack = new Stack(new Node(), new Node());

        // The top and bottom of the stack are identical
        stack.stackBottom = stack.stackTop;

        / / points to null
        stack.stackTop.next = null;


        / / into the stack
        pushStack(stack, 3);
        pushStack(stack, 4);
        pushStack(stack, 5);

        traverse(stack);

    }
Copy the code

Results:

This is in line with the advanced after the characteristics of ~

2.2.3 Check whether the stack is empty

Very simple, as long as the top and bottom of the stack point to the same, then the stack is empty

    /** * Checks whether the stack is empty **@param stack
     */
    public static void isEmpty(Stack stack) {
        if (stack.stackTop == stack.stackBottom) {

            System.out.println(Java3y----> The stack is empty);
        } else {

            System.out.println(Java3y----> This stack is not empty); }}Copy the code

2.2.4 the stack

1. Check to see if the stack is empty before unloading.
2. Assigns a pointer to the top of the stack (pointing to the next node) to the top of the stack (finishing the stack)

    /** * out of the stack (the top pointer to the next node) *@param stack
     */
    public static void popStack(Stack stack) {

        // The stack must be empty before it is unloaded
        if(! isEmpty(stack)) {// Top of stack element
            Node top = stack.stackTop;

            // The top pointer points to the next node
            stack.stackTop = top.next;

            System.out.println("Java3y----> Unstack elements are:"+ top.data); }}Copy the code

Test out stack:

Multiple exit:

2.2.5 empty stack

When learning C, you need to free up memory resources, but Java doesn’t need to, so the top of the stack points to the bottom of the stack, so you empty the stack

    /** * clear the stack *@param stack
     */
    public static void clearStack(Stack stack) {

        stack.stackTop = null;
        stack.stackBottom = stack.stackTop;
    }
Copy the code

It’s that simple

The queue length of the data structure looks like this:

In fact, the queue is very easy to understand, we can think of the queue as children queue

• The children at the end of the line have arrived at the designated place –> get out of the line
• New children have joined the team

In contrast to stacks, queues have the following characteristics: first in, first out

• The children who queue up first will definitely get the meal first!

Queues are also divided into two types:

• Static queue (array implementation)
• Dynamic queue (linked list implementation)

This time I’m going to implement static queues using arrays. It is worth noting that static queues are often implemented and we are made into circular queues

The advantage of circular queuing is that you don’t waste memory resources!

3.1 Data structure [queue] code implementation

This time we are using arrays to implement static queues, so we can design it like this:

public class Queue {


    / / array
    public int [] arrays;

    // points to the first valid element
    public int front;

    // Point to the next element of valid data (i.e. point to invalid data)
    public int rear;

}
Copy the code

From the above design we can see that rear does not point to the last valid element, which is very convenient in a loop queue! Because this design allows us to distinguish between the front and the back of the queue.

Because we’re a circular queue, front and rear are going to change a lot, so we have to keep front and rear in the same range, otherwise we’re going to exceed the length of the queue.

There’s an algorithm: Rear = (Rear +1)% array length

• Let’s say that rear is 2, and the length of the array is 6, and if I move one bit behind it is 3, soRear = (rear+1) % 6That’s still 3

3.1.2 Initializing queues

At this point, the queue is empty, and 6 lengths are allocated to the array (only 5 real numbers, rear points to an invalid position).

    public static void main(String[] args) {

        // Initialize the queue
        Queue queue = new Queue();

        queue.front = 0;
        queue.rear = 0;
        queue.arrays = new int[6];
        
    }
Copy the code

3.1.3 Check whether the queue is full

If the rear and front Pointers are next to each other, then the queue is full

    /** * Check whether the queue is full, and the front and rear Pointers are next to each other@param queue
     * @return* /
    public static boolean isFull(Queue queue) {
        if ((queue.rear + 1) % queue.arrays.length == queue.front) {

            System.out.println("Java3y-- > The queue is full!");
            return true;
        } else {
            System.out.println(Java3y-- > The queue is not full at this time!);
            return false; }}Copy the code

3.1.4 team

1. Determines whether the queue is full
2. The entry value is inserted into the rear pointer at the end of the queue.
3. Rear pointer moves (again pointing to invalid element position)

    /** * join the team **@param queue
     */
    public static void enQueue(Queue queue,int value) {

        // The queue must not be full to join
        if(! isFull(queue)) {// Insert the new element at the end of the queue
            queue.arrays[queue.rear] = value;

            // The rear node moves to the new invalid element position
            queue.rear = (queue.rear + 1) % queue.arrays.length; }}Copy the code

3.1.5 traversal

As long as the front node doesn’t point to the rear node, you can always output

    /** * traverses the queue *@param queue
     *
     */
    public static void traverseQueue(Queue queue) {

        // The front position
        int i = queue.front;

        while(i ! = queue.rear) { System.out.println("Java3y-- >" + queue.arrays[i]);

            / / move the front
            i = (i + 1) % queue.arrays.length; }}Copy the code

When queue is not full:

The queue is full and cannot be inserted:

3.1.6 Checking whether the queue is empty

As long as the rear and front Pointers point to the same place, the queue is empty

    /** * if the front and rear Pointers are equal, the queue is empty@param queue
     * @return* /
    public static boolean isEmpty(Queue queue) {
        if (queue.rear  == queue.front) {
            System.out.println(Java3y-- > This queue is empty!);
            return true;
        } else {
            System.out.println("Attention public number: Java3y-- > queue is not empty!");
            return false; }}Copy the code

3.1.7 the team

The logic of getting out is simple:

1. Checks whether the queue is null
2. If it is not null, the queue is out, as long as the front pointer moves back.

 	/** ** out of line **@param queue
     */
    public static void outQueue(Queue queue) {

        // Check whether the queue is null
        if(! isEmpty(queue)) {// Only when there is no space
            int value = queue.arrays[queue.front];
            System.out.println(Java3y-- > < span style = "max-width: 100%; clear: both; + value);

            // move the front pointer back
            queue.front = (queue.front + 1) % queue.arrays.length; }}Copy the code

Results:

Four,

Stack and queue applications of data structures are very, very many, and this is only the most simple entry, understanding is not difficult.

• Stack: First in last out
• Queue: First in, first out

About the temporary data structure that I am here so far, all simple into the door, meet after more complicated continue to open new articles to write ~ after all where it is not enough, also can’t understand something deeper ~ data structure, it is necessary to wait until the collection will be to review it, or meet new, complex, will also continue to learn…

Those of you who want to dig deeper into data structures should check out the books

If the article has the wrong place welcome to correct, everybody exchanges with each other. Students who are used to reading technical articles on wechat and want to get more Java resources can follow the wechat public account :Java3y