华强北 网站建设,网站服务理念,嘉兴网站专业制作,做酒吧设计的网站目录
栈(Stack)
栈的使用
栈的模拟实现
栈的应用场景
队列(Queue)
队列的使用
队列模拟实现
循环队列
双端队列
用队列实现栈
用栈实现队列 栈(Stack) 什么是栈#xff1f; 栈 #xff1a;一种特殊的线性表#xff0c;其 只允许在固定的一端进行插入和删除元素操…目录
栈(Stack)
栈的使用
栈的模拟实现
栈的应用场景
队列(Queue)
队列的使用
队列模拟实现
循环队列
双端队列
用队列实现栈
用栈实现队列 栈(Stack) 什么是栈 栈 一种特殊的线性表其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操 作的一端称为栈 顶另一端称为栈底。栈中的数据元素遵守后进先出LIFO Last In First Out 的原则。 压栈栈的插入操作叫做进栈 / 压栈 / 入栈 入数据在栈顶 。 出栈栈的删除操作叫做出栈。 出数据在栈顶。 栈的使用 方法例子
public static void main(String[] args) {
StackInteger s new Stack();s.push(1);s.push(2);s.push(3);s.push(4);
System.out.println(s.size()); // 获取栈中有效元素个数--- 4
System.out.println(s.peek()); // 获取栈顶元素--- 4s.pop(); // 4出栈栈中剩余1 2 3栈顶元素为3
System.out.println(s.pop()); // 3出栈栈中剩余1 2 栈顶元素为3if(s.empty()){System.out.println(栈空);}else{System.out.println(s.size());
}
} 栈的模拟实现 从上图中可以看到Stack继承了VectorVector和ArrayList类似都是动态的顺序表不同的是 Vector是线程安全的。 模拟实现代码
public class MyStack {int[] array;int size;public MyStack() {array new int[3];}public int push(int e) {ensureCapacity();array[size] e;return e;}public int pop() {int e peek();size--;return e;}public int peek() {if (empty()) {throw new RuntimeException(栈为空无法获取栈顶元素);}return array[size - 1];}public int size() {return size;}public boolean empty() {return 0 size;}private void ensureCapacity() {if (size array.length) {array Arrays.copyOf(array, size * 2);}}
} 栈的应用场景
1.逆波兰表达式(中缀转后缀)
https://leetcode.cn/problems/evaluate-reverse-polish-notation/
代码
class Solution {public int evalRPN(String[] tokens) {StackInteger stacknew Stack();for(String x:tokens){if(!isCase(x)){stack.push(Integer.parseInt(x));}else{int nums2stack.pop();int nums1stack.pop();switch(x){case :stack.push(nums1nums2);break;case -:stack.push(nums1-nums2);break;case *:stack.push(nums1*nums2);break;case /:stack.push(nums1/nums2);break;}} }return stack.pop();
}public boolean isCase(String s){if(s.equals()||s.equals(-)||s.equals(*)||s.equals(/)){return true;}return false;}} 2.括号匹配
https://leetcode.cn/problems/valid-parentheses/description/
代码
class Solution {public boolean isValid(String s) {StackCharacter stack new Stack();//遍历for (int i 0; i s.length(); i) {char ch s.charAt(i);//取出字符//判断是不是左括号if (ch ( || ch { || ch [) {stack.push(ch);} else {//遇到右括号,判断栈是不是空if (stack.empty()) {return false;}//看看括号匹不匹配char ch2 stack.peek();if ((ch2 ( ch )) || (ch2 { ch }) || (ch2 [ ch ])) {stack.pop();} else {return false;}}}//如果栈不空,并且遍历完了if (!stack.empty()) {return false;}return true;}
} 3.出栈入栈次序匹配
https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId13tqId11174rp1ru/activity/ojqru/ta/coding-interviews/question-ranking
代码 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]);//每进栈一个数字,peek一下判断一不一样,并且判断越没越界while (!stack.empty() j popV.length stack.peek() popV[j]) {stack.pop();j;}}//循环走完了,判断是不是空,是的话就匹配了,不是的话就不匹配return stack.empty();
} 4.最小栈
https://leetcode.cn/problems/min-stack/
代码
class MinStack {public StackInteger stack;public StackInteger minStack;public MinStack() {stack new Stack();minStack new Stack();}public void push(int val) {stack.push(val);if (minStack.empty()) {minStack.push(val);} else {int minVal minStack.peek();//判断最小栈的栈顶是不是小于等于要存入的值if (val minVal) {minStack.push(val);}}}public void pop() {if (stack.peek().equals(minStack.peek())) {// 弹出的元素是全栈最小的minStack.pop();}stack.pop();}public int top() {return stack.peek();}public int getMin() {if (!minStack.empty()) {return minStack.peek();}return -1;
}
} 队列(Queue) 队列 只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进 先出 FIFO(First In First Out) 入队列进行插入操作的一端称为 队尾 Tail/Rear 出队列进行删 除操作的一端称为 队头 Head/Front 队列的使用 在 Java 中 Queue 是个接口底层是通过链表实现 的。 注意Queue是个接口在实例化时必须实例化LinkedList的对象因为LinkedList实现了 Queue接口。 用法例子
public static void main(String[] args) {
QueueInteger q new LinkedList();q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5); // 从队尾入队列
System.out.println(q.size());
System.out.println(q.peek()); // 获取队头元素q.poll();
System.out.println(q.poll()); // 从队头出队列并将删除的元素返回if(q.isEmpty()){System.out.println(队列空);}else{System.out.println(q.size());
}
} 队列模拟实现 队列中既然可以存储元素那底层肯定要有能够保存元素的空间通过前面线性表的学习了解到常 见的空间类型有 两种顺序结构 和 链式结构 。同学们思考下 队列的实现使用顺序结构还是链式 结构好 模拟实现代码
public class Queue {// 双向链表节点public static class ListNode {ListNode next;ListNode prev;int value;ListNode(int value) {this.value value;}}ListNode first; // 队头ListNode last; // 队尾int size 0;// 入队列---向双向链表位置插入新节点public void offer(int e) {ListNode newNode new ListNode(e);if (first null) {first newNode;
// last newNode;} else {last.next newNode;newNode.prev last;
// last newNode;}last newNode;size;}// 出队列---将双向链表第一个节点删除掉public int poll() {
// 1. 队列为空
// 2. 队列中只有一个元素----链表中只有一个节点---直接删除
// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除int value 0;if (first null) {return null;} else if (first last) {last null;first null;} else {value first.value;first first.next;first.prev.next null;first.prev null;}--size;return value;}// 获取队头元素---获取链表中第一个节点的值域public int peek() {if (first null) {return null;}return first.value;}public int size() {return size;}public boolean isEmpty() {return first null;}
} 循环队列
实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会 使用循环队列。 环形队列通常使用数组实现。 https://leetcode.cn/problems/design-circular-queue/description/
代码
public class MyCircularQueue {public int[] elem;public int front; // 队头public int rear; // 队尾public int usedSize; // 记录队列中元素数量public MyCircularQueue(int k) {elem new int[k];usedSize 0; // 初始化为 0}// 入队public boolean enQueue(int value) {if (isFull()) {return false;}elem[rear] value;rear (rear 1) % elem.length;usedSize; // 每次入队增加 usedSizereturn true;}// 出队public boolean deQueue() {if (isEmpty()) {return false;}front (front 1) % elem.length;usedSize--; // 每次出队减少 usedSizereturn true;}// 得到队头元素public int Front() {if (isEmpty()) {return -1;}return elem[front];}// 得到队尾元素public int Rear() {if (isEmpty()) {return -1;}//如果是0下标就返回数组长度-1不是就rear-1int index (rear 0) ? elem.length - 1 : rear - 1;return elem[index];}public boolean isEmpty() {return usedSize 0; // 使用 usedSize 判断是否为空}public boolean isFull() {return usedSize elem.length; // 使用 usedSize 判断是否为满}
} 双端队列
双端队列deque是指允许两端都可以进行入队和出队操作的队列deque 是 “double ended
queue” 的简称。 那就说明元素可以从队头出队和入队也可以从队尾出队和入队。 Deque是一个接口使用时必须创建LinkedList的对象 在实际工程中使用Deque接口是比较多的栈和队列均可以使用该接口。
DequeInteger stack new ArrayDeque();//双端队列的线性实现
DequeInteger queue new LinkedList();//双端队列的链式实现 用队列实现栈
https://leetcode.cn/problems/implement-stack-using-queues/
代码
class MyStack {// 用队列实现栈//用两个队列实现public DequeInteger qu1;public DequeInteger qu2;public MyStack() {qu1 new LinkedList();qu2 new LinkedList();}public void push(int x) {if (!qu1.isEmpty()) {qu1.offer(x);} else if (!qu2.isEmpty()) {qu2.offer(x);} else {//都空的,指定存qu1.offer(x);}}public int pop() {if (empty()) {return -1;}if (!qu1.isEmpty()) {//这样记录不会因为poll改变int size qu1.size();for (int i 0; i size - 1; i) {//取到长度减1个就是要的了int x qu1.poll();qu2.offer(x);}return qu1.poll();} else {int size qu2.size();for (int i 0; i size - 1; i) {//取到长度减1个就是要的了int x qu2.poll();qu1.offer(x);}return qu2.poll();}}public int top() {if (empty()) {return -1;}if (!qu1.isEmpty()) {//这样记录不会因为poll改变int size qu1.size();int x 0;//用来记录拿出来的值,循环结束后就拿到最后一个for (int i 0; i size; i) {x qu1.poll();qu2.offer(x);}return x;} else {int size qu2.size();int x 0;//用来记录拿出来的值,循环结束后就拿到最后一个for (int i 0; i size ; i) {x qu2.poll();qu1.offer(x);}return x;}}public boolean empty() {//判断两个队列是不是都空的return qu1.isEmpty() qu2.isEmpty();}
} 用栈实现队列
https://leetcode.cn/problems/implement-queue-using-stacks/description/
代码
public class MyQueue {public StackInteger s1;public StackInteger s2;public MyQueue() {s1 new Stack();s2 new Stack();}public void push(int x) {s1.push(x);}public int pop() {if (empty()) {return -1;}if (s2.isEmpty()) {while (!s1.isEmpty()) {s2.push(s1.pop());}}return s2.pop();}public int peek() {if (empty()) {return -1;}if (s2.isEmpty()) {int size s1.size();for (int i 0; i size; i) {int x s1.pop();s2.push(x);}}return s2.peek();}public boolean empty() {return s1.isEmpty() s2.isEmpty();}
}
