The software world is a projection of the real world.
The introduction
Most of the concepts in the software world are not created out of thin air; most of them are abstracted from the real world. Just like the “stack” discussed in this article, there is a model in daily life, such as a stack of bowls, the first one is placed at the bottom, like the following:
We commonly used function calls to each other, for example, Java always begins with a main function, if our code is the main method to invoke a method, a method and invoke inside c method, c method and invoke d inside, so obvious is executed after completion of c d method method, c method is performed to execute a method. This execution model is also very stack like:
The stack
An overview of the
Here is a schematic of the stack:
When the ball in the above structure is abstracted as a node in the data structure, it also belongs to a linear table because the relationship between nodes is linear, and it is a linear table with limited operation because its operation can only be carried out at the same end. We call this type of linear table stack.
Now we give a definition of a stack: a stack is a special linear table in which all inserts and deletions are restricted to the same end of the table. The part of the stack where insertions and deletions are allowed is called the top, and the other end is called the bottom. When there are no elements in the stack, it is called an empty stack
The insertion operation of the stack is usually called pushing, pushing or pushing, and the deletion operation of the stack is usually called pushing out of the stack (POP). The first element that goes on the stack is at the bottom, the last element that goes on the stack is at the top, the first element that goes off the stack is at the top, and the last element that goes off the stack is at the bottom.
One might wonder why stacks should be introduced, or why not just arrays and linked lists? Why designate a data structure? In principle, the queue, tree and graph we talk about behind are also realized by array and linked list. Each kind of data structure corresponds to a special kind of data processing problem, such as stack specialized processing “advanced after out”, but also simplifies the program design ideas and reduces the scope of our thinking. Even if we implement the stack in arrays, we need to make sure that external callers don’t have to worry about subscripting out of bounds and adding or subtracting, so this is a new kind of array, but we just call it stacks.
Similar to a linear table, the basic operation of a stack is as follows:
- Stack initialization operation: create an empty stack table
- Stack empty detection: Determines whether the stack is empty
- Fetch top element: Fetch the value of the top element on the stack
- Push: Insert element E into S to make it the new top of the stack
- Pop stack: Remove the elements of stack S.
Many advanced languages, such as Java and C#, have built-in encapsulation of the stack data structure, so we can directly use the push and Pop operations of the stack without worrying about the implementation details of the stack. At the same time can also learn from the design ideas.
Arrays are called sequential stacks, and linked lists are called linked stacks. There are also subdivisions of the sequential stack. One way is to specify the size of the stack at the beginning, and when the stack exceeds the size, we can choose to call the last element at the bottom of the stack the element at the bottom of the stack. The second type is called dynamic stack, the size of the stack is dynamic, that is, dynamic expansion, when the upper limit of the stack, automatic expansion, the size of the stack basically depends on the size of memory.
Order of the stack
We try to use arrays to implement the following sequential Stack, in fact, the sequential Stack related design can also refer to the relevant design ideas in Java, let’s look at the Java Stack:
- Peek does not remove elements at the top of the stack
- Pop removes the top element and returns the top element
Java Stack design ideas:
- Stack nullify looks at the actual capacity of the array
- The push operation adds elements to the end of the array
- The peek operation returns the last element of the array
- The pop operation returns the last element of the array and moves the top element back one position
We can also let us build the sequential stack inherit our data structure and algorithm analysis (3) linear list SequenceList, so we do not need to rewrite the expansion operation again, only to implement the stack method can be. For the design of the method we can take a page from the Java Stack:
public class SequenceStack extends SequenceList {
public SequenceStack(a) {}public int push(int data){
add(data);
return data;
}
/** * returns the last element of the array, while moving the top element back one position *@return* /
public int pop(a){
if (size() == 0) {// Throw an exception
}
int data = peek();
remove(size() - 1);
return data;
}
public int peek(a){
if (size() == 0) {// Throw an exception
}
return get(size() - 1);
}
public boolean empty(a){
return size() == 0; }}Copy the codeChain stack
A chain storage stack is called a chain stack or chain stack. The chain stack is composed of nodes, and each node contains two parts: data field and pointer field. In the chain stack, the storage domain of each node is used to store each element in the stack, and the pointer domain is used to represent the relationship between elements. Something like this:
public class LinkedStack {
private Node top; // points to the top of the stack
private class Node{
private int data;
private Node next;
public Node(int data , Node next){
this.data = data;
this.next = next;
}
public int getData(a) {
return data;
}
public Node getNext(a) {
returnnext; }}public LinkedStack(a) {}/ * * *@param data
* @return* /
public int push(int data){
Node node = new Node(data,top);
top = node;
return data;
}
public int pop(a){
return peek();
}
public int peek(a){
int data = top.data;
top = top.next;
return data;
}
public boolean empty(a) {
return top == null; }}Copy the codeStack application example
System transformation
When converting decimal numbers to R numbers, we generally use decimal numbers and carry residuals, with the highest bit usually appearing last, just conforming to the last in, first out stack. For example, base 1024 to 8:
/** * base conversion *@param input
* @param decimal
*/
private static void binaryConversion(int input, int decimal) {
if(decimal == 0) {return;
}
Stack<Integer> stack = new Stack<>();
while(input ! =0){
stack.push(input % decimal);
input = input / decimal;
}
String result = "";
while(! stack.empty()){ result = result + stack.pop(); } System.out.println(result); }Copy the codeThe resources
- New Perspectives on Data Structure and Algorithm Analysis. Zhou Xingni, Ren Zhiyuan, Ma Yanzhuo, China Industry and Information Technology Publishing Group