【数据结构和算法】(基础篇三)——栈和队列

栈和队列

栈（Stack）和队列（Queue）是两种非常基本的数据结构，它们主要用于存储和检索元素。尽管它们都用于管理一组数据项，但它们的访问规则和数组都是不同的。

栈

栈是一种后进先出（Last In, First Out，LIFO）的数据结构。这意味着最后插入的元素将是第一个被删除的。在软件开发中，这种数据结构的特性还是经常被使用到的，比如浏览器的后退操作，撤销的操作总是最后执行的。递归的底层其实就使用了栈。

我们把允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素称为空栈。栈又称为后进先出(Last In Filrst Out)的线性标，简称LlFO结构。

栈的特殊之处就在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这也就使得栈底是固定的，最先进栈的只能在栈底。

顺序栈

用数组来实现栈，首先定义栈底和最初的栈顶在同一个位置，为-1，这样可以通过栈顶是否为-1判断是否为空栈。需要实现的功能有如下几个：初始化栈，传入最大值，使用最大值创建数组，用于数据的存储，初始化栈底和栈顶为-1；空栈和满栈判断；入栈和出栈操作；查看栈顶元素

public class mystack {private int size;private int top;private int array[];// 构造函数进行初始化public mystack(int maxSize) {size = maxSize;   // 传入最大值top = -1;   // 初始化toparray = new int[maxSize];  // 数组用来存储数据}// 判断空栈public boolean isEmpty(){return ( top == -1);}// 判断满栈public boolean isFull(){return ( top == size-1);}// 入栈操作public void pushStack(int num){//当前不是满栈才能入栈if (!isFull()){array[++top] = num;  // top最开始是-1，要先++才能赋值System.out.println(num + "入栈成功");}else{System.out.println("栈已满，当前元素："+num+"不能入栈");}}// 出栈操作public void getStack(){// 当前栈非空才能出栈if (!isEmpty()){int temp = array[top--];System.out.println(temp + "出栈成功");}else{System.out.println("栈已空");}}// 查看栈顶元素public void getPop(){// 非空if (!isEmpty()){System.out.println("当前栈顶元素为："+array[top]);}else{System.out.println("栈已空");}}// 测试操作public static void main(String[] args) {mystack ms = new mystack(5);ms.pushStack(1);ms.pushStack(2);ms.pushStack(3);ms.pushStack(4);ms.pushStack(5);ms.getPop();ms.getStack();ms.getPop();}
}

链栈

顺序栈在每次创建栈的时候都需要提供最大值，扩容操作比较麻烦，使用链表的原理实现栈可以拥有更灵活的存储空间。但是顺序栈的存取定位更方便，如果整个栈的变化才可以预料的范围内，使用顺序栈更方便。两者各有优缺点，需要根据实际情况进行取用。

链栈的实现可以把top放在头节点，判断空栈就判断top是否为null即可；链栈的大小是弹性的，不需要对bottom和size进行限定，也不需要判断满栈

package dataStructure.stack;public class ListStack {private Node top;// 定义链表节点private static class Node{int data;Node next;public Node(int data) {this.data = data;this.next = null;}}// 构造函数初始化栈public ListStack() {top = null;}// 判断空栈public boolean isEmpty(){return (top == null);}// 入栈操作public void pushStack(Node node){node.next = top;top = node;System.out.println("节点："+node.data+"成功入栈");}// 出栈操作public void  getStack(){// 非空才能出栈if (!isEmpty()){System.out.println("节点："+top.data+"出战成功");top = top.next;}else{System.out.println("栈已空");}}// 查看栈顶元素public void getPop(){// 非空才能出栈if (!isEmpty()){System.out.println("当前栈顶元素为："+top.data);}else{System.out.println("栈已空");}}// 测试操作public static void main(String[] args) {ListStack ls = new ListStack();ls.pushStack(new Node(1));ls.pushStack(new Node(2));ls.pushStack(new Node(3));ls.pushStack(new Node(4));ls.pushStack(new Node(5));ls.getPop();ls.getStack();ls.getPop();}
}

java的封装

java已经为我们封装好了栈的数据结构，我们只需要在使用的时候调用即可，在java.util包中的Stack模块，其具体方法如下所示：

package dataStructure.stack;import java.util.Stack;public class JavaStack {public static void main(String[] args) {Stack<Integer> stack = new Stack<>();// 入栈stack.push(1);stack.push(2);stack.push(3);// 查看栈顶元素System.out.println("当前栈顶元素: " + stack.peek());// 出栈System.out.println("出栈元素: " + stack.pop());// 检查是否为空System.out.println("是否为空栈? " + stack.isEmpty());// 遍历栈中的所有元素System.out.println("栈中所有元素:");while (!stack.isEmpty()) {System.out.println(stack.pop());}}
}

队列

队列( queue ) 是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出( First In First Out) 的线性表，简称FIFO 。允许插入的一端称为队尾，允许删除的一端称为队头。

线性表有顺序存储和链式存储，栈是线性表，所以有这两种存储方式。同样，队列作为一种特殊的钱性表，也同样存在这两种存储方式。

循环队列

我们假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即是队头。所谓的入队列操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为O(1)

与栈不同的是，队列元素的出列是在队头，即下标为0 的位置，那也就意味着，队列中的所有元素都得向前移动，以保证队列的队头，也就是下标为0的位置不为空，此时时间复杂度为O(n)

有一个好方法可以不用每次都移动所有数据，让操作变得简单，我们只需要将队头向后移动即可

为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针， front指针指向队头元素， rear指针指向队尾元素的下一个位置，这样当的front等于rear时，此队列不是还剩一个元素，而是空队列。

但是如果一直按照上面的操作进行的话，front和rear都会一直向后移动，这样的话数组多大都不够用，让rear超出数组的时候，我们可以让它回到0的位置进行循环，把之前空出的位置利用起来

这样的话又会有一个新问题，就是rear会再次与front重合，此时rear == front就表示队列满了，但是我们最开始的时候rear == front又表示空队列

解决的办法就是设置一个flag，当front == rear ，且flag = 0 时为队列空，当front == rear，且flag= 1时为队列满。办法二是当队列空时，条件就是front = rear，当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。

因为rear既可能比front大，也可能比front小，第二种方法的具体计算公式是这样的：(rear+1) % QueueSize == front

package dataStructure.queue;// 用顺序表实现循环队列
public class CircularQueue {private final int capacity;private final int[] queue;private int front;private int rear;private int count;public CircularQueue(int capacity) {this.capacity = capacity;this.queue = new int[capacity];this.front = 0;this.rear = -1;this.count = 0;}// 入队操作public boolean enqueue(int value) {if (isFull()) {return false;}rear = (rear + 1) % capacity;queue[rear] = value;count++;return true;}// 出队操作public int dequeue() {if (isEmpty()) {throw new IllegalStateException("Queue is empty");}int removedValue = queue[front];front = (front + 1) % capacity;count--;return removedValue;}// 查看队首元素public int peek() {if (isEmpty()) {throw new IllegalStateException("Queue is empty");}return queue[front];}// 检查队列是否为空public boolean isEmpty() {return count == 0;}// 检查队列是否已满public boolean isFull() {return count == capacity;}// 测试代码public static void main(String[] args) {CircularQueue queue = new CircularQueue(5);  // 创建一个容量为5的循环队列// 测试入队和出队操作for (int i = 0; i < 6; i++) {if (queue.enqueue(i)) {System.out.println(i + " enqueued");} else {System.out.println("Queue full, cannot enqueue " + i);}}while (!queue.isEmpty()) {System.out.println(queue.dequeue() + " dequeued");}// 尝试从空队列中出队try {System.out.println(queue.dequeue());} catch (IllegalStateException e) {System.out.println(e.getMessage());}}
}

链队列

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。我们将头节点和尾节点设置为队头和队尾，这样就可以了。

package dataStructure.queue;// 用顺序表实现循环队列
public class LinkedListQueue {// 定义链表节点public static class Node{int data;Node next;public Node(int data) {this.data = data;this.next = null;}}private Node front;private Node rear;private int count;public LinkedListQueue() {this.front = null;this.rear = null;this.count = 0;}// 检查队列是否为空public boolean isEmpty() {return count == 0;}// 入队操作public void enqueue(Node newNode) {if (rear == null){  // 往空队列中添加数据front = newNode;rear = newNode;}else {rear.next = newNode;newNode.next = null;}count ++;System.out.println("数据"+ newNode.data+"入队成功");}// 出队操作public void dequeue() {if (count > 0) {System.out.println("数据"+ front.data+"出队成功");front = front.next;count --;}elseSystem.out.println("队列已空");}// 测试代码public static void main(String[] args) {LinkedListQueue lq = new LinkedListQueue();lq.enqueue(new Node(1));lq.enqueue(new Node(2));lq.enqueue(new Node(3));lq.enqueue(new Node(4));lq.enqueue(new Node(5));lq.dequeue();}
}