我正在C中使用Vector实现队列
我使用sz
变量来跟踪任何插入/删除操作中队列中有多少空闲元素。
我在进行比较的实现中遇到一个问题:
sz < vec.size() - 1
在某个时候,这条线开始返回0
,比较是
-1 < 5
有助于这样做的一件事
int vecsz = vec.size() - 1;
int regsz = sz;
if (regsz < vecsz)
{
sz++;
}
即使有帮助,我仍然不明白为什么。有人可以对此有所启发吗?
队列
#include <iostream>
#include <vector>
using namespace std;
template <typename Object>
class queue
{
public:
queue(int s)
: vec(s)
{
sz = s - 1;
}
queue () { }
~queue() { }
/**
* Add element to Q and decrease size
*/
void enque(Object obj)
{
if (sz >= 0) {
vec[sz] = obj;
sz--;
}
}
/**
* Remove element from Q and increase size
*/
Object deque()
{
// grab last element
int last = vec[vec.size() - 1];
// remove last element from array
vec.pop_back();
// insert 0 in the front
vec.insert(vec.begin(), 0);
int vecsz = vec.size() - 1;
int regsz = sz;
// increase size tracking var
if (regsz < vecsz)
{
sz++;
}
return last;
}
void print() {
for (int i = 0; i < vec.size(); ++i) {
cout << "i: " << vec[i] << endl;
}
}
private:
vector<int> vec;
int sz;
};
主要
int main()
{
queue<int> Q(5);
cout << "Empty Q:" << endl;
Q.print();
cout << endl;
Q.enque(1);
Q.enque(2);
Q.enque(3);
cout << "Full Q1:" << endl;
Q.print();
cout << "Deque " << endl;
cout << Q.deque() << " " << Q.deque() << " " << Q.deque() << " " << endl;
cout << Q.deque() << endl;
cout << "Print " << endl;
Q.print();
cout << "Enqueue " << endl;
Q.enque(10);
Q.enque(20);
Q.enque(30);
Q.enque(40);
Q.enque(50);
cout << "\nFull Q2:" << endl;
Q.print();
cout << endl;
cout << Q.deque() << endl;
Q.enque(100);
cout << "Full Q3:"; Q.print(); cout << endl;
cout << Q.deque() << endl;
cout << Q.deque() << endl;
cout << Q.deque() << endl;
cout << Q.deque() << endl;
return 0;
}
这就是为什么不混合带符号和无符号类型很重要的原因。用
sz < vec.size() - 1
您正在将有符号整数与无符号整数进行比较。当您这样做时,编译器会将有符号整数转换为与无符号整数相同的类型。当您这样做时,有符号整数恰好为负,那么您得到的值是无符号类型的最大值,减去有符号整数的值,所以
-1 < 5
变成
4294967295 (for 32 bits) or 18446744073709551615 (for 64 bits) < 5
这是错误的。
要解决此问题,请设置sz
无符号类型。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句