剑指offer之两个队列实现栈的问题

简介: 剑指offer之两个队列实现栈的问题

1 问题

两个队列实现栈的插入和获取头部元素的功能

2 分析

1)获取头部元素的功能分析:

我们有2个队列,我们知道队列的特点的先进先出,而栈的特点是先进后出,比如我们有数据1,2,3,4,我们分别依次压入队列1,队列2目前是空,我们需要有栈的效果,加上队列2也是先进先出的特点,意味着我们队列2里面的数据依次是4,3,2,1入队列2,现在问题转成了我们怎么操作队列1里面的数据让它依次弹出4,3,2,1入队列2

接下来我们分析怎么操作队列1里面的数据让它依次弹出4,3,2,1入队列2

我们知道队列1数据进去的时候是1,2,3,4.我们需要得到4,我们可front()得到进入队列的第一个元素,然后push到队列1,然后执行pop()函数,那么队列1就变成了2,3,4,1, 同理我们也这样操作,知道元素4在队列的最头部,队列1也就变成了3,2,1,4,我们把4弹出来压入到队列2里面去,然后队列1的数据是3,2,1,我们依然按照上面的方法,把3弹出来压入队列2,最后队列2就入队列的元素依次是4,3,2,1 再把队列2弹出头部元素,就是我们栈获取头部元素的效果。

2)插入元素的功能分析:

如果队列2不为空的情况下,我们需要先把队列2里面的元素一一弹出来放到(push)队列1里面去,确保队列2是空的之后,然后再把新的元素push到队列的1的尾巴

如果队列2为空的情况下,我们可以直接把新的元素push到队列1里面去就行。


3 代码实现

#include <iostream>
#include <queue>
using namespace std;
class student
{
public:
    student(){}
    ~student(){}
    student(std::string name, std::string age, std::string sex) 
    {
        this->name = name;
        this->age = age;
        this->sex = sex;
    }
    void toString()
    {
        std::cout << "name is "<< name << " age is "<< age << " sex is "<< sex << std::endl;
    }
private:
    std::string name;
    std::string age;
    std::string sex;
};
template <typename T> 
class Test
{
public:
    Test(){}
    ~Test(){}
    Test(const T& t);
    //往队列里面添加元素
    void add(const T& t);
    //往队列里面删除元素
    T top();
private:
    std::queue<T> queue1;
    std::queue<T> queue2;
};
template <typename T> void Test<T>::add(const T& t)
{
    if (!queue2.empty())
    {
         T& top = queue2.front();
         queue1.push(top);
         queue2.pop();
    }
    queue1.push(t);
}
template <typename T> T Test<T>::top()
{
    if (queue2.empty())
    {
        while (!queue1.empty())
        {
            int size = queue1.size();
            for (int i = 1; i < size; ++i)
            {
                T& top = queue1.front();
                queue1.push(top);
                queue1.pop();
            }
            T& value = queue1.front();
            queue2.push(value);
            queue1.pop();
        }
    }
    T top = queue2.front();
    queue2.pop();
    return top;
}
int main() {
    student std1("chenyu", "27", "man");
    student std2("chencaifeng", "27", "woman");
    student std3("chenzixuan", "3", "woman");
    student std4("chenzixi", "2", "woman");
    student std5("chenxuan", "21", "man");
    Test<student> stack;
    stack.add(std1);
    stack.add(std2);
    stack.add(std3);
    stack.add(std4);
    student top1 = stack.top();
    top1.toString();
    student top2 = stack.top();
    top2.toString(); 
    student top3 = stack.top();
    top3.toString(); 
    std::cout << "--------------------" << std::endl; 
    stack.add(std5);
    student top4 = stack.top();
    top4.toString(); 
    student top5 = stack.top();
    top5.toString();  
  return 0;
}

4 运行结果

name is chenzixi age is 2 sex is woman
name is chenzixuan age is 3 sex is woman
name is chencaifeng age is 27 sex is woman
--------------------
name is chenxuan age is 21 sex is man
name is chenyu age is 27 sex is man


相关文章
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
4天前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
1月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
44 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
38 7
|
3月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
332 9
|
3月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
55 1
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
46 9
|
3月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
99 5
|
3月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
116 21
|
3月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。

热门文章

最新文章