Leecode 面试题09用两个栈实现队列

简介: Leecode 面试题09用两个栈实现队列

题目描述:

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

示例 1:

输入:

[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”]

[[],[3],[],[]]

输出:[null,null,3,-1]

示例 2:

输入:

[“CQueue”,“deleteHead”,“appendTail”,“appendTail”,“deleteHead”,“deleteHead”]

[[],[],[5],[2],[],[]]

输出:[null,-1,null,null,5,2]

解题思路:

在进行这两个操作的时候要注意先要清空其中一个栈,这样子才比较好

1、添加到尾部:由于栈就是先进后出的特点,所以可以直接压入栈就是相当于添加到尾部

2、删除头部元素:可以直接将其中一个栈的全部元素依次压入另外一个栈,这样子在被压入的那个栈的栈顶就是原先栈的头部元素,直接使用栈的pop()方法就可以了

class CQueue {
public:
    CQueue() {
        s1=new stack<int>;
        s2=new stack<int>;
    }
    void appendTail(int value) {
        s1->push(value);
    }
    int deleteHead() {
        if(s2->size()<=0){
            while(s1->size()>0){
                int top=s1->top();
                s1->pop();
                s2->push(top);
            }
        }
        if(s2->size()==0)   return -1;
        int head=s2->top();
        s2->pop();
        return head; 
    }
private:
    stack<int>* s1;
    stack<int>* s2;
};

执行结果如图

Java版的

class CQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    public CQueue() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }
    public void appendTail(int value) {
        //将stack2全部清空并依次压入stack1
        while(!stack2.isEmpty())
        {
            stack1.push(stack2.pop());
        }
        stack1.push(value);
    }
    public int deleteHead() {
        //将stack1清空,并将stack1的数据全部依次压入stack2
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
        if(stack2.isEmpty()){
            return -1;
        }
//此时stack2的栈顶元素就是stack1的栈底元素,所以可以直接使用stack2.pop()来进行达到删除头结点的目的
        return stack2.pop();
    }   
}
/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */


相关文章
|
3月前
|
存储 安全 Java
JVM常见面试题(二):JVM是什么、由哪些部分组成、运行流程,JDK、JRE、JVM关系;程序计数器,堆,虚拟机栈,堆栈的区别是什么,方法区,直接内存
JVM常见面试题(二):JVM是什么、由哪些部分组成、运行流程是什么,JDK、JRE、JVM的联系与区别;什么是程序计数器,堆,虚拟机栈,栈内存溢出,堆栈的区别是什么,方法区,直接内存
JVM常见面试题(二):JVM是什么、由哪些部分组成、运行流程,JDK、JRE、JVM关系;程序计数器,堆,虚拟机栈,堆栈的区别是什么,方法区,直接内存
|
3月前
|
存储 设计模式 Java
Unity精华☀️ 面试“堆、栈”误区!这样做可能反而会降低吸引力
Unity精华☀️ 面试“堆、栈”误区!这样做可能反而会降低吸引力
|
3月前
|
安全 Java
虚拟机栈的五道面试题
这篇文章提供了关于Java虚拟机栈的五个面试问题,涉及栈溢出的情况、栈大小调整、栈内存的分配、垃圾回收与虚拟机栈的关系以及局部变量的线程安全性。
|
4月前
|
存储 安全 Java
Java面试题:在JVM中,堆和栈有什么区别?请详细解释说明,要深入到底层知识
Java面试题:在JVM中,堆和栈有什么区别?请详细解释说明,要深入到底层知识
74 3
|
4月前
|
存储 缓存 监控
Java面试题:解释堆和栈的OutOfMemoryError通常在什么情况下会发生
Java面试题:解释堆和栈的OutOfMemoryError通常在什么情况下会发生
46 3
|
4月前
|
设计模式 安全 Java
Java面试题:请解释Java中的线程池以及为什么要使用线程池?请解释Java中的内存模型以及如何避免内存泄漏?请解释Java中的并发工具包以及如何实现一个简单的线程安全队列?
Java面试题:请解释Java中的线程池以及为什么要使用线程池?请解释Java中的内存模型以及如何避免内存泄漏?请解释Java中的并发工具包以及如何实现一个简单的线程安全队列?
42 1
|
4月前
|
存储 设计模式 监控
Java面试题:简述JVM的内存结构,包括堆、栈、方法区等。栈内存优化的方法有 哪些?
Java面试题:简述JVM的内存结构,包括堆、栈、方法区等。栈内存优化的方法有 哪些?
42 0
|
4月前
|
设计模式 安全 NoSQL
Java面试题:设计一个线程安全的单例模式,并解释其内存占用和垃圾回收机制;使用生产者消费者模式实现一个并发安全的队列;设计一个支持高并发的分布式锁
Java面试题:设计一个线程安全的单例模式,并解释其内存占用和垃圾回收机制;使用生产者消费者模式实现一个并发安全的队列;设计一个支持高并发的分布式锁
61 0
|
4月前
|
Java 开发者
Java面试题:Java内存管理精要与多线程协同策略,Java内存管理:堆内存、栈内存、方法区、垃圾收集机制等,多线程编程的掌握,包括线程创建、同步机制的原理
Java面试题:Java内存管理精要与多线程协同策略,Java内存管理:堆内存、栈内存、方法区、垃圾收集机制等,多线程编程的掌握,包括线程创建、同步机制的原理
36 0
|
4月前
|
算法 Java 开发者
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
35 0