Aiti Tribe Story Collection (25): Analysis of Chain Storage Stack and Code Implementation

[51CTO.com original article] Xiao Yao graduated from the Computer Science Department of Chongqing University of Posts and Telecommunications. Currently, he is a small Android mobile application development programmer. He loves life and his girlfriend. When he is free, he also likes to play games and study hard. His current life goal is to make money, buy a house, a car, and marry a wife.

[[199073]]

Xiaoyao·Android Development

Introduction to stacks and queues

Friends who have learned the basics of computer programming know that the most common data structures in computers are stacks and queues. The reason why this linear list structure is so common is that their simple but powerful functional characteristics are the basis of many algorithms. When Xiao Yao was in a junior year in Beijing, the interviewer asked him a question during an internship interview, "How to use a stack to implement a queue?" At that time, he fell into a misunderstanding, thinking that the stack the interviewer was talking about was a stack. Due to the first-in-last-out characteristics of the stack, it was conceptually impossible for a stack to complete the function of the queue. As the saying goes, if one stack doesn't work, then two stacks. OK, you are right, at least two stacks are indeed needed. Let's get back to the point. Since stacks and queues are so widely used, how can we implement them through code? Many students may say, isn't this simple? Use a collection or array, so easy! So, what if collections or arrays are not allowed to be used in order to improve execution efficiency? Next, Xiao Yao will analyze it for everyone!

Chain storage stack analysis

I won't explain the concept of stack here. If you don't know, please search Baidu. There are many ways to implement the first-in-last-out feature. As the title says, we will implement chain storage here. What is chain storage? As shown in the following figure:

The basic unit of chain storage is Node. In a node, it is divided into data area and pointer field. The pointer field points to the next node to connect the nodes. Due to the characteristics of the chain, inserting and deleting a node in the chain (except the head and tail of the chain) is relatively expensive, but it is very suitable for implementing stacks or queues. For the stack structure, methods such as pushing and popping data and judging whether the stack bottom has been reached are essential.

Code Implementation

Next, let's see how to implement it with Java code:

 /**
 * Created by lxh on 2017/8/1.
 * QQ-632671653
 * Custom chain storage stack
 */
 public class LinkStack<T> {
 private Node<T> top = new Node<>(); //Initialize the top node of the stack
 /**
 * Data stack operation
 * @param data
 */
    public void push(T data) {
        top = new Node<>(data, top);
        System.out.println(top.toString());
 }

 /**
 * Data pop operation
 * @return
 */
 public T pop() {
 T result = top.data;
 if (top.hasNext()) {
 top = top.next;
 }
 return result;
 }
 //Use internal classes to build nodes
 private class Node<T> {
 T data; //Use generics to define data domains
 Node<T> next; //Define the next node
 /**
 * Initialize the bottom of the stack in the no-argument constructor and add an end sentinel to the stack
 */
 Node() {
 data = null;
 next = null;
 }
 /**
 * Construct each added node object through the parameter construction method
 * @param data
 * @param next
 */
        public Node(T data, Node<T> next) {
 this.data = data;
 this.next = next;
 }
 /**
 * Determine whether the stack has reached the bottom
 * @return
 */
 boolean hasNext() {
            return data != null && next != null;
 }
 @Override
        public String toString() {
 return "Node{" +
                    "data=" + data +
                    ", next=" + next +
 '}';
 }
 }
 }

As you can see from the code, generics are used here to ensure the universality of the data type pushed into the stack. The nodes are constructed in the form of inner classes. Because of their privacy, data security can be guaranteed. Students with poor basics may be confused and don't quite understand where this chain is linked to, so Xiaoyao prints out the information in the stack during the push operation. I believe you will understand it at a glance. As shown below:

I believe everyone understands from the infographic that this chain storage stack is formed by recursively adding node objects to the node object to form a link between nodes, which is reflected in the character set as layers of nested objects (because it is written in Java language and there is no pointer in C, so this method is used to replace the pointer). Through the sentinel of the end node, when the data set is null when popping the stack, it can be judged that the data in the stack has been popped.

【Written in ***】

There is a saying among colleagues: Don't reinvent the wheel. But Xiaoyao thinks that even if you don't need to reinvent the wheel, you still have to understand how the wheel is made. If you only know how to call the API, you will lose your competitiveness.

If you are also willing to share your story, please join the 51CTO developer QQ exchange group 542270018 and contact the group owner. We look forward to your wonderful story!

[51CTO original article, please indicate the original author and source as 51CTO.com when reprinting on partner sites]