-
java用数组实现队列和栈
2019-03-04 18:38:271、实现栈结构:栈结构是先进后出,只需要一个数组和一个记录位置的变量size,当进来一个元素,size++,当出去一个元素则size--。 2、实现队列结构:队列先进先出,需要一个数组和三个变量,size记录已经进来了多少...分析:用数组实现大小固定的栈和队列
1、实现栈结构:栈结构是先进后出,只需要一个数组和一个记录位置的变量size,当进来一个元素,size++,当出去一个元素则size--。
2、实现队列结构:队列先进先出,需要一个数组和三个变量,size记录已经进来了多少个元素,in记录刚进来的元素放置在哪个位置,out表示用户要求弹出元素所在的位置。其中size还是in与out的操作的关键信息。
实现:
栈的实现:
package stack1;
public class Stack1 {
public static class MyStack{
private int size;//指针位置,也表示栈已经压了多少
private int[]arr;
MyStack(int iniSize){//构造方法初始化数组
arr = new int[iniSize];
size = 0;
}
public void push(int num){
if(size == arr.length){
throw new RuntimeException("栈下标越界!");
}
arr[size++] = num;
}
public int pop(){
if(size == 0){
throw new RuntimeException("栈中已经没有元素可以弹出!");
}
return arr[--size];
}
public int peek(){
if(size == 0){
throw new RuntimeException("栈中已经没有元素可以弹出!");
}
return arr[size];
}
}
public static void main(String[] args) {
int len = 13;
MyStack myStack = new MyStack(len);
for (int i = 0; i < len; i++) {
myStack.push(i);
}
for (int i = 0; i < len; i++) {
System.out.println(myStack.pop());
}
}
}队列的实现:
package stack1;
public class Queue1 {
public static class MyQueue{
private int out;//新进来的数 放这
private int in;//用户要求弹出的数
private int size;//已经进队列的个数
private int arr[];
public MyQueue(int iniSize){
arr = new int[iniSize];
size = 0;
in = 0;
out = 0;
}
public void push(int num){
if(size==arr.length){
throw new RuntimeException("the queue is full!");
}
size++;//大小扩展一个
arr[in] = num;//赋值
in = in==arr.length-1 ? 0 : in+1;//如果已经到达数组末尾就重新等于0
}
public int pull(){
if(size==0){
throw new RuntimeException("the queue is empty!");
}
size--;
int t = out;//记录
out = out==arr.length-1 ? 0 : out+1;//如果已经到达数组末尾就重新等于0
return arr[t];
}
public int peek(){
if(size==0){
throw new RuntimeException("the queue is empty!");
}
return arr[out];
}
}
public static void main(String[] args) {
int iniSize = 3;
MyQueue myQueue = new MyQueue(iniSize);
myQueue.push(12);
myQueue.push(13);
myQueue.push(15);
System.out.println(myQueue.pull());
System.out.println(myQueue.pull());
System.out.println(myQueue.pull());
myQueue.push(23);
myQueue.push(24);
System.out.println(myQueue.pull());
System.out.println(myQueue.peek());
}
} -
next数组_栈 | 如何使用数组和链表实现“栈”
2020-12-02 08:54:07栈只能从表的一端存取数据,另一端是封闭的在栈中,无论是存数据还是取数据,都必须遵循"先进后出(LIFO)"的原则,即最先进栈的元素最后出栈。上图 的栈来说,从图中数据的存储状态可判断出,元素 1 是最先进的栈。...栈是用来存储逻辑关系为 "一对一" 数据的线性存储结构
后进去先出来。
栈的存储结构中关键的在于:存与取。
栈只能从表的一端存取数据,另一端是封闭的
在栈中,无论是存数据还是取数据,都必须遵循"先进后出(LIFO)"的原则,即最先进栈的元素最后出栈。上图 的栈来说,从图中数据的存储状态可判断出,元素 1 是最先进的栈。因此,当需要从栈中取出元素 1 时,根据"先进后出"的原则,需提前将元素 3 和元素 2 从栈中取出,然后才能成功取出元素 1。
把上图的栈立起来就是这样子的(这样或许更好理解)。
实现一个栈的数据结构,使其具有以下方法:压栈、弹栈、取栈顶元素、判断栈是否为空以及获取栈中元素个数。下面是一个栈的入栈和出栈整个过程
栈的实现有两种方法,分别为采用数组来实现和采用链表来实现。下面分别详细介绍这两种方法。
数组实现
分析
在采用数组来实现栈的时候,栈空间是一段连续的空间。实现思路如下图所示
从上图中可以看出,可以把数组的首元素当作栈底,同时记录栈中元素的个数size,假设数组首地址为arr,压栈的操作其实是把待压栈的元素放到数组arr[size]中,然后执行size++操作;同理,弹栈操作其实是取数组arr[size-1]元素,然后执行size--操作。根据这个原理可以非常容易实现栈。
代码实现
/*** 数组使用栈** @author tian* @date 2020/4/26*/public class MyStackDemo { public static void main(String[] args) { ArrayStack stackDemo = new ArrayStack(); //入栈两个元素 stackDemo.push(1); stackDemo.push(2); System.out.println("栈顶元素:" + stackDemo.top()); System.out.println("栈大小:" + stackDemo.size()); stackDemo.pop(); System.out.println("栈第一次弹出元素"); stackDemo.pop(); System.out.println("栈第二次弹出元素"); stackDemo.pop(); }}class ArrayStack { private ArrayList arrayList; private int stackSize; public ArrayStack() { this.stackSize = 0; this.arrayList = new ArrayList<>(); } int size() { return stackSize; } boolean isEmpty() { return this.stackSize == 0; } //返回栈顶元素 T top() { if (isEmpty()) { return null; } return arrayList.get(stackSize - 1); } //元素出栈 T pop() { if (stackSize > 0) { return arrayList.get(--stackSize); } else { System.out.println("栈中无元素了"); return null; } } //元素入栈 void push(T item) { arrayList.add(item); stackSize++; }}
运行输出
链表实现
分析
在创建链表的时候经常采用一种从头结点插入新结点的方法,可以采用这种方法来实现栈,最好使用带头结点的链表,这样可以保证对每个结点的操作都是相同的,实现思路如下图所示。
在上图中,在进行压栈操作时,首先需要创建新的结点,把待压栈的元素放到新结点的数据域中,然后只需要(1)和(2)两步就实现了压栈操作(把新结点加到了链表首部)。同理,在弹栈的时候,只需要进行步骤(3)的操作就可以删除链表的第一个元素,从而实现弹栈操作。
代码实现
/*** 数组实现栈** @author tian* @date 2020/4/26*/public class NodeStackDemo { private MyNode head; public NodeStackDemo() { this.head = new MyNode<>(); head.data = null; head.next = null; } //判断栈是否为空 boolean isEmpty() { return head == null; } //栈的大小 int size() { int size = 0; MyNode p = head.next; while (p != null) { p = p.next; size++; } return size; } void push(T e) { MyNode temp = new MyNode<>(); temp.data = e; temp.next = head.next; head.next = temp; } //出栈,同时返回栈顶元素 T pop() { MyNode temp = head.next; if (temp != null) { head.next = temp.next; return temp.data; } System.out.println("占中已经不存元素了"); return null; } //获取栈顶元素 T top() { if (head.next != null) { return head.next.data; } System.out.println("栈中不存在元素"); return null; } public static void main(String[] args) { NodeStackDemo stackDemo = new NodeStackDemo(); stackDemo.push(1); stackDemo.push(3); stackDemo.push(5); System.out.println("栈顶元素:" + stackDemo.top()); System.out.println("栈大小:" + stackDemo.size()); stackDemo.pop(); System.out.println("栈第一次弹出元素"); stackDemo.pop(); System.out.println("栈第二次弹出元素"); stackDemo.pop(); System.out.println("栈第二次弹出元素"); stackDemo.pop(); }}class MyNode { T data; MyNode next;}
运行结果
两种方法的对比
采用数组实现栈的优点:一个元素值占用一个存储空间;它的缺点:如果初始化申请的存储空间太大,会造成空间的浪费,如果申请的存储空间太小,后期会经常需要扩充存储空间,扩充存储空间是个费时的操作,这样会造成性能的下降。采用链表实现栈的优点:使用灵活方便,只有在需要的时候才会申请空间。它的缺点:除了要存储元素外,还需要额外的存储空间存储指针信息。
算法性能分析:这两种方法压栈与弹栈的时间复杂度都为O(1)。
-
数据结构--队列的实现(采用数组方式)
2020-04-09 23:24:00队列是一种先进先出的线性表(first in first out,简称FIFO)。它只允许在队列的一段插入数据,另一端取出数据。允许插入数据的一端叫做队尾(rear),允许删除的一段则称为队头(front)。 队列无论在实际生活中...队列概述
队列是一种先进先出的线性表(first in first out,简称FIFO)。它只允许在队列的一段插入数据,另一端取出数据。允许插入数据的一端叫做队尾(rear),允许删除的一段则称为队头(front)。
队列无论在实际生活中还是在开发中都是非常常见的。比如我们去银行办理业务的排号系统就是队列。消息中间件也是队列的思想。队列ADT
下面给出队列的抽象定义,在后文中我们将以此ADT开发队列的实现。
/** * @author jaune * @since 1.0.0 */ public interface Queue<E> { /** * 查看队列中的第一个元素,仅仅查看元素,不从队列中取出。 * @return 队列中的第一个元素 * @throws NoSuchElementException 队列为空时抛出 */ E peek(); /** * 向队列中添加元素,元素添加到队尾。 */ void push(E e); /** * 从队列中取出第一个元素。 * @return 队列中的第一个元素。 * @throws NoSuchElementException 队列为空时抛出 */ E pop(); /** * 清空队列并 */ void clear(); /** * 队列中元素的数量,如果队列为空,则返回0 * * @return 队列中元素的数量 */ int size(); /** * 判断队列是否为空 * @return true-空,false-非空 */ boolean isEmpty(); /** * 判断队列是已满 * @return true-已满,false-未满 */ boolean isFull(); }
使用数组实现的基本思想
定义两个指针,一个指向队头(
front
),一个指向队尾(rear
)。
当从队列中取出元素时,front
指针后移;当向队列中添加元素时rear
指针后移。
当队头和队尾在同一个位置时,队列为空。
采用数组的方式实现队列的最大问题就是,当front
和rear
指针全部指向队列的尾部时,队列失效了。无法添加新的元素至队列中。当添加元素时因为指针指向队尾,所以出现队列已满的情况。在后面我将介绍如何处理这种情况。在本文中对这种情况不做处理。
代码实现
package com.codestd.study.queue; import java.util.NoSuchElementException; /** * 数组队列的实现 * * @author jaune * @since 1.0.0 */ public class ArrayQueue<T> implements Queue<T> { final int maxSize; final T[] queueArray; private int front = -1; private int rear = -1; public ArrayQueue(int maxSize) { this.maxSize = maxSize; this.queueArray = (T[]) new Object[maxSize]; } @Override public T peek() { if (this.isEmpty()) { throw new NoSuchElementException("队列为空"); } return this.queueArray[this.front + 1]; } @Override public void push(T t) { if (this.isFull()) { throw new RuntimeException("队列已满,无法添加新的元素。"); } this.queueArray[++this.rear] = t; } @Override public T pop() { if (this.isEmpty()) { throw new NoSuchElementException("队列为空"); } T element = this.queueArray[++this.front]; this.queueArray[this.front] = null; return element; } @Override public int size() { return this.rear - this.front; } /** * 清空队列,并重置队头和队尾指针。 */ @Override public void clear() { for (int i = (this.front + 1); i <= this.rear; i++) { this.queueArray[i] = null; } this.front = -1; this.rear = -1; } @Override public boolean isEmpty() { return this.rear == this.front; } @Override public boolean isFull() { return this.rear + 1 == this.maxSize; } }
测试代码
package com.codestd.study.queue; import org.junit.Test; import static org.assertj.core.api.Assertions.*; /** * Test for {@link ArrayQueue} */ public class ArrayQueueTest { @Test public void test() { Queue<Integer> queue = new ArrayQueue<>(3); assertThat(queue.isEmpty()).isTrue(); assertThat(queue.isFull()).isFalse(); queue.push(1); assertThat(queue.isEmpty()).isFalse(); assertThat(queue.peek()).isEqualTo(1); assertThat(queue.size()).isEqualTo(1); int el = queue.pop(); assertThat(queue.isEmpty()).isTrue(); assertThat(el).isEqualTo(1); queue.push(2); queue.push(3); assertThat(queue.isEmpty()).isFalse(); assertThat(queue.isFull()).isTrue(); assertThat(queue.size()).isEqualTo(2); el = queue.pop(); assertThat(el).isEqualTo(2); el = queue.pop(); assertThat(el).isEqualTo(3); assertThat(queue.isFull()).isTrue(); assertThat(queue.isEmpty()).isTrue(); queue.clear(); assertThat(queue.isEmpty()).isTrue(); assertThat(queue.isFull()).isFalse(); queue.push(1); queue.clear(); assertThat(queue.isEmpty()).isTrue(); assertThat(queue.isFull()).isFalse(); } }
总结
前文中已经提到这种方式存在严重的问题,这是一个一次性的队列。在队列满了之后,就无法再往队列中插入数据了,哪怕数组中有空位置。要解决这个问题就需要用到环形数组。这部分的实现原理在下一篇文章中将。
-
前端细节大全(二):javascript关于数组栈和队列的细节分析
2019-02-18 20:58:44在开始讲之前,我们都必须明白的一点就是栈和队列数据进出的方式:栈是先进后出的,队列是先进先出的。在数据结构中,这两个算法模式都是很常见或者说最基础和最重要的一部分,数据如何存储的,都基本离不开栈和...导读
在开始讲之前,我们都必须明白的一点就是栈和队列数据进出的方式:栈是先进后出的,队列是先进先出的。在数据结构中,这两个算法模式都是很常见或者说最基础和最重要的一部分,数据如何存储的,都基本离不开栈和队列。但是js中的栈和队列和一般的语言有一些区别,实际上就好像把队列看成栈一样,实际上还是有差别的并且遵循的原理也依然没有变。
一、js中的数组栈和队列
发现问题:
var stack=[]; stack.push("a"); stack.push("b"); stack.push("c"); console.log(stack.pop()); console.log(stack.pop()); var queue = []; queue.unshift("a"); queue.unshift("b"); queue.unshift("c"); console.log(queue.shift()); console.log(queue.shift());
结果输出:
上面是出现疑问的代码,首先对于栈而言,就是输出cb没有任何疑问。但是为什么队列也是输出cb呢?接下来看我们的解释。
1.栈
首先,栈是先进后出的,例如现在给出一组一维数组为[a,b,c],
压栈顺序应该是abc
出栈顺序为:cba。
总结:
栈,在js中的栈中存入值是从头部插入数据的,在尾部输出或者拿走数据,此时a的左边就像被堵住了,必须要在右边拿数据,这是因为是栈的特性必须遵循先进后出的原理。这个相信很多人都懂,也很多人能够理解,先进后出嘛,就是最先进入的数据就最后才出来的意思,在图和逻辑上基本是和平常人思维一致的,但是到js的数组队列中就发现一个问题了。2.队列
同样进入三个值abc,假设和栈的数组一样,从左往右阅读。
队列从尾部插入数据
出去的顺序为:cba。从头部出来数据。
总结:
此时很多人都会觉得真的是这样的吗?其实在内存阅读程序过程中,受到队列和栈的算法影响,阅读顺序有所差别。队列是从尾部插入数据,从头部输出数据会更加好理解。
二、深入js数组栈和堆理解
首先,js中的队列我们不能用一种惯性思维去理解,当然队列算法的原理完全没有问题的,所以也不存在算法逻辑上的错误。实际上,在js中的栈中存入值是从头部插入数据的,最先进入栈里的值会顶到最后面出来的拿一个位置。
如图所示:
所以a最先进入被顶入最左边,最左边封顶,a是最后一个值,此时如果输出值就会拿出cba值。
和栈的区别就是队列中,a的最左边不封顶,被数值顶入队列中,也就是在a左边还有可能还有更多的数值,a不是最后一个值。因为现在内存阅读从右边开始拿数据,那么输出也是和栈一致是cba。
自我感想:
队列和栈在js中都有不同的表现,这些表现也许我们还是相当疑惑的。我们都知道队列和栈的算法原理,但是实际上我们在操作过程中会存在很多疑问,解决这些疑问,就是我们提高我们的硬实力的绝佳路径。
谢谢大家~❤
-
Java_如何实现栈和队列间的相互转化(关于一维数组的输入与输出)?
2019-10-10 19:30:02栈的规则是先进后出(输出5,4,3,2,1,),而队列的规则是先进先出(输出还是1,2,3,4,5)。 那么我们如何实现栈和队列的相互转化呢? 1.两个栈表示一个队列 两个栈想要表示一个队列对于一维数组的操作方式,... -
简单的算法:环形数组实现队列详细分析,
2021-01-13 15:19:20不就是一个先进先出,后进后出吗?这不有手就行?然后一写代码…(懵)啊,这是人学的玩意!!!,偶受不了了!哼╭(╯^╰)╮不管了,劳资今天不写了,想影响我的心态,不存在的。如果明天还拿不下你,我就去搞前端…... -
六十二、数据结构栈和队列的相互实现
2020-07-05 09:35:04栈和队列都是用来保存数据的,无论底层是使用数组还是链表来实现,其基本原理是不变的,那就是栈的特点的先进后出,队列的特点是先进先出。 -
Queue_使用栈来实现队列功能
2019-11-23 22:00:12之前同事给我讲的那个逆序输出数组的问题时,我还想过使用栈的先进后出特性来实现,但是稍微再想想还是不要了,根据数组本身就可以实现,使用栈就显得很多余了。栈先进后出的特性,要是稍加利用,也是可以实现先进先... -
python线性表和队列_浅析数据结构栈和队列的相互实现
2021-01-14 02:03:19栈和队列都是用来保存数据的,无论底层是使用数组还是链表来实现,其基本原理是不变的,那就是栈的特点的先进后出,队列的特点是先进先出。栈栈 (Stack)是一种后进先出(last in first off,LIFO)的数据结构。线性表... -
栈
2018-10-11 23:10:00一种先进后出,后进先出的数据结构,只允许在一端插入和删除数据。 数组或链表与栈对比 数组或链表操作灵活自由,但是暴露了太多的操作接口,使用时比较不可控,容易出错。 栈使用受限较多,但是比较可控,不容易... -
8583 顺序栈的基本操作_六十二、数据结构栈和队列的相互实现
2020-12-23 17:48:44栈和队列都是用来保存数据的,无论底层是使用数组还是链表来实现,其基本原理是不变的,那就是栈的特点的先进后出,队列的特点是先进先出。栈栈 (Stack)是一种后进先出(last in first off,LIF... -
栈:如何实现浏览器的前进和退后功能
2019-12-06 11:30:19当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,首选栈,毕竟数组或者链表暴露太多的操作接口,在使用的时候不可控 实现一个栈 用数组实现的栈,叫顺序栈,用链表实现的栈,链式栈 ... -
数据结构与算法:08 |栈
2020-07-01 00:09:53当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,就应该首选“栈”这种数据结构。 如何实现一个“栈”? 栈可以用数组或链表来实现: 用数组实现的栈,叫顺序栈, 用链表实现的栈,... -
使用两个队列实现栈
2018-05-06 15:03:47使用两个 队列实现栈参考文章栈的队列的特点栈和队列都是用来保存数据的,无论底层是使用数组还是链表来实现,其基本原理是不变的,那就是栈的特点的先进后出,队列的特点是先进先出。队列的常用方法 isEmpty() 判断... -
图解数据结构(3)——队
2015-03-19 15:32:36前一篇讲了栈(Stack),队和栈其实只有一个差别,栈是先进后出,队是先进先出,如图: 从图中可以看出,队有两个常用的方法,Enqueue和Dequeue,顾名思义,就是进队和出队了。队和栈一样,既可以用数组实现,也... -
使用两个栈实现队列
2018-05-06 15:03:02使用两个栈实现队列参考文章栈的队列的特点栈和队列都是用来保存数据的,无论底层是使用数组还是链表来实现,其基本原理是不变的,那就是栈的特点的先进后出,队列的特点是先进先出。栈的常用方法 isEmpty() 判断栈... -
数据结构(2)——队
2013-09-02 14:02:11前一篇讲了栈(Stack),队和栈其实只有一个差别,栈是先进后出,队是先进先出,如图: 从图中可以看出,队有两个常用的方法,Enqueue和Dequeue,顾名思义,就是进队和出队了。队和栈一样,既可以用数组实现,也... -
C语言停车场模拟管理程序的设计与实现
2013-07-12 21:22:12关于栈,就是先进后出的思想,队列就是先进先出的思想,有思想什么都好写。这个程序自己没用链栈和链队列做,因为感觉比较耗时。不过栈和队列的运用大多数都是用数组,先掌握好数组的表示再用链表写上手 -
栈与队列
2013-10-26 17:04:23栈即所谓一种先进后出的机制,而队列即所谓一种先进先出的机制。 1.1数组 栈对于顺序存储还是很方便的,因为不需要移动元素,但是必须实现确定数组空间的大小,故用链表更适合处理。 对于数组栈的一个节约资源... -
c++实现一个简单的循环队列
2019-09-02 22:29:48队列的特点就是先进先出,尾插头出。 涉及到循环,,,无论是数组还是链表,重点在于取余!!!,防止溢出。。。 例如数组大小为5,当队尾为4时,( 且 队头!= 队尾 ),再入队后,队尾应改变为0,需用取余。 #... -
c++学习笔记 --5.11 小结
2017-05-11 23:11:09队列类(先进先出)->循环队列 (运用取余的做法 让头到尾 尾到头) 类是对对象的抽象 而类模板是对类的抽象 但是人们还是不满足 当两个类模板 比如 集合类模板 与 链表类模板 都有相似的算法 add remove 那么... -
java 栈数据结构_java数据结构——栈
2021-02-28 15:51:49/*** 继续学习Java数据结构 ————栈* 栈的实现其实还是使用数组,只不过我们不能直接访问数组下标,而是通过一个指针来对其进行操作* 栈的重要数据特性————先进后出(后进先出)* 压入、弹出、访问、是否空、... -
LeetCode刷题之路,记录刷题成长------随时维护
2020-03-03 15:16:05前言 ...栈,队列,堆的数据结构就不多介绍了,只需要知道栈是先进后出,队列是先进先出。在这里就主要介绍一下堆,其实就是一颗二叉树,还是直接上算法及实现方法吧。 1.寻找一个数组中第K大的... -
栈的简单实现
2020-09-05 10:28:42首先我们要清楚栈是一个什么东西,他是一种先进后出的一种数据结构,不像链表的结构,是环环相扣的,一个接着一个,栈其实就是一个数组,一个由你来定义数据类型的可以实现一些其他操作的数组; 那么我们要怎么去... -
软协 第三次 博客
2020-12-20 22:10:21队列最重要的原则: FIFO(first in first out)先进先出原则 前面出-后面入 队列如果仅仅是 单项线性的空间,肯定会造成 内存的浪费(假溢出) 所以采用循环队列 可以充分利用空间 关于实现方式: 数组实现 还是略...