一 栈(Stack):一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一 端称为栈顶,另一端称为栈底。栈中的数据元素遵守先进后出。
压栈:栈的插入操作也叫入栈,进栈,压栈。 出栈:栈的删除操作也叫出栈。方法:
stack.push(); 压栈 stack.pop(); 查看栈顶元素并删除 stack.peek(); 查看栈顶元素不删除 stack.empty 栈是否为空二 队列(Queue):只允许在一端进行插入数据,另一端进行删除数据操作的特殊线性表,队列中的元素遵循先进先出。
入队列:队尾插入; 出队列:队头删除;方法: 常用:
Queue.offer(); 压栈 Queue.poll(); 查看栈顶元素并删除 Queue.peek(); 查看栈顶元素不删除
抛异常: Queue.add(); 压栈 Queue.remove(); 查看栈顶元素并删除 Queue.element(); 查看栈顶元素不删除三 双端队列(Deque):两端都可以进行入队和出队操作的队列,deque 是 “double ended queue” 的简称。那就说明元 素可以从队头出队和入队,也可以从队尾出队和入队。
方法: 常用: 抛异常: 入队列:队首: offerFirst(); addFirst(); 队尾:offerLast(); addLast();
出队列: 队首: pollFirst(); removeFirst(); 队尾: pollLast(); removeLast();
获取元素: 队首: peekFirst(); getFirst(); 队尾:peekLast(); getLast();
![](/i/l/?n=22&i=blog/2940517/202208/2940517-20220823232140417-1584021900.png)
试题
1 括号匹配问题
class Solution { public boolean isValid(String s) { Stack<Character> 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()){ System.out.println("右括号多"); return false; } char top=stack.peek(); if (top=='('&&ch==')'||top=='['&&ch==']'||top=='{'&&ch=='}'){ stack.pop(); }else { System.out.println("左右括号不匹配"); return false; } } } if (!stack.empty()){ System.out.println("左括号多"); return false; } return true; } }
2 循环队列
class MyCircularQueue {
public int[] elem;
public int front; //队头下标
public int rear; //队尾下标
public MyCircularQueue(int k) {
this.elem=new int[k+1];
}
public boolean enQueue(int value) {
if (isFull()) return false;
this.elem [rear]=value;
rear=(rear+1)% elem.length;
return true;
}
public boolean deQueue() {
if (isEmpty()) return false;
front=(front+1)% elem.length;
return true;
}
//队首获取元素
public int Front() {
if (isEmpty())return -1;
return elem[front];
}
//队尾获取元素
public int Rear() {
if (isEmpty())
return -1;
int index = -1;
if (rear==0){
index= elem.length-1;
}else {
index= rear-1;
}
return elem[index];
}
public boolean isEmpty() {
return front==rear;
}
public boolean isFull() {
if ((rear+1)%elem.length==front){
return true;
}
return false;
}
3 队列实现栈
public class MinStack { public Queue<Integer> qu1; public Queue<Integer> qu2; public MinStack() { qu1=new LinkedList<>(); qu2=new LinkedList<>(); } public void push(int x) { if (qu1.isEmpty()){ qu1.offer(x); }else if (qu2.isEmpty()){ qu2.offer(x); } qu1.offer(x); } public int pop() { if (empty())return -1; if (!qu1.isEmpty()){ int size=qu1.size()-1; for (int i = 0; i < size; i++) { int val =qu1.poll(); qu2.offer(val); } return qu1.poll(); } if (!qu2.isEmpty()){ int size=qu2.size()-1; for (int i = 0; i < size; i++) { int val=qu2.poll(); qu1.offer(val); } return qu2.poll(); } return -1; } public int top() { if (empty())return -1; int val=-1; if (!qu1.isEmpty()){ int size= qu1.size(); for (int i = 0; i<size; i++) { val =qu1.poll(); qu2.offer(val); } return val; } if (!qu2.isEmpty()){ int size= qu2.size(); for (int i = 0; i < size; i++) { val=qu2.poll(); qu1.offer(val); } return val; } return -1; } public boolean empty() { return qu1.isEmpty() && qu2.isEmpty(); } }
4 栈实现队列
class MyQueue { public Stack<Integer>stack1; public Stack<Integer>stack2; public MyQueue() { stack1 =new Stack<>(); stack2 =new Stack<>(); } public void push(int x) { stack1.push(x); } public int pop() { if (empty())return -1; while (stack2.isEmpty()){ if (!stack1.isEmpty()){ stack2.push(stack1.pop()); } } return stack2.pop(); } public int peek() { if (empty())return-1 ; while (stack2.isEmpty()){ if (!stack1.isEmpty()){ stack2.push(stack1.pop()); } } return stack2.peek(); } public boolean empty() { return stack1.isEmpty() &&stack2.empty(); }
标签:qu1,return,队列,public,Queue,int,isEmpty,Stack From: https://www.cnblogs.com/lbwboke/p/16618398.html