(点击跳转即可哦)
java学习专栏
LeetCode刷题专栏
文章目录
- 栈和队列
- 栈
- 栈的常见问题
- Leetcode-20
- Leetcode-155
- 队列
- Leetcode-225
- Leetcode-232
- Leetcode-622
- 双端队列
线性表：一次保存单个同类型元素，多个元素之间逻辑上连续
数组，链表，栈，队列，字符串（内部就是char[]）
栈和队列 其实是操作受限的线性表。“栈和队列”只能在一端插入元素 和删除元素。
之前的数组也罢，链表也罢，既可以在头部插入和删除，也能在尾部插入和删除，甚至可以在任意位置插入和删除。
栈
栈：是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵守先进后出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。
就像一个米缸一样，先放入的大米在最底部，最后放入的大米在最上方，要想取出大米，只能从上往下一层一层的往出取。
栈的对象
Stackstack = new Stack<>();
栈的核心操作：
E push(E item) 压栈
E pop() 出栈
E peek() 查看栈顶元素
boolean isEmpty() 判断栈是否为空
栈的实现
1 基于数组实现的栈 - 顺序栈
2 基于链表实现的栈- 链式栈
//基于数组实现的栈 package stacktest.mystack_array; import java.util.ArrayList; import java.util.EmptyStackException; import java.util.List; public class Mystack{ private int size; List stack = new ArrayList<>(); public E push(E val){ stack.add(val); size++; return val; } public E pop(){ if(isEmpty()){ throw new EmptyStackException(); } E val = stack.remove(size-1); size--; return val; } public boolean isEmpty() { return size == 0; } public E peek(){ if(isEmpty()){ throw new EmptyStackException(); } return stack.get(size-1); } @Override public String toString() { return stack.toString(); } }
栈的常见问题 Leetcode-20
有效的括号：
思路：
遇到左括号直接入栈，遇到不是左括号，出栈与这个右括号进行配对，若不是，直接返回false,若是，继续向后扫描。
还需要注意，若扫描到终点，此时栈内还有元素，则说明左括号比右括号多，返回false,若栈内已经为空，则还没有扫描到终点，说明右括号比左括号多，返回false.
import java.util.Stack;
public class Leetcode_20 {
public boolean isValid(String s) {
//若只有一个括号，返回false
if (s.length() == 1) {
return false;
}
Stack stack = new Stack<>();
//循环扫描字符串
for (int i = 0; i < s.length(); i++) {
//读取单个字符
char str = s.charAt(i);
//遇到左括号就入栈
if (str == '(' || str == '[' || str == '{') {
stack.push(str);
} else { //遇到了右括号
//栈为空的情况
if (stack.isEmpty()) {
return false;
}
//栈顶元素出栈
char ch = stack.pop();
//与右括号进行匹配
if (str == ')' && ch != '(') {
return false;
}
if (str == ']' && ch != '[') {
return false;
}
if (str == '}' && ch != '{') {
return false;
}
}
}
//扫描结束后，若此时栈为空，返回true,栈不为空，返回false
return stack.isEmpty();
}
//测试用例
public static void main (String[]args){
Leetcode_20 leetcode_20 = new Leetcode_20();
String s = "()[]{}";
System.out.println(leetcode_20.isValid(s));
}
}
Leetcode-155
最小栈问题：
思路：
采用双栈的思路，一个栈正常保存元素，
另一个栈也保存元素，栈为空，直接入栈，栈不为空，在保存时判断，val 和栈顶元素的大小，val小，直接入栈，栈顶元素小，读取栈顶元素进行入栈。这样栈顶保存的永远是当前栈内最小的元素。
package stacktest.leetcode;
import java.util.Stack;
public class Leetcode_155 {
Stack s1 = new Stack<>();
Stack s2 = new Stack<>();
public void push(int val) {
if(s1.isEmpty()){
s1.push(val);
s2.push(val);
return;
}
s1.push(val);
if(val <= s2.peek()){
s2.push(val);
}else {
s2.push(s2.peek());
}
}
public void pop() {
s1.pop();
s2.pop();
}
public int top() {
return s1.peek();
}
public int getMin() {
return s2.peek();
}
}
队列
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾（Tail/Rear）
出队列：进行删除操作的一端称为队头 （Head/Front）
JDK内置的队列
Queuequeue = new LinkedLst<>();
出队操作只能在队列的头部进行，若采用数组的方案，每次出队一个元素，都要搬移剩下的索引元素向前移动一个单位。
所以此时采用链表的方案更加适合对列的结构。
poll 出队列：删除头节点
offer 入队：尾插
peek 查看队首元素：头节点
package queue.myqueue; import java.util.NoSuchElementException; public class MyQueue{ private Node head; private Node tail; private int size; public void offer(E val){ Node node = new Node<>(val); if(isEmpty()){ tail = node; head = node; size++; return; } tail.next = node; tail = tail.next; size++; } public E poll(){ if(isEmpty()){ throw new NoSuchElementException("队列为空~~"); } size--; Node node = head; head = head.next; node.next = null; return node.val; } public E peek(){ if(isEmpty()){ throw new NoSuchElementException("队列为空~~"); } return head.val; } public boolean isEmpty(){ return size == 0; } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("h ["); for (Node x= head; x != null;x = x.next) { sb.append(x.val); if (x.next != null){ sb.append(","); } } sb.append("] t"); return sb.toString(); } } class Node { E val; Node next; public Node(E val) { this.val = val; } }
Leetcode-225
用队列实现栈：
使用两个队列实现一个栈
package stacktest.leetcode;
import java.util.LinkedList;
import java.util.Queue;
public class Leetcode_225 {
//使用两个队列
Queue q1 = new LinkedList<>();
Queue q2 = new LinkedList<>();
public void push(int x) {
q2.offer(x);
while (!q1.isEmpty()){
q2.offer(q1.poll());
}
Queue tmep = q1;
q1 = q2;
q2 = tmep;
}
public int pop() {
return q1.poll();
}
public int top() {
return q1.peek();
}
public boolean empty() {
return q1.isEmpty();
}
}
//使用一个队列,实现栈
Queue queue = new LinkedList<>();
public void push(int x) {
queue.offer(x);
while (queue.peek() != x) {
queue.offer(queue.poll());
}
}
public int pop () {
return queue.poll();
}
public int top () {
return queue.peek();
}
public boolean empty () {
return queue.isEmpty();
}
}
Leetcode-232
用栈实现队列：
import java.util.Stack;
public class Leetcode_232 {
Stack s1 = new Stack<>();
Stack s2 = new Stack<>();
public void push(int x) {
if(s1.isEmpty()){
s1.push(x);
return;
}
while(!s1.isEmpty()){
s2.push(s1.pop());
}
s1.push(x);
while(!s2.isEmpty()){
s1.push(s2.pop());
}
}
public int pop() {
return s1.pop();
}
public int peek() {
return s1.peek();
}
public boolean empty() {
return s1.isEmpty();
}
}
Leetcode-622
循环队列：
package stacktest.leetcode;
public class Leetcode_622 {
Integer[] data;
private int head;
private int tail;
public Leetcode_622(int k) { //MyCircularQueue
data = new Integer[k+1];
}
public boolean enQueue(int value) {
if(isFull()){
return false;
}
data[tail] = value;
tail = (tail+1)% data.length;
return true;
}
public boolean deQueue() {
if(isEmpty()){
return false;
}
head = (head+1)%data.length;
return true;
}
public int Front() {
if(isEmpty()){
return -1;
}
return data[head];
}
public int Rear() {
if (isEmpty()){
return -1;
}
Integer index = tail == 0 ? data.length-1 : tail-1;
return data[index];
}
public boolean isEmpty() {
return head == tail;
}
public boolean isFull() {
// if((tail+1)%data.length == head){
// return true;
// }
// return false;
return (tail + 1) % data.length == head;
}
}
双端队列
双端队列： Deque是Queue的子接口，这个队列既可以尾插，头出，也可以头插，尾出。
以后无论是需要使用栈还是接口，统一使用双端队列接口，不推荐使用Stack这个类，双端队列的一个常用子类就是LinkedList
需要一个栈
Qequestack = new LinkedList<>(); stack.push(1); stack.push(2); stack.push(3); System.out.println(stack.pop());
需要一个队列
Qequequeue = new LinkedList<>(); queue.offer(1); queue.offer(2); queue.offer(3); System.out.println(queue.pop());
要是对大家有所帮助的话，请帮我点个赞吧。
