首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >栈与队列基础知识

栈与队列基础知识

作者头像
小飞侠xp
发布2018-08-29 14:37:32
3140
发布2018-08-29 14:37:32
举报

栈,是先进后出的线性表,标准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;
};
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018.03.08 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 队列
    • 1.使用队列实现栈
      • 算法设计,push时调整
    • 使用栈实现队列
      • 算法设计1,push时调整
      • 算法设计2,双栈法
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档