STL中stack和queue的使用以及模拟实现

简介: STL中stack和queue的使用以及模拟实现

一、 stack的介绍和使用

1、stack的介绍

stack文档阅读

  1. stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。
  2. stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定类作为其底层的,元素特定容器的尾部(即栈顶)被压入和弹出。
  3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类,这些容器类应该支持以下操作:
empty 判空操作
back 获取尾部元素操作
push_back 尾部插入元素操作
pop_back 尾部删除元素操作
  1. 标准容器vector、deque、list均符合这些需求,默认情况下,如果没有为stack指定特定的底层容器,默认情况下使用deque。

2、stack的使用

函数说明 接口说明
stack() 构造空的栈
empty() 检测stack是否为空
size() 返回stack中元素的个数
top() 返回栈顶元素的引用
push() 将元素val压入stack中
pop() 将stack中尾部的元素弹出

例如:OJ最小栈

class MinStack {
public:
    void push(int val) {
        _st.push(val);
        if(_min_st.empty() || val <= _min_st.top()) {
            _min_st.push(val);
        }
    }
    void pop() {
        if(_st.top() == _min_st.top())
            _min_st.pop();
        _st.pop();
    }
    int top() {
        return _st.top();
    }
    int getMin() {
        return _min_st.top();
    }
private:
    stack<int> _st;
    stack<int> _min_st;
};

二、queue的介绍和使用

1、queue的介绍

queue文档阅读

  1. 队列是一种容器适配器,专门用于在FIFO上下文(先进先出)中操作,其中从容器一端插入元素,另一端提取元素。
  2. 队列作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从队尾入队列,从队头出队列。
  3. 底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
empty 检测队列是否为空
size 返回队列中有效元素的个数
front 返回队头元素的引用
back 返回队尾元素的引用
push_back 在队列尾部入队列
pop_front 在队列头部出队列
  1. 标准容器类deque和list满足了这些要求。默认情况下,如果没有为queue实例化指定容器类,则使用标准容器deque。

2、queue的使用

函数声明 接口说明
queue() 构造空的队列
empty() 检测队列是否为空,是返回true,否则返回false
size() 返回队列中有效元素的个数
front() 返回队头元素的引用
back() 返回队尾元素的引用
push() 在队尾将元素val入队列
pop() 将队头元素出队列
class MyStack {
public:
    queue<int> q;
    /** Initialize your data structure here. */
    MyStack() {
    }
    /** Push element x onto stack. */
    void push(int x) {
        int n = q.size();
        q.push(x);
        for (int i = 0; i < n; i++) {
            q.push(q.front());
            q.pop();
        }
    }
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int r = q.front();
        q.pop();
        return r;
    }
    /** Get the top element. */
    int top() {
        int r = q.front();
        return r;
    }
    /** Returns whether the stack is empty. */
    bool empty() {
        return q.empty();
    }
};

三、模拟实现

1、模拟实现stack

stack.h

#pragma once
#include<deque>
namespace mystack
{
  template<class T, class Container = std::deque<T> >
  class stack
  {
  public:
    void push(const T& x)
    {
      _con.push_back(x);
    }
    void pop()
    {
      _con.pop_back();
    }
    const T& top()
    {
      return _con.back();
    }
    size_t size()
    {
      return _con.size();
    }
    bool empty()
    {
      return _con.empty();
    }
  private:
    Container _con;
  };
}

2、模拟实现queue

queue.h

#pragma once
#include<deque>
namespace myqueue
{
    template<class T,  class Container = std::deque<T>>
  class queue
  {
  public:
    void push(const T& x)
    {
      _con.push_back(x);
    }
    void pop()
    {
      _con.pop_front();
    }
    const T& front()
    {
      return _con.front();
    }
    const T& back()
    {
      return _con, back();
    }
    size_t size()
    {
      return _con.size();
    }
    bool empty()
    {
      return _con.empty();
    }
  private:
    Container _con;
  };
}
目录
相关文章
|
7月前
|
设计模式 存储 C++
C++:Stack和Queue的模拟实现
C++:Stack和Queue的模拟实现
|
4月前
|
C++ 容器
【C++】stack与queue的使用以及模拟实现
【C++】stack与queue的使用以及模拟实现
|
5月前
|
设计模式 算法 Java
【c++】STL之stack和queue详解
【c++】STL之stack和queue详解
55 1
|
5月前
|
设计模式 安全 数据管理
【c++】stack和queue模拟实现
【c++】stack和queue模拟实现
35 1
|
7月前
|
编译器 C++ 容器
【STL】stack与queue的底层原理及其实现
【STL】stack与queue的底层原理及其实现
|
存储 设计模式 C++
C++ STL stack & queue
stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。
|
7月前
|
存储 C++ 容器
【C++初阶】STL详解(七)Stack与Queue的模拟实现
【C++初阶】STL详解(七)Stack与Queue的模拟实现
36 1
|
7月前
|
存储 C++ 容器
STL--stack、queue实现
STL--stack、queue实现
|
7月前
|
设计模式 C++ 容器
stack和queue的模拟实现
stack和queue的模拟实现
57 0
|
存储 C++ 容器
C++:deque的概念以及stack和queue的模拟实现
C++:deque的概念以及stack和queue的模拟实现