广西南宁建设厅网站公布,网站规划文字说明,沈阳网站排名seo,html5网站开发特点前言#xff1a;
栈与队列在数据结构中用法都相对比较简单#xff0c;是数据结构中经常用到的两种。
1.栈#xff08;Stack#xff09;
#xff08;1#xff09;特点#xff1a; 先入后出#xff0c;后入先出。栈的底层就是一个数组#xff08;java原生库中#x…前言
栈与队列在数据结构中用法都相对比较简单是数据结构中经常用到的两种。
1.栈Stack
1特点 先入后出后入先出。栈的底层就是一个数组java原生库中通过对数组的操作来实现栈的相关操作。栈也是可以用链表LinkedList来实现的在LinkedList这个类中也有pushpoppeek等方法足以说明栈可以用LinkedList来实现。栈继承了Vector类这个类中也有一个判空的方法isEmpty() 可以使用在这个类中的所有非私用方法。 2方法
这里pushpopempty时间和空间复杂度都为O(1)。 empty判空是定义了一个变量用来计数。
3OJ题
1逆波兰表达式求值
题析 题解
import java.util.Stack;
class Solution {public boolean isOperation(String x) {if(x.equals() | x.equals(-) | x.equals(*) | x.equals(/)) {return false;}return true;}public int evalRPN(String[] tokens) {StackString stack new Stack();for(String x : tokens) {if(!isOperation(x)) {//如果不是数字int num1 Integer.parseInt(stack.pop()); //栈顶元素 放在右边int num2 Integer.parseInt(stack.pop()); //栈顶后面一个元素 放在左边switch(x) {case :stack.push(String.valueOf((num2 num1)));break;case -:stack.push(String.valueOf((num2 - num1)));break;case *:stack.push(String.valueOf((num2 * num1)));break;case /:stack.push(String.valueOf((num2 / num1)));break;default:break;}}else {stack.push(x);}}return Integer.parseInt(stack.peek());}
}
2括号匹配
题析 题解
import java.util.Stack;
class Solution {public boolean isValid(String s) {StackCharacter stack new Stack();char[] arr s.toCharArray();for(char x : arr) {if(stack.empty()){stack.push(x);}else {if(stack.peek() ( x ) || stack.peek() { x } || stack.peek() [ x ]) {stack.pop();}else {stack.push(x);}}}return stack.empty();}
}
3出栈入栈次序匹配
题析 题解
public class Solution {public boolean IsPopOrder (int[] pushV, int[] popV) {StackInteger stack new Stack();int j 0;for(int i 0; i pushV.length; i) {stack.push(pushV[i]);while(!stack.isEmpty() j popV.length stack.peek() popV[j]) {stack.pop();j;}}if(!stack.isEmpty()) {return false;}return true;}
}
2.队列
队列分为单端队列Queue和双端队列Deque都是接口都有先入先出后入后出的特点。
2.1 单端队列Queue
1特点
只有一端可以入一端可以出。Queue可以用线性表循环队列也可以用链表LinkedList来实现。 2方法 主要的方法就这三种。需要注意的是这里面Queue接口中没有empty()方法但由于它是继承了Vector类所以可以使用isEmpty()方法来判断是否Queue为空。
3OJ题
1设计循环队列
题析
题解
//法一设置一个计数变量count
class MyCircularQueue {//循环队列的底层就是一个数组public int[] arr;//队头public int front;//队尾public int tail;//计数public int count;public MyCircularQueue(int k) {arr new int[k];}public boolean enQueue(int value) {if(isFull()) {//队列已满return false;}if(tail arr.length) {tail 0;}arr[tail] value;tail;count;return true;}public boolean deQueue() {if(isEmpty()) {return false;}front;if(front arr.length) {front 0;}count--;return true;}public int Front() {if(isEmpty()) {return -1;}return arr[front];}public int Rear() {if(isEmpty()) {return -1;}if(isFull()) {}int index (tail 0) ? 0 : (tail - 1); return arr[index];}public boolean isEmpty() {return count 0;}public boolean isFull() {return count arr.length;}
}
//法二浪费一个空间
class MyCircularQueue {//循环队列的底层就是一个数组public int[] arr;//队头public int front;//队尾public int tail;public MyCircularQueue(int k) {arr new int[k 1];}public boolean enQueue(int value) {if(isFull()) {//队列已满return false;}arr[tail] value;tail (tail 1) % arr.length;return true;}public boolean deQueue() {if(isEmpty()) {return false;}front (front 1) % arr.length;return true;}public int Front() {if(isEmpty()) {return -1;}return arr[front];}public int Rear() {if(isEmpty()) {return -1;}int index (tail 0) ? (arr.length - 1) : (tail - 1); return arr[index];}public boolean isEmpty() {return tail front;}public boolean isFull() {return (tail 1) % arr.length front;}
}
浪费一个空间的这种写法
题中给的示列 而按我们这种这里的写法 如果设置长度为3那么只能放两个元素所以需要将数组的长度设置为4就能放三个元素了也就是数组长度设置为k 1。 2.2 双端队列
1特点
两端都可以入队出队。Deque可以用线性表循环队列也可以用链表LinkedList来实现。 2方法
与单端队列的方法都大同小异。
3.栈与队列相关的OJ题
1用栈实现队列
题析 题解
class MyQueue {StackInteger stack1;StackInteger stack2;public MyQueue() {stack1 new Stack();stack2 new Stack();}public void push(int x) {stack1.push(x);}public int pop() {if(stack2.isEmpty()) {while(!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if(stack2.isEmpty()) {while(!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.isEmpty() stack2.isEmpty();}
}2用队列实现栈
题析 题解
class MyStack {QueueInteger queue1;QueueInteger queue2;public MyStack() {queue1 new ArrayDeque();queue2 new ArrayDeque();}public void push(int x) {if(!queue1.isEmpty()) {queue1.offer(x);}else if(!queue2.isEmpty()) {queue2.offer(x);}else {//两个都为空,指定放在queue1中queue1.offer(x);}}public int pop() {if(empty()) {return -1;}int i 0;if(!queue1.isEmpty()) {int size queue1.size();for(i 0; i size- 1; i) {queue2.offer(queue1.poll());}return queue1.poll();}else {int size queue2.size();for(i 0; i size- 1; i) {queue1.offer(queue2.poll());}return queue2.poll();}}public int top() {int i 0;if(!queue1.isEmpty()) {int size queue1.size();int x -1;for(i 0; i size; i) {x queue1.poll();queue2.offer(x);}return x;}else {int size queue2.size();int x -1;for(i 0; i size; i) {x queue2.poll();queue1.offer(x);}return x;}}public boolean empty() {//两个队列均为空的时候才能判断该栈为空return queue1.isEmpty() queue2.isEmpty();}
}
