Implementation of Java data structure and algorithm stack

This is the second chapter on Java data structures and algorithms. Starting from this chapter, we will learn about the design and implementation of stack in the future. The following are the relevant knowledge points of this chapter:

Design and implementation of sequential stack design and implementation of chain stack application of stack

Abstract data type of stack

   stack is a simple data structure used to store data, which is somewhat similar to linked list or sequential table (collectively referred to as linear table). The biggest difference between stack and linear table is the operation of data access. We can think that stack is a special linear table, and its insertion and deletion operations are only allowed at one end of the linear table. Generally speaking, The allowed end is called the top of the stack, the non operable end is called the bottom, the operation of inserting elements is called push, and the operation of deleting elements is called pop. If there are no elements in the stack, it is called an empty stack. The structure of the stack is as follows:

From the figure, we can see that the stack can only access elements from the top of the stack. At the same time, the elements that enter first come out later, and the top of the stack always points to the top element in the stack. Here we can give the formal definition of stack: stack is an ordered and special linear table. Insertion and deletion operations can only be performed at one end of the table (called the top of the stack, which always points to the top of the stack element). The last inserted element will be deleted first. Therefore, stack is also called last in first out (LIFO) or first in last out (Filo) linear table. The basic operations of stack: create stack, empty judgment, stack entry, stack exit, obtain stack top elements, etc. note that the stack does not support deletion and insertion of the specified position. The interface stack is declared as follows:

Design and implementation of sequential stack

   sequence stack, as its name implies, is a stack implemented by sequence table. The internal of sequence stack is based on sequence table to realize the access operation of elements. Of course, we can also use internal array to realize sequence stack. Here, we use internal data group to realize stack. As for the stack implementation based on sequence table, it will be provided by source code. Here, a sequential stack is declared first, and its code is as follows to implement stack and serializable interfaces:

The peek operation process for obtaining the value of the top element of the stack is shown in the following figure (only the value is obtained without deletion):

The above is the operation of obtaining the top element of the stack. The code is as follows:

The process of adding elements from the stack is as follows (update the top point of the stack):

The above is the stack operation, and the code is as follows:

The process of pop-up stack top elements is as follows (delete and obtain values):

The above is the stack out operation, and the code is as follows:

So far, the main operations of the sequence stack have been implemented. Is it very simple? Indeed, the main operations of the stack are like this. Of course, we can also implement the sequence stack based on myarraylist introduced in the previous article. This is also relatively simple, and the code will be provided later. Here, there is no more explanation or bad annoyance

Design and implementation of chain stack

   after understanding the sequential stack, let's take a look at the chain stack. The so-called linked stack is a stack with chain storage structure. Since we operate on the top end of the stack, we use the single linked list (not the leading node) as the basis to directly realize the main operations such as adding, obtaining and deleting the stack. The operation process is as follows:

As can be seen from the figure, whether inserting or deleting, the direct operation is the head of the linked list, that is, the top element of the stack. Therefore, we only need to use the single linked list without the leading node. The code implementation is as follows. It is relatively simple, but there is more analysis:

The above is the whole content of this article. I hope it will be helpful to your study, and I hope you can support programming tips.