目录
一、栈
1.1 概念
1.2 栈的使用
1.3 栈的模拟实现
1.4 栈的应用场景
1.5 概念区分
二、队列
2.1 概念
2.2 队列的使用
2.3 队列的模拟实现
2.4 循环队列
三、双端队列
四、面试题
一、栈
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());//5System.out.println(stack); //[1, 2, 3, 4, 5]stack.pop();//出栈 5System.out.println(stack.size());//4System.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. 括号匹配
4. 逆波兰表达式求值
5. 出栈入栈次序匹配
6. 最小栈
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());//1System.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、用队列实现栈 链接
2、 用栈实现队列 链接