杭州建设职业学校网站,开发软件需要学什么专业,长沙网站开发,wordpress hello dolly目录
前言
1、栈 2、队列
2.1、实现队列
2.2、循环队列 前言
上一篇中我们介绍了数据结构基础中的《动态数组》#xff0c;本篇我们继续来学习两种基本的数据结构——栈和队列。
1、栈
特点#xff1a;栈也是一种线性结构#xff0c;相比数组#xff…目录
前言
1、栈 2、队列
2.1、实现队列
2.2、循环队列 前言
上一篇中我们介绍了数据结构基础中的《动态数组》本篇我们继续来学习两种基本的数据结构——栈和队列。
1、栈
特点栈也是一种线性结构相比数组栈对应的操作是数组的子集只能从一端添加元素也只能从同一端取出元素这一端称为栈顶。栈是一种后进先出的数据结构即Last In First Out(LIFO)。
上面说到栈对应的操作是数组的子集因此我们就基于上一篇中实现的动态数组来快速的实现一个栈。
首先定义一个接口定义相关功能方法 然后让栈来实现接口中的具体功能
import arr.Array;public class ArrayStackE implements StackE {ArrayE array;public ArrayStack(int capacity) {array new Array(capacity);}public ArrayStack() {array new Array();}public int getCapacity() {return array.getCapacity();}Overridepublic int getSize() {return array.getSize();}Overridepublic boolean isEmpty() {return array.isEmpty();}Overridepublic void push(E e) {array.addLast(e);}Overridepublic E pop() {return array.removeLast();}Overridepublic E peek() {return array.getLast();}Overridepublic String toString() {StringBuilder res new StringBuilder();res.append(Stack).append([);for (int i 0; i array.getSize(); i) {res.append(array.get(i));if (i ! array.getSize() - 1) {res.append(,);}}res.append(] Top);return res.toString();}
}
写一个测试方法 执行结果如下 2、队列
2.1、实现队列
队列也是一种线性结构相比数组队列对应的操作也是数组的子集队列只能从一端队尾添加元素只能从另一端队首取出元素。队列是一种先进先出的数据结构先到先得即First In First OutFIFO。
由于队列对应的操作同样是数组的子集那么我们让然也是基于上一篇中实现的动态数组来快速的实现一个栈。
定义一个接口定义相关功能方法 然后让队列来实现接口中的具体功能
import arr.Array;public class ArrayQueueE implements QueueE {private ArrayE array;public ArrayQueue(int capacity) {array new Array(capacity);}public ArrayQueue(){array new Array();}public int getCapacity(){return array.getCapacity();}Overridepublic int getSize() {return array.getSize();}Overridepublic boolean isEmpty() {return array.isEmpty();}Overridepublic void enqueue(E e) {array.addLast(e);}Overridepublic E dequeue() {return array.removeFirst();}Overridepublic E getFront() {return array.getFirst();}Overridepublic String toString() {StringBuilder res new StringBuilder();res.append(Queue:).append(Front [);for (int i 0; i array.getSize(); i) {res.append(array.get(i));if (i ! array.getSize() - 1) {res.append(,);}}res.append(] tail);return res.toString();}
}
同样的写一个测试类 执行结果如下 2.2、循环队列
初始时front和tail都是指向下标为0的位置当有元素入队时tail指向该元素的下一个位置(tail1)%capacity元素出队时front向后移动一个位置因此循环队列有元素出队时无需让所有的元素都移动一个位置只需让front的指向移动一次即可示意图如下
下面我们来通过代码看一下循环队列该怎么实现
public class LoopQueueE implements QueueE {private E[] data;private int front, tail;private int size;public LoopQueue(int capacity) {data (E[]) new Object[capacity 1];front 0;tail 0;size 0;}public LoopQueue() {this(10);}public int getCapacity() {return data.length - 1;}Overridepublic int getSize() {return size;}Overridepublic boolean isEmpty() {return front tail;}Overridepublic void enqueue(E e) {if ((tail 1) % data.length front) {resize(getCapacity() * 2);}data[tail] e;tail (tail 1) % data.length;size;}private void resize(int newCapacity) {E[] newdata (E[]) new Object[newCapacity 1];for (int i 0; i size; i) {newdata[i] data[(i front) % data.length];}data newdata;front 0;tail size;}Overridepublic E dequeue() {if (isEmpty()) {throw new IllegalArgumentException(队列为空);}E ret data[front];data[front] null;front (front 1) % data.length;size--;if (size getCapacity() / 4 getCapacity() / 2 ! 0) {resize(getCapacity() / 2);}return null;}Overridepublic E getFront() {if (isEmpty()) {throw new IllegalArgumentException(队列为空);}return data[front];}Overridepublic String toString() {StringBuilder res new StringBuilder();res.append(String.format(Queue: size%d,capacity%d\n, size, getCapacity())).append(front [);for (int i front; i ! tail; i (i 1) % data.length) {res.append(data[i]);if ((i1)%data.length ! tail) {res.append(,);}}res.append(] tail);return res.toString();}
}
同样的测试程序 执行结果如下 好了关于栈和队列的内容就说这么多吧咱们下期再会
祝工作顺利
