个人网站一定要备案吗,运营的网站,外贸进口流程,网站建设中国的发展栈和队列
栈#xff08;Stack#xff09;和队列#xff08;Queue#xff09;是两种非常基本的数据结构#xff0c;它们主要用于存储和检索元素。尽管它们都用于管理一组数据项#xff0c;但它们的访问规则和数组都是不同的。
栈
栈是一种后进先出#xff08;Last In,…栈和队列
栈Stack和队列Queue是两种非常基本的数据结构它们主要用于存储和检索元素。尽管它们都用于管理一组数据项但它们的访问规则和数组都是不同的。
栈
栈是一种后进先出Last In, First OutLIFO的数据结构。这意味着最后插入的元素将是第一个被删除的。在软件开发中这种数据结构的特性还是经常被使用到的比如浏览器的后退操作撤销的操作总是最后执行的。递归的底层其实就使用了栈。
我们把允许插入和删除的一端称为栈顶(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) {StackInteger 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小第二种方法的具体计算公式是这样的(rear1) % 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();}
}
