发布时间:2024-04-17 17:01
栈其实就是一种数据结构 - 先进后出(先入栈的数据后出来,最先入栈的数据会被压入栈底)
什么是java虚拟机栈?
java虚拟机栈只是JVM当中的一块内存,该内存一般用来存放 例如:局部变量
当调用函数时,我们会为函数开辟一块内存,叫做 栈帧,在 java虚拟机栈中开辟,具体如下。
常见考点:不可能的出栈顺序
这道题该怎么分析呢?
首先我们知道,出栈时拿到的第一个元素为4,那么4必须入栈,因为入栈的顺序是 1 2 3 4 5 6,所以4要入栈,1 2 3 得先入栈。(通过后面分析得知,该出栈序列正确)
方法 | 作用 |
---|---|
E push(E item) | 放入元素 |
E pop() | 获取栈顶元素并弹出 |
E peek() | 获取栈顶元素 |
boolean isEmpty() | 判断栈是否为空(父类Vector的方法) |
public class MyStack {
public int[] elem;
public int usedSize;
public MyStack() {
this.elem = new int[4];
}
// 放入元素
public void push(int val) {
if(isFull()) {
// 如果放满了,二倍扩容
this.elem = Arrays.copyOf(elem,2 * elem.length);
}
this.elem[this.usedSize++] = val;
}
// 获取栈顶元素并弹出
public int pop() {
if (isEmpty()) {
throw new RuntimeException(\"栈为空!\");
}
usedSize--;
return elem[usedSize];
}
// 获取栈顶元素
public int peek() {
if (isEmpty()) {
throw new RuntimeException(\"栈为空!\");
}
return elem[usedSize-1];
}
// 是否为空
public boolean isEmpty() {
return usedSize == 0;
}
// 是否满了
public boolean isFull() {
return elem.length == usedSize;
}
}
只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有 - 先进先出。
入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头
// 普通队列
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);// 队尾入
int top = queue.peek();// 获取队头元素
queue.poll();// 弹出队尾元素并返回
// 双端队列
Deque<Integer> deque = new LinkedList<>();
deque.offer(1);// 默认队尾入
deque.offerFirst(2);// 队头入
deque.offerLast(3);// 队尾入
deque.peekFirst();// 获取队头元素
deque.peekLast();// 获取队尾元素
deque.pollFirst();// 弹出队头元素并返回
deque.pollLast();// 弹出队尾元素并返回
/**
* 每个节点
*/
class Node{
public int val;
public Node next;
public Node(int val) {
this.val = val;
}
}
public class MyQueue {
public Node head;
public Node tail;
/**
* 插入元素 -- 尾插法
* @param val
*/
public void offer(int val) {
Node node = new Node(val);
if (head == null) {
head = node;
tail = node;
}else {
tail.next = node;
tail = tail.next;
}
}
/**
* 出队列
*/
public int poll() {
if(isEmpty()) {
throw new RuntimeException(\"队列为空!\");
}
int val = head.val;
head = head.next;
return val;
}
/**
* 获取队头元素
*/
public int peek() {
if(isEmpty()) {
throw new RuntimeException(\"队列为空!\");
}
return head.val;
}
// 队列是否为空
public boolean isEmpty() {
return head == null;
}
}
当考虑用数组来实现一个队列, 很容易想到以下结构:
当我们连续从该队头中弹出元素时,就可以发现问题了
可以看到此时数组并没有满,但是当我们再次插入元素时,队尾却插入不了了,这时候我们可以想到将该数组看成是循环的数组,结构如下。
可以看出,当 front 和 rear 相遇时,队列可能的情况有两种,要么为空,要么是满的状态。那么队列什么时候为空,什么时候是满的呢?
我们有两种方法:
1、设置usedSize 当usedSize和数组长度相等时为满,等于0 则为空。
2、设置标志位 设 flag = true,每放一个元素,将 flag 置为 false,每有一个元素出队列,则将 flag 置为 true。当 front 和 rear 相遇时,flag为 true 则是空的,反之则是满的。
public class MyCircularQueue {
public int[] elem;
public int front;// 队头下标
public int rear;// 队尾下标
boolean flag = true;// 是否为空
public MyCircularQueue(int k) {
elem = new int[k];
}
// 向循环队列插入一个元素。如果成功插入则返回真。
public boolean enQueue(int value) {
if (isFull()) {
return false;
// throw new RuntimeException(\"队列已满!\");
}
elem[rear] = value;
rear = (rear + 1) % elem.length;
flag = false;
return true;
}
// 从循环队列中删除一个元素。如果成功删除则返回真。
public boolean deQueue() {
if (isEmpty()) {
return false;
// throw new RuntimeException(\"队列为空!\");
}
front = (front + 1) % elem.length;
flag = true;
return true;
}
// 从队首获取元素。如果队列为空,返回 -1 。
public int Front() {
if (isEmpty()) {
return -1;
// throw new RuntimeException(\"队列为空!\");
}
return elem[front];
}
// 获取队尾元素。如果队列为空,返回 -1 。
public int Rear() {
if (isEmpty()) {
return -1;
// throw new RuntimeException(\"队列为空!\");
}
// 如果是0下标,拿最后一个元素
if (rear == 0) {
return elem[elem.length-1];
}else {
return elem[rear - 1];
}
}
// 检查循环队列是否为空。
public boolean isEmpty() {
if (rear == front && flag){
return true;
}
return false;
}
// 检查循环队列是否已满。
public boolean isFull() {
if (rear == front && !flag){
return true;
}
return false;
}
}