精华内容
下载资源
问答
  • 栈:先进后出 队列:先进先出两个栈实现一个队列:思路:先将数据存到第一个栈里,再将第一个栈里的元素全部出栈到第二个栈,第二个栈出栈,即可达到先进先出源码:class Queue{ //用的jdk自带的栈private Stack s1=...

    栈:先进后出  队列:先进先出

    两个栈实现一个队列:

    思路:先将数据存到第一个栈里,再将第一个栈里的元素全部出栈到第二个栈,第二个栈出栈,即可达到先进先出

    源码:

    class Queue{ //用的jdk自带的栈

    private Stack s1=new Stack<>();

    private Stack s2=new Stack<>();

    public void offer(E val){ //入队

    s1.push(val);

    }

    public E poll() { //出队

    while (s2.empty()){

    while (!s1.empty()){

    s2.push(s1.peek());

    s1.pop();

    }

    }

    E val=s2.peek();

    s2.pop();

    //获取出队元素后,再将s2里面的元素放入s1里面。

    while (!s2.empty()){

    s1.push(s2.pop());

    }

    return val;

    }

    public E peek(){//查看对头元素

    while (s2.empty()){

    while (!s1.empty()){

    s2.push(s1.peek());

    s1.pop();

    }

    }

    E val=s2.peek();

    //获取出队元素后,再将s2里面的元素放入s1里面。

    while (!s2.empty()){

    s1.push(s2.pop());

    }

    return val;

    }

    public boolean empty(){ //判断队是否为空

    return s1.empty();

    }

    }

    测试:

    public static void main(String[] args) {

    Queue queue = new Queue<>();

    Random rand = new Random();

    for (int i = 0; i < 5; i++) {

    int data = rand.nextInt(100);

    System.out.print(data + " ");

    queue.offer(data);

    }

    System.out.println();

    System.out.println("出队:");

    while (!queue.empty()) {

    System.out.print(queue.poll()+" ");

    }

    }

    运行结果:

    79 67 45 73 59

    出队:

    79 67 45 73 59

    两个队列实现一个栈:

    思路:先将数据存到第一个队列里面,然后数据出队一直出队到地二个队列里面,直到第一个队列里面剩余一个数据,这个时候出队 即可达到先进后出的特性

    源码:

    自定义的一个循环队列:

    class Queue{//存储队列元素的数组

    privateE[] que;//表示队头的位置

    private intfront;//表示队尾的位置

    private intrear;publicE[] getQue() {returnque;

    }public intgetFront() {returnfront;

    }public intgetRear() {returnrear;

    }/*** 默认构造队列,初始大小是10*/

    publicQueue(){this(10);

    }/*** 用户可以指定队列的大小size

    *@paramsize*/

    public Queue(intsize){this.que = (E[])newObject[size];this.front = this.rear = 0;

    }/*** 入队操作

    *@paramval*/

    public voidoffer(E val){if(full()){//扩容

    E[] newQue = Arrays.copyOf(this.que,this.que.length*2);int index = 0;for(int i=this.front;

    i!= this.rear;

    i=(i+1)%this.que.length){

    newQue[index++] = this.que[i];

    }this.front = 0;this.rear =index;this.que =newQue;

    }this.que[this.rear] =val;this.rear = (this.rear+1)%this.que.length;

    }/*** 出队操作,并把出队的元素的值返回*/

    publicE poll(){if(empty()){return null;

    }

    E front= this.que[this.front];this.front = (this.front+1)%this.que.length;returnfront;

    }/*** 查看队头元素

    *@return

    */

    publicE peek(){if(empty()){return null;

    }return this.que[this.front];

    }/*** 判断队满

    *@return

    */

    public booleanfull(){return (this.rear+1)%this.que.length == this.front;

    }/*** 判断队空

    *@return

    */

    public booleanempty(){return this.rear == this.front;

    }

    }

    两个队列实现一个栈:

    class SeqStack{private Queue que1; //存放栈的元素

    private Queue que2; //做一个辅助操作

    publicSeqStack(){this.que1 = new Queue<>();this.que2 = new Queue<>();

    }public SeqStack(intsize){this.que1 = new Queue<>(size);this.que2 = new Queue<>(size);

    }public voidpush(E val){this.que1.offer(val);

    }publicE pop(){//从que1出队,把最后一个出队的元素返回

    E data = null;/*** 把que1里面的所有元素出队,放入que2里面,

    * 然后把que1最后一个出队的元素直接返回,不用放入que2*/

    while(!this.que1.empty()){

    data= this.que1.poll();if(this.que1.empty()){break;

    }this.que2.offer(data);

    }//获取该出栈的元素以后,再把que2的元素再放入que1里面

    while(!this.que2.empty()){this.que1.offer(this.que2.poll());

    }returndata;

    }publicE top(){//从que1出队,把最后一个出队的元素返回

    E data = null;while(!this.que1.empty()){

    data= this.que1.poll();this.que2.offer(data);

    }//获取该出栈的元素以后,再把que2的元素再放入que1里面

    while(!this.que2.empty()){this.que1.offer(this.que2.poll());

    }returndata;

    }public booleanfull(){return this.que1.full();

    }public booleanempty(){return this.que1.empty();

    }

    }

    测试:

    public static voidmain(String[] args) {

    SeqStack seqStack=new SeqStack<>();

    Random rand= newRandom();for (int i = 0; i < 5; i++) {int data = rand.nextInt(100);

    System.out.print(data+ " ");

    seqStack.push(data);

    }

    System.out.println();

    System.out.println("出栈:");while (!seqStack.empty()) {

    System.out.print(seqStack.pop()+" ");

    }

    }

    运行结果:

    9 3 7 83 32出栈:32 83 7 3 9

    展开全文
  • 面试中常出现让你手写两个队列实现一个栈,两个栈实现一个队列的问题,很是头疼!今天就仔细将我分析,思考过的Java代码给大家分享一下:(一)两个队列实现一个栈:两个队列添加元素,哪个队列为空,由于在输出元素时...

    面试中常出现让你手写两个队列实现一个栈,两个栈实现一个队列的问题,很是头疼!今天就仔细将我分析,思考过的Java代码给大家分享一下:(一)两个队列实现一个栈:

    2df096e940f0481d4921077e9f021a7d.png

    两个队列添加元素,哪个队列为空,由于在输出元素时,要进行相应元素的移动(除去尾部元素),所以要在对应不为空的队列进行元素的添加;在输出数据时,要进行两个队列的变相操作,不为空的队列要依次向为空的队列中添加元素,直到尾元素输出即可!

    /**

    * 两个队列实现一个栈

    * @auther yangchao

    * @date 2019/7/18

    */

    public class TwoQueueImplStack {

    private Queue queue1 = new ArrayDeque<>();

    private Queue queue2 = new ArrayDeque<>();

    /**

    * 向栈中压入数据

    * @param element

    */

    public void push(Integer element) {

    //两个队列为空时,优先考虑queue1

    if (queue1.isEmpty() && queue2.isEmpty()) {

    queue1.add(element);

    return;

    }

    //如果queue1为空,queue2有数据,直接放入queue2

    if (queue1.isEmpty()) {

    queue2.add(element);

    return;

    }

    //如果queue1为空,queue2有数据,直接放入queue2

    if (queue2.isEmpty()) {

    queue1.add(element);

    return;

    }

    }

    /**

    * 取出栈中的数据

    * @return

    */

    public Integer poll() {

    //两个队列为空时,直接抛出异常

    if (queue1.isEmpty() && queue2.isEmpty()) {

    throw new RuntimeException("stack is empty");

    }

    //如果queue1为空,将queue2中的元素依次加入到 queue1, 弹出最后一个元素

    if (queue1.isEmpty()) {

    while(queue2.size() > 1) {

    queue1.add(queue2.poll());

    }

    return queue2.poll();

    }

    //如果queue2为空,将queue1中的元素依次加入到 queue2, 弹出最后一个元素

    if (queue2.isEmpty()) {

    while(queue1.size() > 1) {

    queue2.add(queue1.poll());

    }

    return queue1.poll();

    }

    return null;

    }

    public static void main(String[] args) {

    TwoQueueImplStack qs = new TwoQueueImplStack();

    qs.push(2);

    qs.push(4);

    qs.push(7);

    qs.push(5);

    System.out.println(qs.poll());

    System.out.println(qs.poll());

    qs.push(1);

    System.out.println(qs.poll());

    }

    }

    输出结果:

    7a85917be704d4761ac746d3b90e9053.png

    (二)两个栈实现一个队列:

    cb8f398f49bf6d92eade57aae8a6e999.png

    第一个栈只负责添加元素,第二个栈在弹出元素时,首先判断当前栈是否为空,若为空就直接将其第一个栈中的数据全部压入第二个栈中,然后输出栈顶元素,即可实现队列效果;若第二个栈中有数据,添加直接将其数据压入第一个栈中,输出时直接输出第二个栈顶的元素即可!

    /**

    * 两个栈实现一个队列

    * @auther yangchao

    * @date 2019/7/18

    */

    public class TwoStackImplQueue {

    private Stack stack1 = new Stack<>();

    private Stack stack2 = new Stack<>();

    /**

    * stack1只负责压入队列元素

    * @param element

    */

    public void push(Integer element) {

    stack1.add(element);

    }

    /**

    * 取出队列顶部元素

    * @return

    */

    public Integer poll() {

    //若stack2为空,将 stack1 中的元素压入 stack2

    if (stack2.isEmpty()) {

    while (stack1.size() > 0) {

    stack2.add(stack1.pop());

    }

    }

    if (stack2.isEmpty()) {

    throw new RuntimeException("queue is Empty!");

    }

    Integer head = stack2.pop();

    return head;

    }

    public static void main(String[] args) {

    TwoStackImplQueue sq = new TwoStackImplQueue();

    sq.push(1);

    sq.push(3);

    sq.push(5);

    sq.push(4);

    sq.push(2);

    System.out.println(sq.poll());

    System.out.println(sq.poll());

    sq.push(7);

    System.out.println(sq.poll());

    }

    }

    输出结果:

    1d4c87c208495d1f2145dc0096463d00.png

    每天进步一点点,继续加油......

    展开全文
  • 面试题7:用两个栈实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。解题思路由于栈是后进先出的,为了实现队列的先进先出特性,那么两个栈中,stack1 用来实现 push。当该仿真队列不断执行 push ...

    面试题7:用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

    解题思路

    由于栈是后进先出的,为了实现队列的先进先出特性,那么两个栈中,stack1 用来实现 push。当该仿真队列

    不断执行 push 操作时,元素一个个被压到栈中,此时的顺序是最先的元素在栈的最底部,顺序和队列元素相反。

    当要弹出元素时,我们期望将 stack1 的数据逆序输出去,即从栈底开始依次弹出,此时就得借助 stack2 了。

    执行仿真队列的 pop 操作时,将 stack1 的元素全部 pop 出来并压入 stack2,此时 stack2 就变成栈底

    是最后 push 进队列(最后 push 到 stack1)、栈顶是最先 push 到队列(最先 push 到 stack1)的元素

    顺序,对 stack2 直接 pop 就是期望的队列元素。

    间接实现了队列的先进先出特性。

    复制代码

    代码实现

    import java.util.Stack;

    public class Solution {

    Stack stack1 = new Stack();

    Stack stack2 = new Stack();

    public void push(int node) {

    stack1.push(node);

    }

    public int pop() {

    if(stack1.isEmpty() && stack2.isEmpty()) {

    throw new RuntimeException("Queue is empty!");

    }

    if(!stack2.isEmpty()) {

    return stack2.pop();

    }

    while(!stack1.isEmpty()) {

    stack2.push(stack1.pop());

    }

    return stack2.pop();

    }

    }

    复制代码

    总结

    栈和队列这两种数据结构可以互相用来实现对方,但必须多出同类型的一个辅助数据结构才行。

    扩展:两个队列实现栈

    思路

    每次 push 进 Queue1, 都是先进先出的序列,而 pop 时要求实现后进先出,由于队列只能最先进的从队列头最先

    弹出,此时,可以将 Queue1 的元素,全部 pop 出来,通过一个变量 element 来暂存 Queue1 中的最后一个元

    素,在这个过程中,将弹出的元素 push 到 Queue2(除 Queue1 最后一个元素),返回的 element 就是最后 push

    到队列的值,相当于栈顶元素,间接实现栈的后进先出特性。

    如果此时要继续 pop 出仿真栈的下一个元素,则模仿上一步,将 Queue2 所有元素,除了最后一个元素都 pop 出来,

    并 push 进 Queue1, 这个过程中同样通过 element 这个变量来保存 Queue2 的最后一个元素,返回该元素即栈

    顶元素。

    注意:每次 pop 都最终保证一个 Queue 为空。

    如此交替装元素,一个作为发射枪发射子弹,另一个作为容器装这个发射枪的发出的子弹。

    复制代码

    代码实现

    import java.util.Queue;

    public class Solution {

    Queue queue1 = new Queue();

    Queue queue2 = new Queue();

    public void push(int node) {

    if(queue1.size() != 0) {

    queue1.add(node);

    } else if(queue2.size() != 0) {

    queue2.add(node);

    } else {

    queue1.add(node);

    }

    }

    public int pop()() {

    if(queue1..size() == 0 && queue2..size() == 0) {

    return new RuntimeException("Stack is empty!");

    }

    int element;

    if(queue1.size() != 0) {

    while(queue1.size() > 0){

    element = queue1.poll();

    if(queue1.size() != 0) {

    queue2.add(element);

    }

    }

    } else {

    while(queue2.size() > 0) {

    element = queue2.poll();

    if(queue2.size() != 0) {

    queue1.add(element);

    }

    }

    }

    return element;

    }

    }

    复制代码

    展开全文
  • 1、两个栈实现一个队列import java.util.Stack;public class TwoStackToQueue {Stacks1 = new Stack();Stacks2 = new Stack();public void push(int node){s1.push(node);}public int pop(){if(s2.isEmpty()){while...

    1、两个栈实现一个队列

    import java.util.Stack;

    public class TwoStackToQueue {

    Stacks1 = new Stack();

    Stacks2 = new Stack();

    public void push(int node){

    s1.push(node);

    }

    public int pop(){

    if(s2.isEmpty()){

    while(!s1.isEmpty()){

    s2.push(s1.pop());

    }

    }

    return s2.pop();

    }

    public static void main(String[] args) {

    TwoStackToQueue tsq = new TwoStackToQueue();

    tsq.push(1);

    tsq.push(2);

    tsq.push(3);

    System.out.println(tsq.pop());

    System.out.println(tsq.pop());

    tsq.push(4);

    tsq.push(5);

    System.out.println(tsq.pop());

    System.out.println(tsq.pop());

    }

    }

    2、两个队列实现一个栈

    import java.util.LinkedList;

    import java.util.Queue;

    public class TwoQueueToStack {

    Queue q1 = new LinkedList();

    Queue q2 = new LinkedList();

    public void push(int node){//添加元素,如果q1不为空,向q1添加;如果q2不为空,向q2添加;都为空时,向q1添加

    if(!q1.isEmpty()){

    q1.offer(node);

    }else if(!q2.isEmpty()){

    q2.offer(node);

    }else{

    q1.offer(node);

    }

    }

    public int pop(){

    if(q1.isEmpty()&&q2.isEmpty()){

    try{

    throw new RuntimeException("Stcak is Empty!!!");

    }catch(Exception e){

    }

    }

    //如果Q1为空,q2有元素,将q2中的元素依次出队添加到q1,保留最后一个元素,然后出栈。

    if(q1.isEmpty()){

    while(q2.size()>1){

    q1.offer(q2.poll());

    }

    return q2.poll();

    }

    //如果Q2为空,q1有元素,将q1中的元素依次出队添加到q2,保留最后一个元素,然后出栈。

    if(q2.isEmpty()){

    while(q1.size()>1){

    q2.offer(q1.poll());

    }

    return q1.poll();

    }

    return (Integer) null;

    }

    public static void main(String[] args) {

    TwoQueueToStack tqs = new TwoQueueToStack();

    tqs.push(1);

    System.out.println(tqs.pop());

    tqs.push(2);

    tqs.push(3);

    System.out.println(tqs.pop());

    System.out.println(tqs.pop());

    }

    }

    展开全文
  • 面试中常出现让你手写两个队列实现一个栈,两个栈实现一个队列的问题,很是头疼!今天就仔细将我分析,思考过的Java代码给大家分享一下: (一)两个队列实现一个栈: 两个队列添加元素,哪个队列为空,由于在输出...
  • 两个栈实现一个队列 栈的特性是先入后出,输出就是倒序输出,队列的特性是先入先出,输出是顺序输出。要用两个栈实现一个队列,先让数据入第一个栈,倒序,再出来入第二个栈,又倒序,通俗点说就是负负得正。 ...
  • 两个栈实现一个队列: 首先要清楚栈的特点是后进先出,然后队列的特点是先进先出,这样的话,用两个栈就可以实现队列的特性。 public class TwoStackToQueue { private Stack stack1; private Stack stack2; public ...
  • 两个栈实现一个队列: 思路:先将数据存到第一个栈里,再将第一个栈里的元素全部出栈到第二个栈,第二个栈出栈,即可达到先进先出 源码: class Queue<E>{ //用的jdk自带的栈 private Stack<E> s1=...
  • 两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 ) class CQueue { ...
  • import java.util.Stack;public class QueueByTwoStacks {private Stack stack1;private Stack stack2;public QueueByTwoStacks() {stack1 = new Stack();stack2 = new Stack();}public static void main(String[] a...
  • 两个栈实现一个队列import java.util.EmptyStackException; import java.util.Stack;class Solution { Stack<Integer> stack1 = new Stack(); Stack<Integer> stack2 = new Stack(); public void
  • 两个栈实现队列的pop和pushimport java.util.*;/*** 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。* 思路:入队列,直接用堆栈入就行* 出队列,当栈2位空的时候,把栈1所有的数据全部...
  • <用两个栈实现一个队列的功能> 入队:将元素进栈A 出队:判断栈B是否为空,如果为空,则将栈A中所有元素pop,并push进栈B,栈B出栈;如果不为空,栈B直接出栈。import java.util.*;/** * 用两个栈来实现一个队列...
  • 两个队列实现一个栈 现有两个队列 q1 和 q2,入栈则将元素加到 q1 出栈的时候先判读 q1 是否为空,除了队列的最后一个元素,将其它元素添加到 q2,q1 的最后一个元素出队 出栈的时候如果在 2 中判断 q1 为空,除了 ...
  • 1.两个栈实现一个队列 思路:压入元素直接入stack1,删除元素先判断stack2中是否为空,如果不为空直接弹出;为空则将stack1中的元素取出压入 stack2中再弹出。 代码: import java.util.Stack; public class ...
  • java 实现 两个栈实现一个队列的功能
  • 一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。队列队列种...
  • 两个栈实现一个队列 import java.util.Stack; public class Demo07 { Stack&lt;Integer&gt; stack1 = new Stack&lt;Integer&gt;(); Stack&lt;Integer&gt; stack2 = new Stack&lt...
  • Java:两个栈实现一个队列 import java.util.Stack; public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); /* ....
  • 两个栈实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 import java.util.Stack; public class Solution { Stack&lt;Integer&gt; stack1 = new Stack&lt;Integer&gt;(); ...
  • 两个栈实现一个队列思路:所有元素进stack1,然后所有出stack1并进入stack2.实现队列的先进先出即:若stack2非空,我们须要的恰好再栈顶,出栈;若要给队列加入元素,即先进sack1,要出队时,若stack2不为空就出栈,为...
  • 思路:先将数据存到第一个栈里,再将第一个栈里的元素全部出栈到第二个栈,第二个栈出栈,即可达到先进先出 package ds; import java.util.Queue; import java.util.Stack; import java.util.concurrent....
  • 日常生活中一端封闭的山洞就是一个典型例子。 特性:后进先出(LIFO:Last In First Out) 队列 队列也是一种线性表,一端插入元素(入队列),另一端删除元素(出队列),通常我们将可以插入元素的一端...
  • 题目:用两个栈实现一个队列。队列的生命如下,请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入结点和在队列头部删除结点的功能。 package 数据结构; import java.util.Stack; /** *题目:...
  • 题目:用两个栈实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。思路:用两个栈来模拟队列,一个栈作为存储,另一个栈作为交换空间。队列的push操作就直接push到第一个栈中,队列的pop操作,需要...
  • 问题一:两个栈实现一个队列。 思路:   用两个栈,分为添加元素栈、移除元素栈。 添加元素栈:一直向该栈添加元素 移除元素栈:   如果该栈为空,将添加元素栈的元素都移到移除元素栈,再将栈顶元素...
  • 首先了解队列是先进先出,入队...那要使用两个栈实现一个队列 举个简单的例子,我们有栈1 和栈2 两个栈,均为空,将数字 1 2 3 4先入栈1,当数字从栈1出栈时,4,先出来,然后压入栈2,数字3再出栈1,压入栈2,数字...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,712
精华内容 684
关键字:

两个栈实现一个队列java

java 订阅