【stack和queue的模拟实现】—— 我与C++的不解之缘（十五）

星辰与你

发布于 2024-11-21 17:43:51

1460

文章被收录于专栏：学习学习

前言

stack 和 queue使用起来都非常简单，现在来模拟实现一下，理解其底层的原理。

在实现之前，应该知道，stack 和 queue 都是容器适配器，通过看官网文件也可以看出来；其默认的容器都是deque（双端队列）。

stack 和 queue 都是在容器的基础上进行了封装，实现了各自的操作。

（在下面的实现中stack默认容器用vector，queue默认容器用list）

栈和队列的使用

栈的使用

首先，STL中的栈是基于容器适配器实现的，默认容器是deque。

使用栈需要包含头文件:

#include<stack>

1.1 栈的基本操作

先看一下，栈提供的接口函数

常用方法：

push(): 将元素 val 压入栈顶。
pop(): 移除栈顶元素。
top(): 返回栈顶元素（但不移除）。
empty(): 判断栈是否为空。
size(): 返回栈的元素数量。

1.2 栈的使用

现在简单使用一下stack：

void test_stack() {
    //创建一个栈——存储整形
    stack<int> s;  
    //入栈
    s.push(1);
    s.push(2);
    s.push(3);
    //栈中元素
    cout << "元素个数: " << s.size() << endl;
    //栈顶元素
    cout << "栈顶元素: " << s.top() << endl;
    //出栈
    s.pop();
    //依次输出栈中的数据
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;
    return 0;
}

输出结果：

元素个数: 3
栈顶元素: 3
2 1

1.3 应用实例：点击消除

栈可以用来解决括号匹配这一类的问题。

括号匹配之前已经做过了，这里来用栈做这样的一道题：点击消除_牛客题霸_牛客网

题目描述：

这题思路比较简单，就是遍历字符串时，不断入栈，出栈（字符串中字符与栈顶元素相等）；最后输出即可。

需要注意的是：这里使用数组来模拟栈，方便输出

当然也可以使用栈，不过输出时顺序是反的，需要进行处理。

#include <iostream>
using namespace std;

int main() {
    string str;
    cin>>str;
    string ret;
    for(auto ch: str)
    {
        if(ret.size()==0||ret[ret.size()-1]!=ch)
        {
            ret.push_back(ch);
        }
        else 
        {
            ret.pop_back();
        }
    }
    if(ret.empty())
    {
        cout<<'0';
        return 0;
    }
    cout<<ret;
    return 0;
}

队列的使用

2.1 队列的基本操作

STL 中的队列（queue）也是一种容器适配器，默认底层容器也是 deque。

使用栈需要包含头文件:

#include<queue>

常用方法：

push(): 将元素 val 插入队尾。
pop(): 移除队头元素。
front(): 返回队头元素（不移除）。
back(): 返回队尾元素（不移除）。
empty(): 判断队列是否为空。
size(): 返回队列的元素数量。

2.2 队列的使用

简单使用一下队列：

void test_queue()
{
    //创建一个队列——存储整型
    queue<int> q;
    //入队列
    q.push(10);
    q.push(20);
    q.push(30);
    cout << "数据个数: " << q.size() << endl;
    cout << "队头元素: " << q.front() << endl;
    cout << "队尾元素: " << q.back() << endl;
    //出队列
    q.pop();
    cout << "队列中数据: ";
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;
}

输出结果：

数据个数: 3
队头元素: 10
队尾元素: 30
队列中数据: 20 30

栈和队列的模拟实现

`stack` 模拟

学习过初阶数据结构的栈，大概知道栈是怎么实现的，使用过STL里的stack也知道具体哪些操作，这里就直接开始实现。

1.默认成员函数

对于默认成员函数，因为这里stack是对容器的封装，所以那些构造函数、析构函数、赋值运算符重载等都不需要我们自己去实现，编译器默认生成的会去调用vector（容器）的默认成员函数。

	template<class T, class Container = vector<T>>
	class stack
	{
		stack() {}

	private:
		Container _con;
	};

2.基本操作

栈的基本操作无疑就是，入栈、出栈、取栈顶元素、判断栈是否为空。

入栈：

直接调用容器vector的尾插即可。

		void push(const T& x)
		{
			_con.push_back(x);
		}

出栈：

直接调用容器vector的尾删

		void pop()
		{
			_con.pop_back();
		}

取栈顶元素：

直接返回容器vector的最后一个元素即可，即调用back()函数

		T& top()
		{
			return _con.back();
		}
		const T& top()const 
		{
			return _con.back();
		}

判断是否为空：

调用容器的empty函数即可

		bool empty() const
		{
			return _con.empty();
		}

返回栈中元素个数：

		size_t size() const 
		{
			return _con.size();
		}

swap

直接调用容器的swap函数即可。

		void swap(stack& st)
		{
			_con.swap(st._con);
		}

到这里就简单实现了我们的stack 结构了，是不是感觉很简单呢？

	template<class T, class Container = vector<T>>
	class stack
	{
	public:
		stack() {}
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_back();
		}
		T& top()
		{
			return _con.back();
		}
		const T& top()const 
		{
			return _con.back();
		}
		bool empty() const
		{
			return _con.empty();
		}
		size_t size() const 
		{
			return _con.size();
		}
		void swap(Container& st)
		{
			_con.swap(st._con);
		}
	private:
		Container _con;
	};

`queue` 模拟

默认成员函数

和stack一样，我们不需要去实现它的默认成员函数，编辑器默认生成的就已经可以满足我们的需求了。

基本操作

push

入队列，在队尾插入

		void push(const T& x)
		{
			_con.push_back(x);
		}

pop

出队列，从头部删除

		void pop()
		{
			_con.pop_front();
		}

front和back

返回队头数据 / 队尾数据

T& back()
{
	return _con.back();
}
const T& back() const
{
	return _con.back();
}
T& front()
{
	return _con.front();
}
const T& front()const
{
	return _con.front();
}

empty

		bool empty() const
		{
			return _con.empty();
		}

size

		size_t size() const
		{
			return _con.size();
		}

swap

		void swap(Container& con)
		{
			_con.swap(con);
		}

到这里stack和queue的模拟实现就完成了，感觉是不是很容易呢。

三、双端队列（`deque`）的栈和队列操作

deque（双端队列）既可以当作栈，也可以当作队列使用。我们可以在双端队列的两端进行插入和删除操作，从而更灵活地实现栈和队列的功能。

对于双端队列，简单来说，就是可以像vector那样随机访问，也可以像链表那样随机位置插入；但是，效率很低，（个人感觉，就是为了给stack和queue作默认容器适配器来用的。

这里就不过多描述双端队列了，感兴趣可以去看一下源码学习学习。

继续加油！！！

_con.size(); }

**`swap`**

~~~cpp
		void swap(Container& con)
		{
			_con.swap(con);
		}

到这里stack和queue的模拟实现就完成了，感觉是不是很容易呢。

三、双端队列（`deque`）的栈和队列操作

deque（双端队列）既可以当作栈，也可以当作队列使用。我们可以在双端队列的两端进行插入和删除操作，从而更灵活地实现栈和队列的功能。

这里就不过多描述双端队列了，感兴趣可以去看一下源码学习学习。

继续加油！！！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-11-17，如有侵权请联系 cloudcommunity@tencent.com 删除

c++

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

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

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度