高价做单网站,安阳市网站建设,网站建设云梦,网站正常打开速度栈的概念
栈是一种先进后出的线性表#xff0c;只允许在固定的一端进行插入和删除操作。 进行插入和删除操作的一端被称为栈顶#xff0c;另一端被称为栈底 栈的插入操作叫做进栈/压栈/入栈 栈的删除操作叫做出栈 现实生活中栈的例子#xff1a;
栈的模拟实现
下面是Jav…栈的概念
栈是一种先进后出的线性表只允许在固定的一端进行插入和删除操作。 进行插入和删除操作的一端被称为栈顶另一端被称为栈底 栈的插入操作叫做进栈/压栈/入栈 栈的删除操作叫做出栈 现实生活中栈的例子
栈的模拟实现
下面是Java集合类给我们提供的栈的方法 模拟实现顺序栈
我们通过数组来模拟实现栈。
构建数组栈
我们需要两个成员变量一个是数组另一个是记录当前的数据个数。 public int[] elem;public int usedSize;public MyStack() {elem new int[5];}push
要考虑扩容问题 private boolean isFull() {if(usedSize elem.length) {return true;}return false;}private void grow() {elem Arrays.copyOf(elem,2*elem.length);}public void push(int val) {if(isFull()) {grow();}elem[usedSize] val;}isEmpty
判断栈是否为空 public boolean isEmpty() {return usedSize 0;}pop
设置自定义异常
public class PopException extends RuntimeException{public PopException() {super();}public PopException(String message) {super(message);}
}删除栈顶的同时还会返回删除的元素 private void checkPop() throws PopException{if(isEmpty()) {//抛异常throw new PopException(栈已空无法删除);}}public int pop() {try {checkPop();int ret elem[usedSize-1];usedSize--;return ret;} catch (PopException e) {e.printStackTrace();}return -1;}peek 获取栈顶元素 但是不删除 public int peek() {try {checkPop();return elem[usedSize-1];} catch (PopException e) {e.printStackTrace();}return -1;}链式栈
链式栈顾名思义就是利用链表来保存栈
假设使用单链表制作链式栈建议使用头插和头删法来进行push和pop操作peak直接把头节点的值获取即可这样时间复杂度可以为O1但是如果你使用尾插和尾删就是以尾节点的位置作为栈顶在pushpop 和 peak 的时候时间复杂度为ON
假设使用双向无头循环链表无论是选择头插头删还是尾插尾删作为push与pop时间复杂度都是O1
这里就不演示链式栈的代码。
Stack 的使用 push 入栈pop 出栈peak 获取栈顶元素empty 是否为空size 这个获取有效元素的方法是在Vector 中的search 找到某元素距离栈顶元素的距离多少栈顶元素记为1然后一直到目标元素
栈、虚拟机栈、栈帧有什么区别呢 栈是我们的数据结构的其中一种形式虚拟机栈是JVM虚拟机的一块内存栈帧是运行一个方法或者函数的时候计算机给它开辟的内存。 队列的概念
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out) 入队列进行插入操作的一端称为队尾Tail/Rear 出队列进行删除操作的一端称为队头Head/Front
队列类似我们生活中的排队。 队列的模拟实现 上面是Java集合类给我们提供的队列的方法其中add和offer都是入队操作poll 和 remove 都是出队操作element 和 peek 都是获取队列头部的元素。
它们主要的区别是会不会抛异常~~ 下面有详细的介绍 链式队列
这里我们将使用数组来模拟实现队列并且这里只实现下图所示的方法
size 和 isEmpty 是队列继承的方法并且队列没有重写这两个方法所以上面的IDEA直接看队列的Structure 是看不到的。 假设我们使用单链表为基础该怎么实现队列 假设入队采用尾插那要出队即使用头删即可 出队列使用单链表的头删即可时间复杂度为O1 入队列使用尾插一般情况下单链表实现尾插首先要找到尾然后才是开始插入这时候时间复杂度就尾ON不是最优解我们可以加一个尾指针保存好尾节点这样就方便我们快速进行尾插操作。
假设入队使用头插那出队的时候就需要使用尾删 这时候就不好弄了即使你有尾指针在进行尾删的时候还是需要遍历链表找到尾节点的前一个结点才能完成尾删这时候你可能会认为再定义一个指针这就很麻烦了。
所以单链表构建队列的话限制条件有点大但是使用上一片文章的双向链表无头双向循环链表 LinkedList 就可以随意选取一端作为入队另一端作为出队。
这里我们入队采用尾插出队采用头删
public class MyQueue {public static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val val;}}public ListNode head;public ListNode last;//入队public boolean offer(int data) {ListNode node new ListNode(data);if(isEmpty()) {last head node;} else {last.next node;node.prev last;last node;}return true;}public boolean isEmpty() {return head null;}//出队public int poll() {if(isEmpty()) {return -1;}int ret head.val;if(head.next ! null) {head.next.prev null;}head head.next;return ret;}//求结点个数public int size() {ListNode cur head;int count 0;while(cur ! null) {count;cur cur.next;}return count;}//获取队头元素public int peek() {if(isEmpty()) {return -1;}return head.val;}
}这里要注意出队的代码如果只有一个结点的情况下你进行删除后就没有结点了head.next.prev null 这行代码就会发生报错。
顺序队列
顺序队列我们采用数组来实现队列这时候我们就要思考一个问题在不断的出队入队的情况下怎么保证空间尽可能地利用起来 假设数组的数据已满装满的情况下我们一直出队直到数组变空的话怎么利用起来前面的空间 循环队列
这时候我们就需要使用循环队列让队列的空间有效的利用起来。 法1 定义一个成员变量usedSize 记录使用了多少的空间 法2 定义一个标记符记录空间是否已满 法3 浪费一个空间通过数学公式判断队列是否已满 一般情况下我们会认为这就是队列空和满的两种状态但是这两种状态都是 front near怎么办 根据法1我们可以记录使用了多少空间的usedSize 来判断队列是否已满即 usedSize 数组的长度即可认为队列已满 根据法2我们使用标记符首先 将标记符记为 -1认为队列没满当front 与near 再次相遇时标记符乘 -1 变为1 判断 队列 已满如果下一个操作时出队那标记符再自乘 -1变回 -1 当front 与 rear 再次相遇时标记符自乘 -1 变为1 表示队列已满以此类推这里大家可以自由发挥。 第三个方法是利用队列自身来进行判断当 rear 的下一个就是 front 的时候即 ( rear 1 ) % 数组长度 front就判断队列已满这需要我们浪费队列的一个空间。 如何让rear 和 front 循环起来呢即rear 的下标该如何制定呢 这里有一个公式当 rear 要 自增的时候新的 rear ( rear 1 ) % 数组长度就是此时rear 对应的实际下标当 rear 为 7 时rear 向下移动一格时新的 rear 就是 ( 7 1 ) % 8 0 正好就是 7 下一个的下标值 0 问题拓展 数组下标循环的小技巧 下标往后移动(offset 小于 array.length): index (index offset) % array.length 下标往前移动(offset 小于 array.length): index (index array.length - offset) % array.length array.length - offset 其实就是变相地让 小标变成向后 移动。 顺序队列的代码
public class MyQueue {int front;int rear;int[] elem;public MyQueue() {elem new int[4];}//入队public boolean offer(int data) {if(isFull()) {return false;}elem[rear] data;rear (rear 1) % elem.length;return true;}//队列是否已满private boolean isFull() {return (rear 1) % elem.length front;}//队列是否为空public boolean isEmpty() {return rear front;}//出队public int poll() {if(isEmpty()) {return -1;}int ret elem[front];front (front 1) % elem.length;return ret;}//求元素个数public int size() {int count 0;for (int i front; i rear; i) {count;}return count;}//获取队头元素public int peek() {if(isEmpty()) {return -1;}return elem[front];}
}
Queue 上面是我们常用的队列方法 队列Queue本质上是一个接口所以Queue 不能被实例化那如何使用
Deque 双端队列 双端队列deque是指允许两端都可以进行入队和出队操作的队列deque 是 “double ended queue” 的简称。 那就说明元素可以从队头出队和入队也可以从队尾出队和入队。 我们可以发现 Deque 其实是继承了 Queue 接口但是还是一个接口还是不能实例化那怎么使用请看下面解说。
LinkedList 和栈与队列的关系 LinkedList 有很多接口其中包括了 Deque 而Deque 这个接口其实继承了 Queue 也就是队列所以我们可以实例化 一个LinkedList 对象然后通过 Queue 接收就可以使用普通队列的方法同理通过实例化一个LinkedList 对象然后通过 Deque 接收就可以使用双端队列的方法 public static void main(String[] args) {LinkedListInteger linkedList new LinkedList();linkedList.push(1);linkedList.push(2);linkedList.push(3);System.out.println(linkedList.peek());System.out.println(linkedList.pop());System.out.println(linkedList.peek());}LinkedList还可以当成栈来使用也就是说LinkedList还包含栈的方法自身功能很强大。 小结 LinkedList 不仅可以作为不带头的双向循环链表使用还可以当成栈或者队列使用。 在实际工程中使用Deque接口是比较多的栈和队列均可以使用该接口。
DequeInteger stack new ArrayDeque();//双端队列的线性实现
DequeInteger queue new LinkedList();//双端队列的链式实现习题链接 http://t.csdnimg.cn/aV91m
