栈：具有先进后出的特点，且只能在一端进行插入与删除的操作，栈的实现如下所示
在解放等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供成都网站设计、做网站 网站设计制作按需网站设计,公司网站建设,企业网站建设,品牌网站设计,全网营销推广,成都外贸网站建设公司,解放网站建设费用合理。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 *_next;
Node(const T &data=0)
{
_data = data;
_next = NULL;
}
};
template
class Queue
{
protected:
Node *_head;
Node *_tail;
public:
Queue()
:_head(NULL)
, _tail(NULL)
{}
~Queue()
{
Node *ret = NULL;
if (_head == NULL)
return;
if (_head == _tail)
{
delete _head;
_head = NULL;
_tail = _head;
}
else
{
while (_head)
{
pop();
}
}
}
void push(const T&x)
{
Node *newNode = new Node(x);
if (_tail == NULL)
{
_tail = newNode;
_head = _tail;
}
else
{
_tail->_next = newNode;
_tail = newNode;
}
}
void pop()
{
Node*ret = NULL;
if (_head == NULL)
return;
if (_head == _tail)
{
delete _head;
_head = NULL;
_tail = _head;
}
else
{
ret = _head;
_head = _head->_next;
delete ret;
}
}
T &Front()
{
Node *ret = _head;
_head = _head->_next;
return ret->_data;
}
T &Back()
{
Node *ret = _tail;
_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;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
q.pop();
q.show();
getchar();
return 0;
}
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
网站栏目：c++中栈与队列的实现-创新互联
网址分享：
http://cdkjz.cn/article/dhdoej.html
