这篇具有很好参考价值的文章主要介绍了stack&queue的模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。
stack模拟:
stack的源代码:
stack的全部源代码就这些。
stack的代码少,原因在于采用了适配器模式,所谓适配器,以电器为例,每个电器都有电源适配器,中国的家用电源为220V的交流电,但是几乎没有电器需要220V的交流电,所以每个电器都有一个电源适配器,将家庭电压转换为自己需要的电压。stack的适配器原理就是将某个容器转换为符合stack语法的容器。就不需要再进行开辟空间之类的操作了。
图示位置可见,是对deque容器进行转换。deque是什么?
简单的来说,deque是一个双端队列,虽然是队列,但并不是先进先出,而且deque支持随机访问,头插,头删,尾插,尾删,就机制而言,集合了list和vector的优点,但不代表能代替list和vector,因为在效率方面不如list和vector。
目前知道这些就可以了。
deque适合进行头尾删除的操作,作为stack的源容器很适合。vector和list也可以。stack的特性要求,vector和list都能满足。
queue模拟:
queue的源代码:
这些也是queue的全部代码。
简单总结一下:
stack的适配容器包括:deque,list,vector;
queue的适配容器包括:deque,list;
priority_queue的适配容器包括:vector,deque
queue不支持vector是因为vector不支持头删;虽然priority_queue也支持deque,但是deque的随机访问效率并不高,所以不推荐使用deque。
创建queue.h stack.h test.cpp
queue.h中:
#pragma once
#include<deque>
using namespace std;
template<class T, class container = deque<T>>
//deque是一个双端队列,虽然是队列,但并不是先进先出,而且deque支持随机访问,头插,头删,尾插,尾删
class myQueue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_front();
//vector不支持头部的删除,所以vector不能做queue的原容器。
}
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;
};
stack.h中
#pragma once
#include<deque>
using namespace std;
template<class T, class container = deque<T>>
//deque是一个双端队列,虽然是队列,但并不是先进先出,而且deque支持随机访问,头插,头删,尾插,尾删
class myStack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
const T& top()
//直接引用返回数据可以被修改,不加引用如果T是string之类的,深拷贝代价较大
{
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
container _con;
};
test.cpp中
#define _CRT_SECURE_NO_WARNINGS 1
#include"queue.h"
#include"stack.h"
#include<iostream>
#include<vector>
#include<list>
using namespace std;
void test_stack1()
{
myStack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
cout << st.empty() << " " << st.size() << endl;
for (; !st.empty(); )
{
cout << st.top() << " ";
st.pop();
}
}
void test_stack2()
{
myStack<int,vector<int>> st;
//stack之所以叫空间适配器就是因为可以适配不同类型的容器
//传的容器如果为string似乎也能实现,string中的字符类型本质上也是整形,
//但是用string意味着存储范围只能是char类型的范围,准确来说是数据被截断了。
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
cout << st.empty() << " " << st.size() << endl;
while (!st.empty())
//执行效果和test_stack1是一样的。
{
cout << st.top() << " ";
st.pop();
}
cout << endl;
}
void test_queue1()
{
myQueue<int> qu;
qu.push(1);
qu.push(2);
qu.push(3);
qu.push(4);
qu.push(5);
cout << qu.empty() << " " << qu.size() << endl;
while (!qu.empty())
{
cout << qu.front() << " ";
qu.pop();
}
cout << endl;
}
void test_queue2()
{
myQueue<int,list<int>> qu;
qu.push(1);
qu.push(2);
qu.push(3);
qu.push(4);
qu.push(5);
cout << qu.empty() << " " << qu.size() << endl;
while (!qu.empty())
{
cout << qu.front() << " ";
qu.pop();
}
cout << endl;
}
int main()
{
test_stack2();
test_queue2();
return 0;
}
文章来源地址https://www.toymoban.com/news/detail-464146.html
文章来源:https://www.toymoban.com/news/detail-464146.html
到了这里,关于stack&queue的模拟实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!