c++中栈与队列的实现
栈:具有先进后出的特点,且只能在一端进行插入与删除的操作,栈的实现如下所示
目前成都创新互联公司已为上1000+的企业提供了网站建设、域名、雅安服务器托管、网站托管、企业网站设计、九江网站维护等服务,公司将坚持客户导向、应用为本的策略,正道将秉承"和谐、参与、激情"的文化,与客户和合作伙伴齐心协力一起成长,共同发展。
struct truetype
{
bool get()
{
return true;
}
};
struct falsetype
{
bool get()
{
return false;
}
};
template
struct typetraits
{
typedef falsetype isnpodtype;
};
template <>
struct typetraits
{
typedef truetype ispodtype;
};
template
class stack
{
protected:
T *_a;
size_t _top;
size_t _capacity;
public:
stack()
: _top(0)
, _capacity(3)
{
_a = new T[_capacity];
}
~stack()
{
if (_a)
delete[] _a;
}
void checkcapacity()
{
if (_top == _capacity)
{
_capacity = 2 * _capacity;
T *tem = new T[_capacity];
if ((typetraits
::ispodtype()).get()) {
memcpy(tem, _a, sizeof(T)*_capacity);
delete[]_a;
_a = tem;
}
else
{
int i = 0;
for (i = 0; i < _top; i++)
{
tem[i] = _a[i];
}
delete[]_a;
_a = tem;
}
}
}
void push(const T&x)
{
checkcapacity();
_a[_top] = x;
_top++;
}
void pop()
{
_top--;
}
bool Empty()
{
return _top == 0;
}
T &Top()
{
if (_top > 0)
{
size_t ret = _top;
_top--;
return _a[ret - 1];
}
}
};
int main()
{
stack
s1; s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4);
while (!s1.Empty())
{
cout << s1.Top() << " ";
}
getchar();
return 0;
}
2.队列:具有队头插入,队尾删除的特点,具有一个头指针和一个尾指针
template
struct Node
{
T _data;
Node
Node(const T &data=0)
{
_data = data;
_next = NULL;
}
};
template
class Queue
{
protected:
Node
Node
public:
Queue()
:_head(NULL)
, _tail(NULL)
{}
~Queue()
{
Node
if (_head == NULL)
return;
if (_head == _tail)
{
delete _head;
_head = NULL;
_tail = _head;
}
else
{
while (_head)
{
pop();
}
}
}
void push(const T&x)
{
Node
if (_tail == NULL)
{
_tail = newNode;
_head = _tail;
}
else
{
_tail->_next = newNode;
_tail = newNode;
}
}
void pop()
{
Node
if (_head == NULL)
return;
if (_head == _tail)
{
delete _head;
_head = NULL;
_tail = _head;
}
else
{
ret = _head;
_head = _head->_next;
delete ret;
}
}
T &Front()
{
Node
_head = _head->_next;
return ret->_data;
}
T &Back()
{
Node
_tail = _head->_tail;
return _tail->_data;
}
bool Empty()
{
return _head == _tail;
}
void show()
{
while (_head)
{
cout << _head->_data << " ";
_head = _head->_next;
}
}
};
int main()
{
Queue
q.push(1);
q.push(2);
q.push(3);
q.push(4);
q.pop();
q.show();
getchar();
return 0;
}
当前名称:c++中栈与队列的实现
分享路径:http://hbruida.cn/article/jjjhei.html