This article will introduce an important data structure – stack. Like linked lists and arrays mentioned before, it is also a linear data structure, but in this structure, we can only access the newly added data. A stack is like a stack of books. When we get a new book, we put it on the top of the stack. When we get a book, we can only take the new book from the top.

The stack

The concept diagram of the stack is shown above, and only data Blue is stored in the stack. When adding data to the stack, the new data is placed at the top.

Then, we add data Green to the stack. The operation of adding data to the stack is called pushing.

Next, the data Red is pushed.

When data is fetched from the stack, it is fetched from the top, the most recent data, which is Red. The operation of fetching data from a stack is called making a stack.

If you do another stack removal, you get Green.

Last In First Out (LIFO) is a Last In First Out (LIFO) structure.

Like linked lists and arrays, data is arranged in a linear manner, but data can only be added and removed at one end of the stack, and data can only be accessed at the top. To access data in the middle, the target data must be moved to the top of the stack by removing data from the stack.

After introducing the basic knowledge of the stack, the next example is given. For example, we are reading the article of the public number. I will take the wechat subscription number as an example.

How do you understand stacks?

First you open the subscription number, is a list of public numbers, then you click a public number – Wu Peixuan, into the corresponding article list interface, then you click the article – what is the array? , enter the article details page.

Ok, now what do you do if you want to return the subscription number? Swipe right twice, first to the article list screen and second to the subscription number screen.

If you want to go back to the subscription number screen (which is at the bottom of the stack), you have to go out of the stack twice to remove the first two screens.

The realization of the stack

Now that you have a basic understanding of the stack, the stack consists of two operations, push and push, that is, insert data at the top of the stack and remove data from the top of the stack. It’s not enough to understand, but to implement a stack, so let’s take a look at how to implement a stack in code.

The stack has two types of storage structure, namely sequential storage and chained storage, that is, the stack can be implemented by arrays or linked lists. A stack implemented in arrays is called a sequential stack, and a stack implemented in linked lists is called a chained stack.

Let’s take a look at what an array stack looks like. The implementation looks like this:

So I first use the Java language to achieve the following sequential stack, the code is as follows:

Public class ArrayStack {/** * array */ private String[] items; /** * private int count; /** * stack size */ private int n; ** @param n */ public ArrayStack(int n) {this.items = new String[n]; this.n = n; this.count = 0; } /** * push ** @param item * @return */ public Boolean push(String item) { if (count == n) { return false; } // place item at subscript count, and count + items[count] = item; ++count; return true; Public String pop() {if (count == 0) {return null; String TMP = items[count-1]; String TMP = items[count-1]; --count; return tmp; }}Copy the code

The other is the chain stack, which is implemented as shown in the following figure:

Then use the linked list to implement the stack, the code is as follows:

@author wupx * @date 2020/02/11 */ public Class LinkedListStack {private Node top = null; Public void push(int value) {Node newNode = newNode (value, null); /** @param value */ public void push(int value) {Node newNode = newNode (value, null); If (top! = null) { newNode.next = top; } top = newNode; Public int pop() {if (top == null) {return -1; } int value = top.data; top = top.next; return value; } public void printAll() { Node p = top; while (p ! = null) { System.out.print(p.data + " "); p = p.next; } System.out.println(); } private static class Node { private int data; private Node next; public Node(int data, Node next) { this.data = data; this.next = next; } public int getData() { return data; }}}Copy the code

Now that we have a deeper understanding and practice of the stack, let’s take a look at its space complexity and time complexity.

Whether it’s a sequential stack or a chained stack, all we need to store data is an array of size N. Only one or two temporary variable storage Spaces are required during loading and unloading, so the space complexity is O(1).

Loading and unloading only affect the last element, not the whole movement of other elements, so whether implemented as an array or a linked list, the time complexity of loading and unloading is O(1).

conclusion

The stack is a linear logical structure that only supports loading and unloading operations, following the last in, first out principle (FILO). The stack can be implemented by array or linked list, and the time complexity of loading and unloading is O(1) regardless of array or linked list.

reference

My First Algorithm Book

Diagram of algorithms