目录
一、栈
1.1 概念
栈：一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底，栈中的元素遵循先进后出的原则。
压栈：栈的插入操作，也叫进栈或入栈，在栈顶插入数据；出栈：栈的删除操作，在栈顶删除数据。
1.2 栈的使用
| 方法 | 解释 |
| Stack() | 构造一个空的栈 |
| E push(E e) | 将 e 入栈，并返回e |
| E pop() | 将栈顶元素出栈并返回 |
| E peek() | 获取栈顶元素 |
| int size() | 获取栈中有效元素个数 |
| boolean empty() | 检测栈是否为空 |
public static void main(String[] args) { Stackstack = new Stack(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); System.out.println(stack.size());//5 //获取栈顶元素 System.out.println(stack.peek());//5 System.out.println(stack); //[1, 2, 3, 4, 5] stack.pop();//出栈 5 System.out.println(stack.size());//4 System.out.println(stack); //[1, 2, 3, 4] System.out.println(stack.empty());//false}
1.3 栈的模拟实现
由图可知Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。
public class MyStack { int[] elem; int usedSize; public MyStack(){ elem = new int[3]; } //判断栈是否满了 private boolean CapacityIsFull(){ return usedSize == elem.length; } //确保容量充足 private void ensureCapacity(){ if(CapacityIsFull()){ elem = Arrays.copyOf(elem,elem.length*2); } } //入栈 public int push(int data){ ensureCapacity(); elem[usedSize++] = data; return data; } //获取栈顶元素 public int peek(){ if(usedSize == 0){ throw new StackNullEception("栈为空，无法获取栈顶元素"); } return elem[usedSize-1]; } //出栈 public int pop (){ int e = peek(); usedSize--; return e; } //获取栈的长度 public int size(){ return usedSize; } //判断栈是否为空 public boolean empty(){ return usedSize == 0; }}
1.4 栈的应用场景
1. 改变元素的序列
1. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（） A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1 2. 一个栈的初始状态为空。现将元素 1 、 2 、 3 、 4 、 5 、 A 、 B 、 C 、 D 、 E 依次入栈，然后再依次出栈，则元素出栈的顺 序是（ ）。 A: 12345ABCDE B: EDCBA54321 C: ABCDE12345 D: 54321EDCBA2. 将递归转化为循环
//递归方式void printList(Node head){ if(head == null){ return; } printList(head.next); System.out.println(head.val+" ");}//循环方式void printList2(Node head){ if(head == null){ return; } Stackstack = new Stack<>(); //将链表中的元素(节点)放入栈中 Node cur = head; while(cur !=null){ stack.push(cur); cur = cur.next; } //栈中的元素出栈 while (!stack.empty()){ System.out.print(stack.pop().val+" "); }}
3. 括号匹配
代码实现
public boolean isValid(String s) {
Stack
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 ch1 = stack.pop();
if((ch1 =='(' && ch == ')') || (ch1 == '[' && ch == ']') || (ch1 == '{' && ch == '}')){
continue;
} else {
return false;
}
}
}
//栈中还有左括号
if(!stack.empty()){
return false;
}
return true;
}
4. 逆波兰表达式求值
代码实现
public int evalRPN(String[] tokens) {
Stack
stack = new Stack(); for(String s:tokens){
if(!(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/"))){
stack.push(Integer.parseInt(s));
}else{
int num2 = stack.pop();
int num1 = stack.pop();
switch(s){
case "+":
stack.push(num1+num2);
break;
case "-":
stack.push(num1-num2);
break;
case "*":
stack.push(num1*num2);
break;
case "/":
stack.push(num1/num2);
break;
}
}
}
return stack.pop();
}
5. 出栈入栈次序匹配
代码实现
public boolean IsPopOrder (int[] pushV, int[] popV) {
Stack
stack = new Stack<>(); //i遍历pushV，j遍历popV
int i = 0, j = 0;
for(;i < pushV.length; i++){
//入栈
stack.push(pushV[i]);
//获取栈顶元素
int pe = stack.peek();
//判断栈顶元素是否需要出栈
while(pe == popV[j]){
stack.pop();
j++;
//栈空
if(stack.empty()){
break;
}
//判断后面是否需要出栈
pe = stack.peek();
}
}
//栈中还有元素
if(!stack.empty()){
return false;
}
return true;
}
6. 最小栈
代码实现
class MinStack {
//普通栈
private Stack
stack; //最小值栈-》存放当前普通栈中的最小值
private Stack
minStack; public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
//入栈
public void push(int val) {
if(stack.empty()){
stack.push(val);
minStack.push(val);
}else {
stack.push(val);
int peek = minStack.peek();
//判断minStack是否要入栈
if(val <= peek){
minStack.push(val);
}
}
}
//出栈
public void pop() {
//普通栈为空
if(stack.empty()){
return;
}
int po= stack.pop();
//判断minStack是否要出栈
if(po == minStack.peek()){
minStack.pop();
}
}
//获取栈顶元素
public int top() {
//普通栈为空
if(stack.empty()){
return -1;
}
return stack.peek();
}
//获取当前栈中最小值
public int getMin() {
//最小值栈-》 空
if(minStack.empty()){
return -1;
}
return minStack.peek();
}
}
1.5 概念区分
栈、虚拟机栈、栈帧有何区别？
栈是一种数据结构，虚拟机栈是JVM划分的一块内存，栈帧是方法调用时，虚拟机给方法分配的一块内存。
二、队列
2.1 概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特点入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头
2.2 队列的使用
Queue是个接口，底层是通过链表实现。 
| 方法 | 解释 |
| boolean offer(E e) | 入队列 |
| E poll() | 出队列并返回 |
| E peek() | 获取队头元素 |
| int size() | 获取队列中有效长度的个数 |
| boolean isEmpty | 判断队列是否为空 |
Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。
public static void main(String[] args) { Queuequeue = new LinkedList<>(); //入队 queue.offer(1); queue.offer(2); queue.offer(3); System.out.println(queue);//[1, 2, 3] //获取队头元素 int t = queue.peek(); System.out.println(t);//1 //出队 System.out.println(queue.poll());//1 System.out.println(queue);//[2, 3] //判断队列是否为空 boolean bool = queue.isEmpty(); System.out.println(bool);//false}
2.3 队列的模拟实现
队列中可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到 常见的空间类型有两种：顺序结构 和 链式结构，那么 队列的实现使用顺序结构还是链式结构好？
public class MyLinkqueue { static class ListNode{ int val; ListNode next; ListNode pre; public ListNode(int val){ this.val = val; } } ListNode first;//队头 ListNode last;//队尾 int usedsize;//队列中元素个数 //入队列 public boolean offer(int data){ ListNode node = new ListNode(data); if(first == null){ //空队列 first = node; last = node; }else { last.next = node; node.pre = last; last = last.next; } usedsize++; return true; } //获取队头元素 public int peek(){ if(usedsize == 0){ return -1; } return first.val; } //出队列 public int poll(){ int x = peek(); //只有一个元素 if(first.next==null){ first = null; last = null; } first = first.next; first.pre = null; usedsize--; return x; } //获取队列中元素的个数 public int size(){ return usedsize; } //判断队列是否为空 public boolean isEmpty(){ return usedsize == 0; }}
2.4 循环队列
实际中我们有时会使用一种队列叫循环队列，环形队列通常使用数组实现。
设计循环队列 三、双端队列
双端队列（deque）指允许两端都可以进行入队和出队操作的队列，说明元素可以从队头入队和出队，也可以从队尾入队和出队。
Deque是一个接口，使用时必须创建LinkedList的对象。
实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。
Dequestack = new ArrayDeque<>();// 双端队列的线性实现 Dequequeue = new LinkedList<>();//双端队列的链式实现
四、面试题
1、用队列实现栈 链接
代码实现
class MyStack {
private Queue
queue1 ; private Queue
queue2 ; public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
//入栈
public void push(int x) {
//栈为空
if (empty()){
queue1.offer(x);
}else {
//放入非空队列中
if(!queue1.isEmpty()){
queue1.offer(x);
}else {
queue2.offer(x);
}
}
}
//出栈
public int pop() {
//栈空
if(empty()){
return -1;
}
if(!queue1.isEmpty()){
//将queue1中的size-1个元素放入queue2
while (queue1.size()>1){
int x= queue1.poll();
queue2.offer(x);
}
//出队x并返回x
int x = queue1.poll();
return x;
}else {
//将queue2中的size-1个元素放入queue1
while (queue2.size()>1){
int x= queue2.poll();
queue1.offer(x);
}
//出队x并返回x
int x = queue2.poll();
return x;
}
}
//获取栈顶元素
public int top() {
//栈空
if(empty()){
return -1;
}
if(!queue1.isEmpty()){
//将queue1中的size-1个元素放入queue2
while (queue1.size()>1){
int x= queue1.poll();
queue2.offer(x);
}
//出队x放入另一队列并返回x
int x = queue1.poll();
queue2.offer(x);
return x;
}else {
//将queue2中的size-1个元素放入queue1
while (queue2.size()>1){
int x= queue2.poll();
queue1.offer(x);
}
//出队x放入另一队列并返回x
int x = queue2.poll();
queue1.offer(x);
return x;
}
}
//判断栈是否为空
public boolean empty() {
//两个队都为空-》栈为空
return queue1.isEmpty() && queue2.isEmpty();
}
}
2、 用栈实现队列 链接
代码实现
class MyQueue {
private Stack
stack1;//入队 private Stack
stack2;//出队 public MyQueue() {
stack1 = new Stack<>();
sstack2 = new Stack<>();
}
//入队
public void push(int x) {
stack1.push(x);
}
//出队
public int pop() {
//队空
if(empty()){
return -1;
}
//保证stack2不为空
if(stack2.isEmpty()){
while (!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
//获取队头元素
public int peek() {
//队空
if(empty()){
return -1;
}
//保证stack2不为空
if(stack2.isEmpty()){
while (!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
//判断队列是否为空
public boolean empty() {
//两个栈都为空-》队列为空
return stack1.isEmpty() && stack2.isEmpty();
}
}
来源地址：https://blog.csdn.net/qq_64668629/article/details/133172101
