用栈实现队列和用队列实现栈

简介: 用栈实现队列和用队列实现栈

这两个问题对我来说有点绕,不过还好,终于搞明白了,我把他们写在这里,防止自己再次犯错

1.用栈实现队列

一个栈显然是无法实现队列的,所以需要两个栈

数据是12,23,34,45,56.

首先把这几个数据按照顺序依次入栈1.

然后把它们按顺序出栈1,进入栈2

1c65a021f20f4a1f88be9bff119c5670.png这个时候栈2的栈顶元素就是我们需要的

我在写这个代码的时候陷入了一种思维怪圈,总想着要求size(),判断栈满啥的,但是这是不对的,栈如果满了会自动扩容,所以不要这样想

现在上代码


class MyQueue {
    public Stack<Integer>  stack1;
    public Stack<Integer>  stack2;
    public MyQueue() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }
    public void push(int x) {
        //默认压入到栈1中
        stack1.push(x);
    }
    public int pop() {
        if(empty()){
            return -1;
        }
            if(stack2.empty()){
                while(!stack1.empty()){
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
    }
    public int peek() {
        if(empty()){
            return -1;
        }
       if(stack2.empty()){
                while(!stack1.empty()){
                    stack2.push(stack1.pop());
                }
            }
            return stack2.peek();
    }
    public boolean empty() {
        return stack1.isEmpty()&&stack2.isEmpty();
    }
}


现在让我们进行下一个题,用队列实现栈

先判断哪个队列为空,哪个为空才能放到队列里面

这是在pop的情况

这是在top的情况

定义一个size()

上代码


class MyStack {
    Queue<Integer>  queue1;
    Queue<Integer>  queue2;
    public MyStack() {
        queue1=new LinkedList<>();
        queue2=new LinkedList<>();
    }
    public void push(int x) {
        if(!queue1.isEmpty()){
            queue1.offer(x);
        }else if(!queue2.isEmpty()){
            queue2.offer(x);
        }else{
            queue1.offer(x);
        }
    }
    public int pop() {
        if(empty()){
            return -1;
        }
        if(!queue1.isEmpty()){
     int size=queue1.size();
    while(size-1!=0){
     int val= queue1.poll();
  size--;
  queue2.offer(val);
 }
   return   queue1.poll();
}else{
 int  size=queue2.size();
  while(size-1!=0){
    int val= queue2.poll();
  size--;
       queue1.offer(val);
}
     return     queue2.poll();
}
    }
    public int top() {
        if(empty()){
            return -1;
        }
         if(!queue1.isEmpty()){
     int size=queue1.size();
     int val=-1;
         while(size!=0){
     val= queue1.poll();
  size--;
  queue2.offer(val);
 }
   return   val;
}else{
 int  size=queue2.size();
 int val=-1;
  while(size!=0){
     val= queue2.poll();
  size--;
       queue1.offer(val);
}
     return     val;
    }
    }
    public boolean empty() {
        return queue1.isEmpty()&&queue2.isEmpty();
    }
}


这就是今天的博客,我们下期再见,886!!!

相关文章
|
14天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
5天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
14 1
|
8天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
11天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
13天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
40 4
|
17天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
30天前
数据结构(栈与列队)
数据结构(栈与列队)
17 1
|
1月前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
67 1
|
1月前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
16 0
|
1月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
30 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器

热门文章

最新文章