栈和队列-Java
目录
一、栈
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) {
Stack<Integer> stack = 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,12.
一个栈的初始状态为空。现将元素
1
、
2
、
3
、
4
、
5
、
A
、
B
、
C
、
D
、
E
依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。A: 12345ABCDE B: EDCBA54321 C: ABCDE12345 D: 54321EDCBA
//递归方式 void printList(Node head){ if(head == null){ return; } printList(head.next); System.out.println(head.val+" "); } //循环方式 void printList2(Node head){ if(head == null){ return; } Stack<LinkList.Node> stack = 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<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()){
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<Integer> 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<Integer> 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<Integer> stack;
//最小值栈-》存放当前普通栈中的最小值
private Stack<Integer> 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 队列的使用
| 方法 | 解释 |
| boolean offer(E e) | 入队列 |
| E poll() | 出队列并返回 |
| E peek() | 获取队头元素 |
| int size() | 获取队列中有效长度的个数 |
| boolean isEmpty | 判断队列是否为空 |
Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。
public static void main(String[] args) {
Queue<Integer> queue = 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接口是比较多的，栈和队列均可以使用该接口。
Deque<Integer> stack = new ArrayDeque<>();//
双端队列的线性实现Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现
四、面试题
1、用队列实现栈 链接
代码实现
class MyStack {
private Queue<Integer> queue1 ;
private Queue<Integer> 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<Integer> stack1;//入队
private Stack<Integer> 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();
}
}