栈与队列基础知识

栈,是先进后出的线性表,标准STL的栈包括如下5种操作,设栈S: 1.取出栈顶元素:S.top(); 2.判断栈是否为空:S.empty(); 3.将元素x添加至栈:S.push(x) 4.弹出栈顶:S.pop(); 5.求栈存储元素的个数:S.size()

#include <stdio.h>
#include <stack>
int main(){
    std:: stack<int> S;
    if(S.empty()){
        printf("S is empty!");
     }
    S.push(5);
    S.push(6);
    S.push(10);
    printf("S.top = %d\n",S.top());
    S.pop();
    S.pop();
    printf("S.top = %d\n",S.top());
    printf("S.size = %d\n",S.size());
    return 0;
}

队列

队列,是先进先出的线性表,标准STL的队列包括如下6种操作,设队列Q: 1.判断队列是否为空:Q.empty(); 2.返回队列头部元素:Q.front(); 3.返回队列尾部元素:Q.back() 4.弹出队列头部元素:Q.pop(); 5.将元素x添加至队列:Q.push(x); 6.求队列存储元素的个数:Q.size()

# include <stdio.h>
# include <queue>
int main(){
    std::queue<int> Q;
    if(Q.empty()){
        printf("Q is empty!\n");
    }
    Q.push(5);
    Q.push(6);
    Q.push(10);
    printf("Q.front = %d \n",Q.front());
    Q.pop();
    Q.pop();
    printf("Q.front = %d \n",Q.front());
    Q.push(1);
    printf("Q.back = %d \n",Q.back());
    printf("Q.size = %d\n",Q.size());
    return 0;
    
}

1.使用队列实现栈

LeetCode 225. Implement Stack using Queues 设计一个栈,支持如下操作,栈的内部存储数据的结构为队列,队列的方法只 能包括push、peek(front)、pop、size、empty等标准的队列方法。

class MyStack{
public:
    MyStack(){
}
    void push(int x){
}
    int pop(){
}
    int top(){
}
    bool empty(){
}        
};
算法设计,push时调整

普通队列实现栈stack,内部存储结构时队列Queue:

#include<queue>
class Mystack{
public:
    Mystack(){}
    void push(int x){
        std::queue<int> temp_queue;
        temp_queue.push(x);//先将新元素push进入temp_queue
        while(!_data.empty()){
            temp_queue.push(_data.front());//将数据队列元素导入临时队列
            _data.pop();
        }
        while(!temp_queue.empty()){
            _data.push(temp_queue.front());//将临时队列元素再导入数据队列
            temp_queue.pop();
        }
    }
int pop(){
    int x= _data.front();
    _data.pop();
    return x;
}
int top(){
    return _data.front();
}
bool empty(){
     return _data.empty();
}
private:
    std::queue<int> _data;
};

使用栈实现队列

LeetCode 232. Implement Queue using Stacks 设计一个队列,队列支持如下操作,尽量使队列的各项操作的平均时间复杂度是 常数级O(1);队列的内部存储数据的结构为栈,栈的方法只能包括push、top、 pop、size、empty等标准的栈方法。 1.push(x) : 将元素x压入队列中 2.pop() : 弹出(移除)队列头部元素 3.peek() : 返回队列头部元素(即为front) 4.empty() : 判断队列是否是空

算法设计1,push时调整

1.在队列push元素时,利用临时栈调换元素次序

2.将原数据栈内容push进入临时栈temp_stack

3.将新数据push进入临时栈temp_stack

4.将临时栈temp_stack中的元素push进入数据栈data_stack

#include <stack>
class MyQueue{
public:
    MyQueue(){
    }
    void push(int x){
        std::stack<int> temp_stack
        while(! _data.empty){
            temp_stack.push(_data.top());
            _data.pop();
    }
        temp_stack.push(x);   
        while(!temp_stack.empty()){
        _data.push(temp_stack.top());
        temp.pop()  
    }
    }
int pop(){
    int x = _data.top();
    _data.pop;
    return x;
}
int peek(){
    return _data.top();
}
bool empty(){
    return _data.empty();
}
};
算法设计2,双栈法

双栈法,即用两个栈,来实现队列的功能。一个栈为输入栈input_stack,一个栈为输出栈output_stack。 算法过程,整体各项操作的平均算法复杂度常数级,O(1): 1.push(x)操作:将待压入的元素x直接push至input_stack中。 2.pop或peek(front)操作,在获取队列头部元素时,可能需要对两个栈进行调整(adjust): 如果output_stack不空,不需要调整,直接返回或弹出output_stack栈顶元素。 否则,将input_stack全部元素push进入output_stack,每push一个元素input_stack弹出一个元素;然后再返回或弹 出output_stack栈顶元素。 3.empty操作:input_stack与output_stack均为空时,返回true,否则返回false。

#include <stack>
class MyQueue{
public:
    MyQueue(){
    }
    void push(int x){
        _input.push(x);//直接将x push进入_input
    }
    int pop(){
        adjust();//调整再进行pop
        int x = _output.top();
        _output.pop();
        return x;    
    }
    int peek(){
        adjust();
        return _output.top();
    }
    bool empty(){//当input_stack与output_stack 同时为空时,才返回true
        return _input.empty()&&_output.empty();
    }
private:
    void adjust(){
        if(!_output.empty()){
            return ;
        }
        while(!_input.empty()){
            _output.push(_input.top());
            _input.pop();
        }
}
    std::stack<int> _input;
    std::stack<int> _output;
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏玄魂工作室

如何学python 第八课 流程控制-For,While,循环语句,函数

循环语句 也许你会问,什么是‘循环’?在脚本程序里,循环就是‘在一定情况下一次又一次的执行某些代码’。举个例子来说,假设你很饿,桌上有好多好多个馒头,当你依旧饿...

3469
来自专栏猿人谷

size_type、size_t、differentce_type以及ptrdiff_t

目录(?)[-] size_type size_t different_type ptrdiff_t size_t是unsigned类型,用于指明数...

2207
来自专栏机器之心

资源 | 忘了Python关键语句?这份备忘录拯救你的记忆

Python 3 Cheat Sheet 一共包含两页,分成了多个框图,涉及基本的 Python 数据结构、数学运算、条件和循环语句、文件读写,以及异常值处理等...

1213
来自专栏专注研发

交换排序—冒泡排序(Bubble Sort)

在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们...

1212
来自专栏诸葛青云的专栏

C语言位运算的妙用你知道多少?

位运算在驱动开发中是经常遇到的,尤其是置0和置1。既要指定的位数发生变化,又不能改变其它位的值,还要高效率的编写代码,这时候技巧就很重要了。在位运算中有几个符号...

1974
来自专栏chenjx85的技术专栏

leetcode-674-Longest Continuous Increasing Subsequence

2085
来自专栏IT可乐

深入理解计算机系统(2.5)------C语言中的有符号数和无符号数以及扩展和截断数字

  上一篇博客我们讲解了计算机中整数的表示,包括无符号编码和补码编码,以及它们之间的互相转换,个人觉得那是非常重要的知识要点。这篇博客我们将介绍C语言中的有符号...

2768
来自专栏cs

c++那些事儿12.0 STL--Map

知识点综述: ---- map:关联容器。 1.0 由key--value组成,通过key,查找value,关键字key唯一。 2....

3345
来自专栏赵俊的Java专栏

两数之和

2123
来自专栏软件开发 -- 分享 互助 成长

C++STL 之排列

固然我们可以自己使用递归编写全排列程序,但是既然STL里面已将有了这个功能为什么不直接用呢,下面就写一下直接使用C++ STL生成全排序的程序 函数名:next...

2027

扫码关注云+社区

领取腾讯云代金券