java数据结构之栈的详解

java数据结构之栈的详解

目录一、栈1.栈的应用1.1括号匹配1.2后缀表达式1.3用栈实现队列1.4最小栈1.5栈的压入和弹出序列总结

一、栈

栈的特性就是先进后出，常用方法是入栈（push()）,出栈(pop()),栈空（empty()）,看栈顶元素（peek()）;

1.栈的应用

1.1括号匹配

public boolean isValid(String s) {

//有效括号时隔4个月后重新打卡 看看栈学的怎么样

Stack stack=new Stack<>();

for(int i=0;i

char ch=s.charAt(i);

if(ch=='('||ch=='{'||ch=='['){

stack.push(ch);

}else{

if(stack.empty()){

//右括号多

return false;

}else{

char ch1=stack.peek();

if(ch1=='{'&&ch=='}'||ch1=='['&&ch==']'||ch1=='('&&ch==')'){

stack.pop();

}else{

return false;

}

}

}

}

if(!stack.empty()){

return false;

}

return true;

}

1.2后缀表达式

a+b 这是我们最常见的表达式

前缀表达式就是+ab

后缀表达式就是ab+

转换方式就是每一个表达式用括号括起，将两个表达式中间的运算符放到括号外，加括号的顺序就是先乘除后加减

逆波兰表达式求值：这里是后缀表达式，所以减法就是后出的减先出的，除法也是。利用栈的特性来实现后缀表达式

public int evalRPN(String[] tokens) {

Stack stack=new Stack<>();

int num1=0;

int num2=0;

for(String str:tokens){

if(str.equals("+")){

num1=stack.pop();

num2=stack.pop();

stack.push(num1+num2);

}else if(str.equals("-")){

num1=stack.pop();

num2=stack.pop();

stack.push(num2-num1);

}else if(str.equals("*")){

num1=stack.pop();

num2=stack.pop();

stack.push(num1*num2);

}else if(str.equals("/")){

num1=stack.pop();

num2=stack.pop();

stack.push(num2/num1);

}else{

stack.push(Integer.parseInt(str));

}

}

return stack.pop();

}

1.3用栈实现队列

用栈模拟出队列的push(),pop(),peek(),empty() 方法

class MyQueue {

public Stack stack1;

public Stack stack2;

/** Initialize your data structure here. */

public MyQueue() {

stack1 =new Stack<>();

stack2 =new Stack<>();

}

/** Push element x to the back of queue. */

public void push(int x) {

stack1.push(x);

}

/** Removes the element from in front of queue and returns that element. */

public int pop() {

if(stack2.empty()){

while(!stack1.empty()){

stack2.push(stack1.pop());

}

}

IBbyW return stack2.pop();

}

/** Get the front element. */

public int peek() {

if(stack2.empty()){

while(!stack1.empty()){

stack2.push(stack1.pop());

}

}

return stack2.peek();

}

/** Returns whether the queue is empty. */

public boolean empty() {

return stack1.empty()&&stack2.empty();

}

}

/**

* Your MyQueue object will be instantiated and called as such:

* MyQueue obj = new MyQueue();

* obj.push(x);

* int param_2 = obj.pop();

* int param_3 = obj.peek();

* boolean param_4 = obj.empty();

*/

1.4最小栈

class MinStack {

//定义双栈来实现最小栈

public Deque stack1;

public Deque minStack;

/** initialize your data structure here. */

public MinStack() {

stack1=new LinkedList();

minStack=new LinkedList();

minStack.push(Integer.MAX_VALUE);

}

public void push(int val) {

stack1.push(val);

minStack.push(Math.min(val,minStack.peek()));

}

public void pop() {

stack1.pop();

minStack.pop();

}

public int top() {

return stack1.peek();

}

public int getMin() {

return minStack.peek();

}

}

/**

* Your MinStack object will be instantiated and called as such:

* MinStack obj = new MinStack();

* obj.push(val);

* obj.pop();

* int param_3 = obj.top();

* int param_4 = obj.getMin();

*/

1.5栈的压入和弹出序列

先看题目要求：输入两个整数序列，第一个序列表示栈的压入顺序，第二个序列表示栈的弹出序列，请判断是否为合法的出栈序列

public boolean validateStackSequences(int []pushed,int []popped){

Stack stack=new Stack<>();

int i=0;

for(int num:pushed){

stack.push(num);

while(!stack.isEmpty()&&stack.peek()==popped[i]){

i++;

stack.pop();

}

}

return stack.isEmpty();

}

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注我们的更多内容！

char ch=s.charAt(i);

if(ch=='('||ch=='{'||ch=='['){

stack.push(ch);

}else{

if(stack.empty()){

//右括号多

return false;

}else{

char ch1=stack.peek();

if(ch1=='{'&&ch=='}'||ch1=='['&&ch==']'||ch1=='('&&ch==')'){

stack.pop();

}else{

return false;

}

}

}

}

if(!stack.empty()){

return false;

}

return true;

}

1.2后缀表达式

a+b 这是我们最常见的表达式

前缀表达式就是+ab

后缀表达式就是ab+

转换方式就是每一个表达式用括号括起，将两个表达式中间的运算符放到括号外，加括号的顺序就是先乘除后加减

逆波兰表达式求值：这里是后缀表达式，所以减法就是后出的减先出的，除法也是。利用栈的特性来实现后缀表达式

public int evalRPN(String[] tokens) {

Stack stack=new Stack<>();

int num1=0;

int num2=0;

for(String str:tokens){

if(str.equals("+")){

num1=stack.pop();

num2=stack.pop();

stack.push(num1+num2);

}else if(str.equals("-")){

num1=stack.pop();

num2=stack.pop();

stack.push(num2-num1);

}else if(str.equals("*")){

num1=stack.pop();

num2=stack.pop();

stack.push(num1*num2);

}else if(str.equals("/")){

num1=stack.pop();

num2=stack.pop();

stack.push(num2/num1);

}else{

stack.push(Integer.parseInt(str));

}

}

return stack.pop();

}

1.3用栈实现队列

用栈模拟出队列的push(),pop(),peek(),empty() 方法

class MyQueue {

public Stack stack1;

public Stack stack2;

/** Initialize your data structure here. */

public MyQueue() {

stack1 =new Stack<>();

stack2 =new Stack<>();

}

/** Push element x to the back of queue. */

public void push(int x) {

stack1.push(x);

}

/** Removes the element from in front of queue and returns that element. */

public int pop() {

if(stack2.empty()){

while(!stack1.empty()){

stack2.push(stack1.pop());

}

}

IBbyW return stack2.pop();

}

/** Get the front element. */

public int peek() {

if(stack2.empty()){

while(!stack1.empty()){

stack2.push(stack1.pop());

}

}

return stack2.peek();

}

/** Returns whether the queue is empty. */

public boolean empty() {

return stack1.empty()&&stack2.empty();

}

}

/**

* Your MyQueue object will be instantiated and called as such:

* MyQueue obj = new MyQueue();

* obj.push(x);

* int param_2 = obj.pop();

* int param_3 = obj.peek();

* boolean param_4 = obj.empty();

*/

1.4最小栈

class MinStack {

//定义双栈来实现最小栈

public Deque stack1;

public Deque minStack;

/** initialize your data structure here. */

public MinStack() {

stack1=new LinkedList();

minStack=new LinkedList();

minStack.push(Integer.MAX_VALUE);

}

public void push(int val) {

stack1.push(val);

minStack.push(Math.min(val,minStack.peek()));

}

public void pop() {

stack1.pop();

minStack.pop();

}

public int top() {

return stack1.peek();

}

public int getMin() {

return minStack.peek();

}

}

/**

* Your MinStack object will be instantiated and called as such:

* MinStack obj = new MinStack();

* obj.push(val);

* obj.pop();

* int param_3 = obj.top();

* int param_4 = obj.getMin();

*/

1.5栈的压入和弹出序列

先看题目要求：输入两个整数序列，第一个序列表示栈的压入顺序，第二个序列表示栈的弹出序列，请判断是否为合法的出栈序列

public boolean validateStackSequences(int []pushed,int []popped){

Stack stack=new Stack<>();

int i=0;

for(int num:pushed){

stack.push(num);

while(!stack.isEmpty()&&stack.peek()==popped[i]){

i++;

stack.pop();

}

}

return stack.isEmpty();

}

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注我们的更多内容！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。