c++中栈与队列的实现
栈：具有先进后出的特点，且只能在一端进行插入与删除的操作，栈的实现如下所示
struct truetype
{
bool get()
{
return true;
}
};
struct falsetype
{
bool get()
{
return false;
}
};
template<class T>
struct typetraits
{
typedef falsetype isnpodtype;
};
template <>
struct typetraits<int>
{
typedef truetype ispodtype;
};
template<class T>
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<T>::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<int> s1;
s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4);
while (!s1.Empty())
{
cout << s1.Top() << " ";
}
getchar();
return 0;
}
2.队列：具有队头插入，队尾删除的特点，具有一个头指针和一个尾指针
template <class T>
struct Node
{
T _data;
Node <T> *_next;
Node(const T &data=0)
{
_data = data;
_next = NULL;
}
};
template <class T>
class Queue
{
protected:
Node<T> *_head;
Node <T>*_tail;
public:
Queue()
:_head(NULL)
, _tail(NULL)
{}
~Queue()
{
Node<T> *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<T> *newNode = new Node<T>(x);
if (_tail == NULL)
{
_tail = newNode;
_head = _tail;
}
else
{
_tail->_next = newNode;
_tail = newNode;
}
}
void pop()
{
Node<T>*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 <T>*ret = _head;
_head = _head->_next;
return ret->_data;
}
T &Back()
{
Node <T>*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<int> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
q.pop();
q.show();
getchar();
return 0;
}
声明：本站所有文章资源内容，如无特殊说明或标注，均为采集网络资源。如若本站内容侵犯了原著者的合法权益，可联系本站删除。
