Java 栈与队列超详细分析讲解

Java 栈与队列超详细分析讲解

目录一、栈（Stack）1、什么是栈？2、栈的常见方法3、自己实现一个栈（底层用一个数组实现）二、队列（Queue）1、什么是队列？2、队列的常见方法3、队列的实现（单链表实现）4、循环队列

一、栈（Stack）

1、什么是栈？

栈其实就是一种数据结构 - 先进后出（先入栈的数据后出来，最先入栈的数据会被压入栈底）

什么是java虚拟机栈？

java虚拟机栈只是JVM当中的一块内存，该内存一般用来存放 例如：局部变量当调用函数时，我们会为函数开辟一块内存，叫做 栈帧，在 java虚拟机栈中开辟，具体如下。

常见考点：不可能的出栈顺序

这道题该怎么分析呢？

首先我们知道，出栈时拿到的第一个元素为4，那么4必须入栈，因为入栈的顺序是 1 2 3 4 5 6，所以4要入栈，1 2 3 得先入栈。（通过后面分析得知，该出栈序列正确）

2、栈的常见方法

方法作用E push(E item)放入元素E pop()获取栈顶元素并弹出E peek()获取栈顶元素boolean isEmpty()判断栈是否为空（父类Vector的方法）

3、自己实现一个栈（底层用一个数组实现）

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];

}

// 是否为空

GxOPr public boolean isEmpty() {

return usedSize == 0;

}

// 是否满了

public boolean isFull() {

return elem.length == usedSize;

}

}

二、队列（Queue）

1、什么是队列？

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有 - 先进先出。

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

2、队列的常见方法

// 普通队列

Queue queue = new LinkedList<>();

queue.offer(1);// 队尾入

int top = queue.peek();// 获取队头元素

queue.poll();// 弹出队尾元素并返回

// 双端队列

Deque deque = new LinkedList<>();

deque.offer(1);// 默认队尾入

deque.offerFirst(2);// 队头入

deque.offerLast(3);// 队尾入

deque.peekFirst();// 获取队头元素

deque.peekLast();// 获取队尾元素

deque.pollFirst();// 弹出队头元素并返回

deque.pollLast();// 弹出队尾元素并返回

3、队列的实现（单链表实现）

/**

* 每个节点

*/

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;

}

}

4、循环队列

当考虑用数组来实现一个队列， 很容易想到以下结构：

当我们连续从该队头中弹出元素时，就可以发现问题了

可以看到此时数组并没有满，但是当我们再次插入元素时，队尾却插入不了了，这时候我们可以想到将该数组看成是循环的数组，结构如下。

可以看出，当 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;

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。