建网站卖产品,网站建设多少钱 知乎,公司里面有人员增减要去哪个网站做登记,设计师做网站的流程文章目录 题目一、什么是队列和栈#xff1f;1.1队列1.2栈 二、具体实现2.1 思路分析2.2代码实现 题目
用两个栈实现一个队列#xff0c;实现在队列尾部插入节点和在队列头部删除节点的功能。 一、什么是队列和栈#xff1f;
1.1队列
队列是一种特殊的线性表#xff0c;… 文章目录 题目一、什么是队列和栈1.1队列1.2栈 二、具体实现2.1 思路分析2.2代码实现 题目
用两个栈实现一个队列实现在队列尾部插入节点和在队列头部删除节点的功能。 一、什么是队列和栈
1.1队列
队列是一种特殊的线性表它只允许在表的前端队头进行删除操作在表的后端队尾进行插入。 故队列又称为先进先出FIFO—first in first out线性表。
1.2栈
栈作为一种数据结构是一种只能在一端进行插入和删除操作的特殊线性表。 它按照后进先出LIFO—last in first out的原则存储数据先进入的数据被压入push栈底最后的数据在栈顶需要读数据的时候从栈顶开始弹出pop数据最后一个数据被第一个读出来。 栈在计算机领域被广泛应用比如操作系统会给每个线程创建一个栈用来存储函数调用时各个函数的参数、返回地址及临时变量等。
二、具体实现
2.1 思路分析 a在stack1中依次插入a、b、cstack2为空 b现在从队列中删除一个元素按照队列先入先出的规则最先删除的应该是a。 但是a在栈底不能直接删除这时候可以借助stack2将元素逐个弹出pop并压入pushstack2则元素在stack2中的顺序{从c、b、a}正好和stack1中相反此时就可以弹出stack2的栈顶a如图b。 c如果想继续删除队列头部按照最开始的顺序b比c早进入队列此时应该删除b。b正好在stack2的栈顶只需要弹出stack2的栈顶即可。如图c。
这样就可以总结出一个删除的步骤 1、当stack2不为空时stack2就是栈顶就是最先进入队列的元素可以弹出。 2、当stack2为空时将stack1中的元素逐个弹入stack2中由于先进入队列的元素被压到stack1栈底经过弹出和压入操作后位处stack2栈顶就可以直接弹出。
d接下来插入一个元素d把它压入stack1。 e现在考虑删除一个元素此时stack2不为空直接弹出c而c确实比d先进入队列因此也是正确的。
2.2代码实现
代码如下
import java.util.*;
import java.util.Stack;
public class CQueue{StackInteger stack1 new StackInteger();StackInteger stack2 new StackInteger();public void push(int node){stack1.push(node);}public int pop(){if(stack2.isEmpty()){//将第一个栈中内容弹出放入第二个栈中while(!stack1.isEmpty()){stack2.push(stack1.pop());}}if(stack2.isEmpty()){Throw new Exception(queue is empty!);}int head stack2.pop();return head;}}
