This article was originally posted on the public account bigsai
What is a stack
Stacks are very common in our daily coding, and many people’s exposure to stacks may be limited to recursive use of stacks and StackoverflowExceptions. Stacks are lifO data structures (think of the cell of a biochemical pyramid and the dog hole of a biochemical ring).
The stack is defined like this:
A stack, also known as a stack, is a linear table with limited operations. Defines linear tables that only perform insert and delete operations at the end of the table. This end is called the top of the stack, and the other end is called the bottom of the stack. Adding a new element to a stack is also called pushing, pushing, or pushing. It is done by placing the new element on top of the top element to make it the new top element. To remove an element from a stack is also called to stack or unstack. It is to remove the top element from the stack so that the adjacent element becomes the new top element.
A brief introduction to the key nouns:
Limited operation: this is the table you can’t delete and insert. You can only insert and delete according to its rules. A stack, for example, can only be inserted and deleted at one end. Similarly, queues are computationally constrained and can only operate at both ends.
Linear table: Stack is also a linear table, described in detail in the previous linear table, which is a logical relationship of data. That is, elements are adjacent to each other on the stack. Of course, in the concrete implementation of fractional groups and linked list implementation, their physical storage structure is different. But the logical structure (the purpose of the implementation) is the same.
Top of stack bottom of stack: This description is more logical, as it is known that arrays are easier to insert and delete at the end, while singly linked lists are usually easier to insert and delete at the head. So arrays can have tails at the top of the stack, and lists can have heads at the top of the stack.
Stack applications: Stacks can be used in a variety of ways, such as viewing the call stack in your program, adding and subtracting operations in the computer, non-recursive forms of algorithms, parenthesis matching problems, and so on. So the stack is also a data structure that must be mastered. The simplest, you know, you take a book and you put it on top of it, it’s a lifO, you can think of it as a stack. Next we introduce the stack for array implementation and the stack for linked list implementation.
Array implementation
Array implementation stack use more, we often brush problems will also use the array to achieve a simple stack to solve simple problems.
The structure design
For arrays, it’s easy to emulate stacks because stacks are last-in, first-out, and we can easily insert and delete at the end of the array. So we chose the end to be the top of the stack. So the basic elements needed for a stack are a data[] array and a top(int) for the top of the stack.
So the initialization function code is:
private T data[];
private int top;
public seqStack(a) {
data=(T[]) new Object[10];
top=-1;
}
public seqStack(int maxsize)
{
data=(T[]) new Object[maxsize];
top=-1;
}
Copy the codeA push into
One of the core operations of the stack is push() : the push operation.
- If top< array length -1. Into the stack,
top++; a[top]=value; - If top== array length -1; The stack is full.
Pop pops and returns first
- If top>=0, the stack is not empty and can be ejected.
return data[top--]; - As shown below, the stack is 1,2,3,4,5,6 (the top of the stack).
Other operating
For example, peek returns the top of the stack without popping. Return data[top] only when the requirement is met.
Array implementation:
packageTeam stack;public class seqStack<T> {
private T data[];
private int top;
public seqStack(a) {
data=(T[]) new Object[10];
top=-1;
}
public seqStack(int maxsize)
{
data=(T[]) new Object[maxsize];
top=-1;
}
boolean isEmpty(a)
{
return top==-1;
}
int length(a)
{
return top+1;
}
boolean push(T value) throws Exception/ / in the stack
{
if(top+1>data.length-1)
{
throw new Exception("Stack full");
}
else {
data[++top]=value;
return true; }}T peek(a) throws Exception// Return the top element of the stack not removed
{
if(! isEmpty()) {return data[top];
}
else {
throw new Exception("Stack empty"); }}T pop(a) throws Exception
{
if(isEmpty())
{
throw new Exception("Stack empty");
}
else {
returndata[top--]; }}public String toString(a)
{
if(top==-1)
{
return "";
}
else {
String va="";
for(inti=top; i>=0; i--) { va+=data[i]+"";
}
returnva; }}}Copy the codeLinked list implementation
You can do arrays, you can do linked lists. The design of stack can be roughly divided into two ideas:
- Insert and delete at the end like an array. As we all know, the low efficiency of linked list is query, and the efficiency of query to the tail is very low. Even if the tail pointer is used, the tail insertion efficiency can be solved, but the deletion efficiency still cannot be solved (deletion needs to find the precursor node), and the bidirectional linked list is also required. Although I have described bidirectional lists in detail, this is too complicated!
- Therefore, we use the single linked list of the leading node to insert and delete the head, which is the top of the stack. The insertion is directly after the head node, and the deletion is also directly after the first node, which can perfectly meet the needs of the stack.
The structure design
Design and linked list is very similar, long story short, short words do not say, directly on the code to understand. List nodes:
static class node<T>
{
T data;
node next;
public node(a) {}public node(T value)
{
this.data=value; }}Copy the codeBasic structure:
public class lisStack <T>{
int length;
node<T> head;/ / head node
public lisStack(a) {
head=new node<>();
length=0;
}
// Other methods
}
Copy the codeA push into
Consistent with single linked list head insertion, if you are not familiar with the previous linear table to explain the specific process.
There is a difference between array stack and chained stack. The stack has no size limit (no memory system limit) and does not need to consider whether or not it is out of bounds, while the array needs to consider the capacity problem.
If a node team is pushed:
- Empty linked list pushed
head.next=team; - Not empty into the stack
team.next=head.next; head.next=team;
Pop the pop-up
Consistent with the single-linked list header deletion, if you do not know much about the author, please see the introduction of the linear list.
As with arrays, check whether the stack is empty if the node team is off the stack: head points to the team backend node.
Other operating
Other operations such as PEEK return to the top of the stack without popping up. Return head. Next. Data. Length you can either iterate through the list to return the length, or you can set it dynamically (in this article) to follow the stack length.
Linked list implementation:
packageTeam stack;public class lisStack <T>{
static class node<T>
{
T data;
node next;
public node(a) {}public node(T value)
{
this.data=value; }}int length;
node<T> head;/ / head node
public lisStack(a) {
head=new node<>();
length=0;
}
boolean isEmpty(a)
{
return head.next==null;
}
int length(a)
{
return length;
}
public void push(T value) {/ / close to stack
node<T> team=new node<T>(value);
if(length==0)
{
head.next=team;
}
else{ team.next=head.next; head.next=team; } length++; }public T peek(a) throws Exception {
if(length==0) {throw new Exception("Linked list is empty"); }else {/ / delete
return(T) head.next.data; }}public T pop(a) throws Exception {/ / out of the stack
if(length==0) {throw new Exception("Linked list is empty"); }else {/ / delete
T value=(T) head.next.data;
head.next=head.next.next;//va.next
length--;
returnvalue; }}public String toString(a){
if(length==0) {return ""; }else {
String va="";
node team=head.next;
while(team! =null)
{
va+=team.data+"";
team=team.next;
}
returnva; }}}Copy the codeStacks can be played this way
Since the above detailed description of the design stack, here are two very classic very classic examples (very high frequency, easy to forget, and important, common problems will not be included)
Force buckle 20 valid parentheses:
Question: given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘string, to determine whether a string is effective.
A valid string must meet the following requirements:
An open parenthesis must be closed with a close parenthesis of the same type. The left parentheses must be closed in the correct order. Note that an empty string can be considered a valid string.
Example:
Input: “()[]{}” Output: true
Example:
Input: “([)]” output: false
Analysis: bracket class problem is a classic stack class problem, must think of stack processing. Whether a string is a valid string depends on whether it all forms pairs.
From a single parenthesis pair, ((,)) is not satisfied, only () is satisfied, that is, one left and one right.
From multiple parenthesis pairs {[(the string can also accept any infinite parenthesis of (, [,{, but if the left parenthesis can only accept first) parenthesis (becomes {[).
It can be seen from above as the idea of phase elimination. For example, ({[()()]})) string traversal can be handled like this:
(({[(The next)Off into(({[(({[(The next)Off into(({[(({[The next]Off into(({(({The next}Off into((((The next)Off into((The next)Off into
During each operation, it is determined whether the top bracket of the remaining valid parentheses can be eliminated with the phase of the traversal. This process uses the stack to determine whether the current stack is added or the top is eliminated. At the end, if the stack is empty, it is satisfied; otherwise, it is not satisfied.
public boolean isValid(String s) {
Stack<Character>stack=new Stack<Character>();
for(int i=0; i<s.length(); i++) {char te=s.charAt(i);
if(te=='] ')
{
if(! stack.isEmpty()&&stack.pop()=='[')
continue;
else {
return false; }}else if(te=='} ')
{
if(! stack.isEmpty()&&stack.pop()=='{')
continue;
else {
return false; }}else if(te==') ')
{
if(! stack.isEmpty()&&stack.pop()=='(')
continue;
else {
return false; }}else
stack.push(te);
}
return stack.isEmpty();
}
Copy the codeOf course, the JDK stack is not easy to use, you can use the array optimization:
public boolean isValid(String s) {
char a[]=new char[s.length()];
int index=-1;
for(int i=0; i<s.length(); i++) {char te=s.charAt(i);
if(te=='] ')
{
if(index>=0&&a[index]=='[')
index--;
else {
return false; }}else if(te=='} ')
{
if(index>=0&&a[index]=='{')
index--;
else {
return false; }}else if(te==') ')
{
if(index>=0&&a[index]=='(')
index--;
else {
return false; }}else
a[++index]=te;
}
return index==-1;
}
Copy the codeForce buckle 32 longest valid bracket (difficulty)
Given a string containing only ‘(‘ and ‘)’, find the length of the longest substring containing valid parentheses.
Example:
Input: “(()” Output: 2 Explanation: The longest valid parenthesis substring is “()”
Example:
Input: “)()())” Output: 4 Explanation: The longest valid parenthesis substring is “()()”
Program 1 Violence
The core idea of this problem is to use stack simulation. It’s a little bit easier in this case because there are only two parentheses (and), and if you’re using violence you can loop around and find the longest valid parentheses each time. If the parentheses match, you can terminate the match if the parentheses match.
It is impossible to connect to the front until the third one. If (just expect to come later), a) can pair with a (to eliminate one of the stacks (.
Of course, in the specific implementation, we use the array to simulate the stack, the implementation code is:
public int longestValidParentheses(String s) {
char str[]=s.toCharArray();// Array of characters
int max=0;
for(int i=0; i<str.length-1; i++) {int index=-1;
if(max>=str.length-i)
break;
for(intj=i; j<str.length; j++) {if(str[j]=='(')
index++;
else {
if(index<0)
{
i=j;
break;
}
else{ index--; }}if(index==-1&&(j-i+1>max))
{
max=j-i+1; }}}return max;
}
Copy the codeThis is too complicated, so let’s see how we can use stack optimization.
Scheme two stack optimization
How to optimize this problem from O(n2) time complexity to O(n)? It’s easy. We need to pay attention to his process. Let’s just look at some random maximum scenarios.
())() () () ()Max. Last part (separated by space)() ()((()Maximum is the front part( ( ( ( (() () () ()The maximum is the latter part
For a fetch like this you’ll notice that there are some differences between the parentheses: (once the left parenthesis is present it expects one) matches, but it may be followed by) and there are many other parentheses pairs in between. : There are two cases of right expansion:
- One is that it’s already past the opening parenthesis and can’t be continuous anymore. For example,
() ()The occurrence of the third parenthesis has made the whole string impossible to be continuous,The largest is either to the left of it.Or to the right. You can think of it as an initial mechanism for clearing zeros. - Another situation
)It’s in the target stack(You can match it.The match is superimposed on the number of levels after eliminationAnd determine if it is the maximum. (Explained below)
We use an int array to indicate that the current level (stack depth) has the correct number of parentheses. Simulate a stack behavior from left to right, encounter) too much (not present in the current stack (to match) then clear the data and start again. And so on to the end. You can think of it as a step, meet (go up a step and clear the new step, meet) go down the next step and add the amount to the step that has fallen. For details, please see the following picture to simulate the process: () () () () ())
Take a closer look at the diagram. The code is as follows:
public static int longestValidParentheses(String s) {
int max=0;
int value[]=new int[s.length()+1];
int index=0;
for(int i=0; i<s.length(); i++) {if(s.charAt(i)=='(')
{
index++;
value[index]=0;
}
else {/ / ")"
if(index==0)
{
value[0] =0;
}
else {
value[index-1]+=value[index--]+2;/ / overlay
if(value[index]>max)/ / updatemax=value[index]; }}}return max;
}
Copy the codeThis can also be done with stacks, but is slightly less efficient than arrays:
public int longestValidParentheses(String s) {
int maxans = 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {//(Add the current
stack.push(i);
} else {
stack.pop();
if (stack.empty()) {
stack.push(i);
} else {//i-stack.peek is the total number of occurrences and peek is the number of unmatched occurrencesmaxans = Math.max(maxans, i - stack.peek()); }}}return maxans;
}
Copy the codeconclusion
This is the end of this article on the stack introduction, I believe you can write a stack and try to solve the bracket matching problem! Of course, stack can solve a lot of problems, such as rain problem, binary tree non-recursive traversal and so on, some important will be summarized.
Welcome to pay attention to my public number: Bigsai first-hand learning knowledge, finally don’t mean your key three even, original support, thank you!