第七十三讲 队列(2)

关于队列,我们说了deque,这一讲我们来看看堆栈stack,stack和deque一样简单,甚至还要简单一些,以至于我都不知道该从哪儿说起,好吧,我们来看看他的实现:
———————————
template<typename T,typename C=XXX<T>>
class stack{
public:

typedef typaname C::value_type value_type;



typedef typename C::size_type size_type;



typedef C container_type;

explicit stack(const C&

a = C()):c(a){ }

bool empty() const{

return c.empty();


}

size_type size() const{

return c.size();


}

value_type&

top()
{

return c.back();


}

const value_type&

top() const{

return c.back();


}

void push(const value_type&

x){

c.push_back();


}

void pop(){

c.pop_back();


}
protected:

C c;


};


———————————

上面的XXX指的是容器,具有支持push_back()和pop_back()的容器,所以,我们可以看得出,其实堆栈就是某些容器的界面,如果我们的XXX就是deque的话(默认情况下也就是我们上一讲说的deque),那么我们可以看下面的用法。
===================================

stack<char>s1;

//这句代码就是告诉编译器用deque<char>来保存char类型的元素。

stack<int,vector<int>>s2;

//这句代码就不再是默认情况了,我们使用的容器是vector,所以这里是用vector<int>来储存int类型的元素。
vector<int>v;


…………

void printf_element(v){

stack<int,vector<int>>s(v);


while(s.size()){

cout<<s.top()<<endl;


s.pop();


}

}
===================================
上面我们的例子是通过一个现有的容器v来初始化堆栈s的,不过这里有一个问题,当我们用一个现有的容器去初始化一个堆栈时,会复制里面的所有元素,这会是一笔不小的开销。还有一个问题:
—————————–
stack<int>s;


s.push(5);


if(s.empty()){

;


}else{

s.pop();

//1

s.pop();

//2
}
—————————
上面的代码看出什么了吗?在第一个pop时删除我们压入的5,但是第二个pop下去就出问题了,还记得我们以前说的下溢吗?就是一种无定义状态,自然会引起无数种bug。

好了,今天队列就说到这里吧,下一讲我们来结束队列——优先列队。
===============================
昨天回答一同学的问题,有朋友回复说关于中文怎么判断,因为昨天下班回来太晚,所以也没验证,今天再看了下昨天的回答,发现还是有些问题的,因为中文不同于一般的英文字符,一般的英文字符可以是一个字节,但是中文不是一个字符,所以完整的判断方式应该如下:
——————————
int myStr::ChineseChar(string str){
mstr = str;


count1 = 0;



for (int i = 0;

i <str.length();

i++){

wchar_t ch = mstr.at(i);



if (int(ch)>127){

i++;


wchar_t
temp = str.at(i);


if (int(temp) >127)

++count1;


}

}

return count1;


}
————————-


如果我们不用wchar_t而用char的话,在对比ASCII的时候用他和0对比:
————————–

char ch = mstr.at(i);



if(int(ch) <0){

i++;


char
temp = mstr.at(i);


if(int(temp)<0)

++count1;


}
————————-

其实通常情况下我们想要比较ASCII,可以不用转换为int的,因为char对象就可以完成隐士转换,但是为了明显一些,我通常都会显示转换。
==============================
回复D查看目录


原文始发于微信公众号(

C/C++的编程教室

):第七十三讲 队列(2)

|

发表评论