The stack in a data structure is not to be confused with the stack in Java, they are not the same thing. The stack in a data structure is a restricted linear table with a first-in, last-out, last-in, first-out feature because the stack only allows access to the last item of data, the last item inserted. You might wonder, given all the restrictions on stacks, why not use arrays or linked lists instead? In development, we have a specific scene, according to the specific scene to choose the data structure, the stack for scene very much, such as the browser’s forward and backward, string, such as the legitimacy of the bracket, we use the stack to achieve are better, because the stack is relatively array, the interface of the list for providing a lot less, less interface, the probability of error is reduced, The control of risk increases.
Implementing a stack
It can be seen from the definition of the stack that there are two main operations of the stack. One is to add a piece of data, which is called pushing, and the other is to obtain a piece of data, which is called pushing out. The following two figures are schematic diagrams of pushing and pushing out.
There are two ways to implement a stack, one is based on an array, which we call a sequential stack, and the other is based on a linked list, which we call a chained stack. The following is the code to implement the two stacks
Array-based sequential stack
/** * array-based sequential stack */
public class ArrayStack {
// Maximum stack capacity
private int maxSzie;
// Store the content
private String[] array;
// Top of stack element
private int top;
public ArrayStack(int size){
this.maxSzie = size;
this.array = new String[this.maxSzie];
this.top = 0;
}
/** ** push operation **@paramThe data data *@return0: failed to stack 1: succeeded */
public int push(String data) {
if (top == maxSzie) return 0;
array[top] = data;
top++;
return 1;
}
Stack operation * * / * * *@return* /
public String pop(a) {
if (top == 0) return null;
return array[--top];
}
/** * gets the top element **@return* /
public String peek(a) {
return array[top - 1];
}
/** * Check whether the stack is empty *@return* /
public boolean isEmpty(a) {
return top == 0; }}Copy the codeChain stack based on linked list
/** ** list based chain stack */
public class LinkStack {
// always refer to the first element of the stack
private Node top = null;
/** ** stack **@param data
* @return* /
public int push(String data) {
Node node = new Node(data);
if (top == null) {
top = node;
} else {
node.next = top;
top = node;
}
return 1;
}
/** ** out of the stack **@return* /
public String pop(a) {
if (top == null) return null;
String data = top.getData();
top = top.next;
return data;
}
/** * Node information */
private static class Node {
private String data;
private Node next;
public Node(String data) {
this.data = data;
this.next = null;
}
public String getData(a) {
return this.data; }}}Copy the codeThe implementation of the stack is relatively simple, because the stack involves few operations, mainly on the stack and the stack of two operations.
The application of the stack
Checks the validity of string parentheses
We sometimes need to check the validity of string parentheses, that is, an open parenthesis needs to match a close parenthesis, which we can do using a stack. We can understand why a stack is used from a valid parenthesis, right? If the parentheses are valid, the last open parentheses match the first close parentheses, the penultimate open parentheses match the second close parentheses, and so on, which conforms to the nature of our stack.
Suppose we have three types of parentheses: parentheses (), square parentheses [], and curly parentheses {}. We use a stack to check the validity of parentheses. We push all the open parentheses, and when the close parentheses are present, we match them, in the following three cases:
- If the stack is empty, there are no open parentheses, and the use of parentheses is illegal
- The left parenthesis removed from the stack does not match the right parenthesis. The parenthesis is not valid
- The left parenthesis pulled from the stack matches the right parenthesis, using temporary legal parenthesis
When the entire string is scanned, the stack is checked to see if there are any values left. If the stack is empty, the parentheses are valid.
The implementation code
public static boolean BracketChecker(String data) {
char[] chars = data.toCharArray();
ArrayStack stack = new ArrayStack(chars.length);
for (char ch : chars) {
switch (ch){
case '{':
case '[':
case '(':
stack.push(ch);
break;
case '} ':
case '] ':
case ') ':
if(! stack.isEmpty()){char ch1 = stack.pop();
if ((ch=='} '&& ch1 ! ='{')
||(ch=='] '&& ch1 ! ='[')
||(ch==') '&& ch1 ! ='(')
){
return false; }}else {
return false;
}
break;
default:
break; }}return stack.isEmpty();
}
Copy the codeBrowser forward and backward functions
As we all know when we use a browser, the browser can move forward and backward, which also conforms to the characteristics of the stack. The page we visit first must be the last to go back. So let’s see how does the stack do this?
We need to define two stacks. We push the first page into the first stack, when we click back, we take data from the first stack and put it into the second stack, and when we click forward, we take data from the second stack and put it into the first stack. When the first stack has no data, there are no pages to click back, and when the second stack has no data, there are no pages to click forward. This allows us to move the browser forward and backward through the stack.
The last
For a small advertisement, jinjiu Yinshi job-hopping season, Brother Flathead has arranged a more comprehensive Java learning materials for everyone. Please scan the code to pay attention to the wechat public number: “Flathead’s technical blog” to receive, I wish you a promotion and salary increase.
