c++中栈与队列的实现

发布时间:2020-07-27 21:31:28 作者:走走停停吧
来源:网络 阅读:309
  1. 栈:具有先进后出的特点,且只能在一端进行插入与删除的操作,栈的实现如下所示


  2. struct truetype

  3. {

  4. bool get()

  5. {

  6. return true;

  7. }

  8. };

  9. struct falsetype

  10. {

  11. bool get()

  12. {

  13. return false;

  14. }

  15. };

  16. template<class T>

  17. struct typetraits

  18. {

  19. typedef falsetype  isnpodtype;

  20. };

  21. template <>

  22. struct typetraits<int>

  23. {

  24. typedef truetype  ispodtype;

  25. };


  26. template<class T>

  27. class stack

  28. {

  29. protected:

  30. T *_a;

  31. size_t _top;

  32. size_t _capacity;

  33. public:

  34. stack()

  35. : _top(0)

  36. , _capacity(3)

  37. {

  38. _a = new T[_capacity];

  39. }

  40. ~stack()

  41. {

  42. if (_a)

  43. delete[] _a;

  44. }

  45. void  checkcapacity()

  46. {

  47. if (_top == _capacity)

  48. {

  49. _capacity = 2 * _capacity;

  50. T *tem = new T[_capacity];

  51. if ((typetraits<T>::ispodtype()).get())

  52. {

  53. memcpy(tem, _a, sizeof(T)*_capacity);

  54. delete[]_a;

  55. _a = tem;

  56. }

  57. else

  58. {

  59. int i = 0;

  60. for (i = 0; i < _top; i++)

  61. {

  62. tem[i] = _a[i];


  63. }

  64. delete[]_a;

  65. _a = tem;

  66. }

  67. }

  68. }

  69. void push(const T&x)

  70. {

  71. checkcapacity();

  72. _a[_top] = x;

  73. _top++;

  74. }

  75. void pop()

  76. {

  77. _top--;

  78. }

  79. bool Empty()

  80. {

  81. return _top == 0;


  82. }

  83. T &Top()

  84. {

  85. if (_top > 0)


  86. {

  87. size_t ret = _top;

  88. _top--;

  89. return _a[ret - 1];

  90. }

  91. }


  92. };

  93. int main()

  94. {

  95. stack<int> s1;

  96. s1.push(1);

  97. s1.push(2);

  98. s1.push(3);

  99. s1.push(4);

  100. while (!s1.Empty())

  101. {

  102. cout << s1.Top() << " ";

  103. }

  104. getchar();

  105. return 0;

  106. }

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;

}


推荐阅读:
  1. 数据结构--栈与队列
  2. java中的栈与队列有区别吗

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

队列 栈与队列

上一篇:SpringMvc与Struts2的对比,孰优孰劣

下一篇:updateByExample与updateByExampleSelective的区别

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》