栈和队列的实现,java实现栈和队列数据结构
这篇文章给你带来了一些关于java的知识，包括栈和队列的定义、应用、实现和操作。下面就来看看吧，希望对你有帮助。
如何解决写爬虫IP受阻的问题？立即使用。
在学习栈和队列之前，先了解什么是线性表：一次保存同类型的单个元素，多个元素在逻辑上是连续的，比如数组、链表、字符串、栈和队列。
栈和队列实际上是线性表、数组或链表，操作有限。它们可以在头部或尾部插入和删除，但是栈和队列只能在一端插入和删除。
一、栈
1.定义
您只能在一端(堆栈的顶部)插入或删除元素。你可以把栈想象成一个“水杯”。您只能从一端添加元素或从段落中删除元素。而且先入杯的水在杯底，后入杯的水在杯顶。倒出来的时候，也是杯子顶部倒出来的水。所以先入栈的元素后出，后入栈的元素先出。这也是栈的特点：“先进后出，后进先出”(LIFO)。取出元素和添加元素只能在栈顶。
将1 2 3 4 5放入堆栈中一次。
2.栈的应用
1.无处不在的undo(撤销)操作
在任一编辑器中键入错误内容后，使用Ctrl z返回到输入的内容；
在任一浏览器中单击后退。
就是堆栈的这种结构的应用。
1.使用编辑器来使用撤消操作。一旦你输入了，你将把内容推入堆栈，然后你将再次把它推入堆栈。如果发现一次输入错误，就用撤销操作在当前栈顶弹出错误的内容。那么当前栈顶的内容就是最后输入的内容。
2.浏览网页其实是一样的原理，就像打开百度-打开csdn-打开创意中心一样。也使用这种结构。首先将百度网页推入栈中，然后将csdn网页推入栈中，再将创意中心网页推入栈中。如果想返回csdn主页，按返回箭头弹出当前栈顶的创意中心网页，取出csdn主页。
2.操作系统栈
在程序重新执行的过程中，从A函数调用B函数，从B函数调用C函数。当调用结束，执行返回，怎么知道从哪里继续执行？背后还有堆栈结构。
3.栈的实现
基于链表的堆栈链堆栈
基于阵列实施的堆栈—顺序堆栈(更常用)
基于动态数组实现定义堆栈。
//基于动态数组实现的顺序堆栈公共类mystack
//记录当前堆栈中的元素数量
私有int大小；
//实际存储数据的动态数组。此时，只能在堆栈中的数组末尾添加和删除元素。
private ListE data=new ArrayList()；
}
4.栈的操作
1.向堆栈中添加一个元素
只能添加到堆栈的顶部。
/**
*将元素添加到当前栈-栈压操作
* @param val
*/
公共无效推送(E值){
data . add(val)；
尺寸；
}2.当前一个元素从栈顶弹出
/**
*弹出当前顶层元素并返回顶层元素的值。
* @返回
*/
public E pop(){
if (isEmpty()){
//堆栈为空，无法弹出。
抛出new NoSuchElementException(堆栈为空！“不能爆！”);
}
//删除数组末尾的元素
e val=data . get(size-1)；
data.remove(大小为1)；
尺寸-；
返回val
}3.查看堆栈的当前顶部元素，但它不会弹出
/**
*检查当前栈顶元素值，元素不会弹出。
* @返回
*/
公共E peek(){
if (isEmpty()){
抛出new NoSuchElementException(堆栈为空！“不能偷看！”);
}
返回data.get(大小-1)；
}
二、队列
1.定义
队列：先进先出(FIFO)数据结构一、元素只能从队列尾加入队列，只能从队列头出队列。元素的出队顺序和队列顺序是一致的。
依次排队1 2 3 4 5。
2.队列的应用
现实生活中，各种“排队”操作
3.队列的实现
基于阵列实施的队列顺序队列
基于链表-链队列的队列
出列操作只能在队列的头部执行。如果采用由array实现的队列，则每次一个元素出队，所有剩余的元素都必须向前移动一个单位。这时链表实现的队列更适合队列的结构。要删除元素，只需删除头节点，并在链表的末尾添加元素。
公共接口队列{
//排队操作
无效报价；
//出列操作
e poll()；
//检查队列头元素
e peek()；
布尔型isEmpty()；}对于栈来说，队列有很多实现子类，比如
先进先出队列
双端队列
循环排队
优先队列
无论实现哪个队列。
:
4.FIFO队列
1.定义一个FIFO队列
//突出显示的blockvar foo= bar2.向队列中添加元素
公开无效要约(E val) {
NodeE node=新节点(val)；
if (head==null){
头=尾=节点；
}否则{
//链表的尾部插入
tail.next=node
尾=节点；
}
尺寸；
}3.来自当前团队领导的一个元素
公共电子投票(){
if (isEmpty()){
引发新的NoSuchElementException(队列为空！无法投票！);
}
//标头删除
E val=head.val
NodeE节点=头；
head=head.next
node.next=node=null
尺寸-；
返回val
}4.检查当前队列的头元素。
公共E peek() {
if (isEmpty()){
引发new NoSuchElementException(队列为空！“不能偷看！”);
}
返回head.val
}
5.循环队列
1.定义：基本上是用定长数组来实现数组。实现数组时，如果从数组头删除元素，需要频繁移动后面的元素，效率很低；对于出队和入队操作，使用两个引用，一个头和一个尾。添加元素是在数组的末尾添加的。删除元素只需要移动head引用所指向的地址(逻辑删除)。
2.应用：操作系统的生产消费者模型，MySQL数据库的InnoDB存储引擎的重做日志。
3.循环队列是用定长数组实现的，数组头是队列头，数组尾是队列尾。数组[head…tail]是循环队列的有效元素。
Head总是指向循环队列的第一个元素。
Tai总是指向循环队列中有效元素的最后一个位置。
此时，循环队列的有效元素是7 ^ 9 ^ 1。
当队列循环地将一个元素出队时，它只需要将头引用向后移动一个位置。
此时，循环队列中唯一有效的元素是9和1。
另一个元素在排队，但是head引用此时已经到了末尾。所谓循环队列，就是当头或尾引用到达数组末尾时，回移就是返回数组头部的操作。循环队列最大的优点是删除元素时不需要移动数据。当新元素被添加到队列中时，原始元素将被覆盖，因此只需要用新元素覆盖尾部索引位置，然后让tail移回。
流通中应注意的要点。
1.因此，当头尾相等时，无法判断此时循环队列是满的还是空的，所以在循环队列中，如果(tail 1)% n==head，则认为循环队列已满。
此时循环队列已满，循环队列中会浪费一个空间来判断队列是否已满。
2.2 .头尾的运动不可能是简单的1。使用模运算，取数组的长度。
tail=(tail 1) % n
head=(head 1) % n
模数组长度的本质：
当head和tai到达数组的最后一个索引位置时，下一次它们返回数组的头部时，它们必须将数组长度取1对的模。
3.当3.head==tail时，队列被认为是空的。
:
6.循环队列的操作
1.定义一个循环队列
//循环队列公共类循环队列实现基于整形的队列整数{
//固定长度数组
私有整数[]数据；
//指向队列元素的头部
int head
//指向队列末尾元素的下一个元素
int tail
公共循环队列（整数大小){
数据=新整数[大小1];
}}2.向循环队列中添加一个元素
@覆盖公共无效报价（整数值){
if (isFull()){
抛出新的ArrayIndexOutOfBoundsException(循环队列已满！不能提供);
}
data[tail]=val；
tail=(tail 1)%数据。长度；
}3.从循环队列中出队一个元素
@覆盖公共整数轮询(){
if (isEmpty()){
引发新的NoSuchElementException(循环队列为空！无法投票!);
}
整数val=data[head]；
head=(head 1)%数据。长度；
返回英国压力单位
}4.查看当前循环队列队首元素
@Override public Integer peek() {
if (isEmpty()){
引发新的NoSuchElementException(循环队列为空！"不能偷看!");
}
返回数据[头]；
}5.判断当前循环队列是否为空
@ Override public boolean isEmpty(){
返回头==尾
}6.判断当前循环队列是否已满
public boolean isFull(){
返回(尾1)%数据。长度==头；
7.toString方法
公共字符串toString(){
StringBuilder sb=new StringBuilder()；
某人（somebody的简写）append( front[)；
//最后一个有效元素的索引
int lsatIndex=tail==0？数据。长度-1:尾部-1；
for(int I=head；我！=尾巴；) {
某人（somebody的简写）append(data[I])；
如果（我！=lsatIndex){
某人（somebody的简写）追加(,);
}
I=(I ^ 1)%数据。长度；
}
某人（somebody的简写）append(]tail )；
归还某人。tostring()；
}
7.双端队列
双端队列：德克是长队的子接口，这个队列既可以尾插，头出；也可以头插，尾出
双端队列的一个常用子类就是链接列表，不管使用栈还是队列，都可以统一使用双端队列接口
1.现在需要一个栈
2.现在需要一个队列
推荐学习： 《java视频教程》 以上就是一文带你认识爪哇栈和队列的详细内容，更多请关注我们其它相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。