Shulou(Shulou.com)06/03 Report--

This article is to share with you what the stack is in web development, the editor thinks it is very practical, so I share it with you to learn. I hope you can get something after reading this article, without saying much, follow the editor to have a look.

What is a stack?

Stack encounters a lot in our daily coding, and many people's contact with stack may be limited to recursive use of stack and StackOverflowException, stack is a last-in-first-out data structure (you can imagine the cell of the biochemical pyramid and the dog hole of the biochemical Colosseum). Stack is simple and not simple, because it is easy to learn stack directly, but using stack to solve problems often requires ingenious methods.

Evoke a wave of memories

The stack is defined like this:

Stack, also known as stack, is a linear table with limited operations. Qualifies linear tables that insert and delete only at the end of the table. This end is called the top of the stack, on the contrary, the other end is called the bottom of the stack. Inserting a new element into a stack is also called entering, entering, or pressing the stack. It puts the new element on top of the stack and makes it a new top element. Removing an element from a stack is also called making a stack or unstack. It removes the top element of the stack and makes its adjacent elements a new top element of the stack.

A little introduction to the key nouns:

Operation restriction: that is, you can't just delete and insert this table. You can only insert and delete according to its rules. For example, the stack can only be inserted and deleted at one end. Similarly, queues are operationally limited and can only operate at both ends.

Linear table: stack is also a kind of linear table, which is described in detail earlier, which expresses the logical relationship of data. That is, the elements in the stack are adjacent. Of course, in the specific implementation, there are also score groups and linked lists, and their physical storage structures are different. But the logical structure (the purpose of implementation) is the same.

Top and bottom of the stack: this description is biased towards logical content, because it is known that it is easier to insert and delete an array at the end, while a single linked list is usually easier to insert and delete at the beginning. So the array can be used as the top of the stack, and the linked list can be used as the top of the stack.

Stack application: stack is widely used, such as your program execution to view the call stack, the computer four addition and subtraction operations, the non-recursive form of the algorithm, parenthesis matching problems, and so on. So stack is also a data structure that must be mastered. The simplest thing everyone has experienced is that when you stack a book up and down, it is a last-in-first-out process, and you can think of it as a stack. Let's introduce the stack of the array implementation and the stack of the linked list implementation.

Array implementation

Array implementation of the stack is more, we often do exercises will also use the array to achieve a simple stack to solve simple problems.

Structural design.

For arrays, the process of simulating the stack is simple, because the stack is last-in, first-out, and we can easily insert and delete at the end of the array. So we chose the end as the top of the stack. So the basic elements required for a stack are an data [] array and a top (int) indicating the top position of the stack.

Then the initialization function code is:

Private T data []; private int top; public seqStack () {data= (T []) new Object [10]; top=-1;} public seqStack (int maxsize) {data= (T []) new Object [maxsize]; top=-1;}

Push insertion

One of the core operations of the stack, push (): the stack operation.

If top=0, the stack is not empty and can be popped up. Return data [top--]

As shown in the following figure, the original stack is 1, top 2, 3, 4, 5, 6 (top of the stack), perform the pop operation, and the stack becomes 3 and returns 4.

Other actions

For example, the peek operation returns to the top of the stack without popping up. So you just need to return data [top] when you meet the requirements.

Array implementation:

Package stack; public class seqStack {private T data []; private int top; public seqStack () {data= (T []) new Object [10]; top=-1;} public seqStack (int maxsize) {data= (T []) new Object [maxsize]; top=-1;} boolean isEmpty () {return top==-1 } int length () {return top+1;} boolean push (T value) throws Exception// push stack {if (top+1 > data.length-1) {throw new Exception ("stack full");} else {data [+ + top] = value; return true }} T peek () throws Exception// returns the top element of the stack without removing {if (! isEmpty ()) {return data [top];} else {throw new Exception ("stack is empty") } T pop () throws Exception {if (isEmpty ()) {throw new Exception ("stack is empty");} else {return data [top--];}} public String toString () {if (top==-1) {return "" } else {String va= "; for (int itemtopisti > = 0positomotion -) {va+= data [I] +";} return va;} linked list implementation

There are arrays, and linked lists can, of course. For stack design, it can be roughly divided into two ideas:

Insert and delete at the tail like an array. We all know that the efficiency of the linked list is low in the query, and the efficiency of the query to the tail is very low. Even if the tail pointer is used, it can solve the tail insertion efficiency, but still can not solve the deletion efficiency (delete needs to find the precursor node), but also requires a two-way linked list. Although the previous detailed introduction of two-way linked list, but this is too complicated!

Therefore, we use the single linked list of the leading node to insert and delete the header, regard the head as the top of the stack, insert directly after the header node, and delete the first node after deleting the header node directly, so that we can perfectly meet the needs of the stack.

Structural design.

The design is very similar to the linked list, make a long story short, do not say a short story, and understand it directly on the code.

Nodes of the linked list:

Static class node {T data; node next; public node () {} public node (T value) {this.data=value;}}

Basic structure:

Public class lisStack {int length; node head;// header node public lisStack () {head=new node (); length=0;} / / other methods}

Push insertion

Consistent with single-chain header insertion, if you don't know much about it, you can take a look at the linear table written earlier to explain the process.

Different from the stack formed by the array, the chained stack theoretically has no size limit (does not break the memory system limit), does not need to consider whether to cross the boundary, while the array needs to consider the capacity problem.

If a node team enters the stack:

Empty linked list stacks head.next=team

Non-empty stack team.next=head.next;head.next=team

Pop eject

Consistent with the deletion of the single chain header, if you don't know much about it, please take a look at the author's introduction to the linear table.

And arrays also need to determine whether the stack is empty, if the node team out of the stack: head points to the team trailing node.

Other actions

Others, such as peek operation, return to the top of the stack without popping up. So you only need to return head.next.data when you are satisfied with the question. On the other hand, in length, you can traverse the return length of the linked list, or you can set it dynamically (taken in this article) to follow the stack length.

Linked list implementation:

Package queue stack; public class lisStack {static class node {T data; node next; public node () {} public node (T value) {this.data=value;}} int length; node head;// header node public lisStack () {head=new node (); length=0 } boolean isEmpty () {return head.next==null;} int length () {return length;} public void push (T value) {/ / near stack node team=new node (value); if (length==0) {head.next=team;} else {team.next=head.next; head.next=team } length++;} public T peek () throws Exception {if (length==0) {throw new Exception ("linked list is empty");} else {/ / delete return (T) head.next.data;}} public T pop () throws Exception {/ / unstack 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--; return value;}} public String toString () {if (length==0) {return ";} else {String va="; node team=head.next While {va+=team.data+ "; team=team.next;} return va;} stack can play like this.

Since the design stack is explained in detail above, here are two very classic examples of stacks (very high frequency, easy to forget, and very important, not to put down common problems).

Force 20 valid parentheses:

Given a string that includes only'(',')','{','}','[',']', judge whether the string is valid or not.

A valid string must satisfy:

The left parenthesis must be closed with the same type of closing parenthesis.

The left parenthesis must be closed in the correct order.

Note that an empty string can be considered a valid string.

Example:

Enter: "() [] {}"

Output: true

Example:

Enter: "([)]"

Output: false

Analysis:

The problem of parenthesis class is a classical stack class problem, so you must think of stack processing. To determine whether a string satisfies a valid string, it depends on whether it can form a pair.

From a single parenthesis pair, ((,)) is not satisfied, only () can be satisfied, that is, one left and one right.

From multiple parenthesis pairs, {[(the string can also accept any infinite (, [, {parentheses). But if the parentheses to the left can only be received first) parentheses (become {[).

From above, it can be regarded as a kind of thought of elimination. For example, (({[) ()]})) string traversal can be handled like this:

({[(next)) is deleted into ({[)

({[(next)) is deleted into ({[)

({[next]) disappear into (({)

(({next}) disappear into ()

((next) eliminate into ()

(next) it will satisfy the meaning of the question if it is eliminated like this.

Each operation determines whether the parenthesis at the top of the remaining valid parentheses can be eliminated with the traversal. This process uses the stack to determine whether to add the stack or eliminate the top. In the end, if the stack is empty, it is satisfied, otherwise it is not satisfied. Of course, the specific parentheses should correspond to the specific implementation code:

Public boolean isValid (String s) {Stackstack=new Stack (); for (int iIndexes) / a [index] ='{') index--; else {return false }} else if (te==')') {if (index > = zero & a [index] ='(') index--; else {return false;}} else a [+ + index] = te;} return index==-1 }

Force buckle 32 longest valid parentheses (difficult)

Topic description: given a string that contains only'('and')', find out the length of the longest substring containing valid parentheses.

Example:

Enter: "()"

Output: 2

Explanation: the longest valid parenthesis string is "()"

Example:

Enter: ") () ()"

Output: 4

Explanation: the longest valid parenthesis string is "() ()"

Option 1 violence

The core idea of this problem is to use stack simulation. This question is a little simpler because there are only (and) two kinds of parentheses, and the longest valid parentheses can be found in each cycle when using violence. The case where the parentheses match can be terminated directly is that there are more right parentheses that cannot be matched.

For example, () (to the third is impossible to connect with the front. If you come (just look forward to coming later), one can be paired with one (to eliminate one in the stack).

Of course, in the specific implementation, we simulate the stack with an array, and the implementation code is as follows:

Public int longestValidParentheses (String s) {char str [] = s.toCharArray (); / / character array int max=0; for (int iExhibitor iStemstr.roomthmeri) break; for (int

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.