c++中栈与队列的实现

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. 
    

27. template<class T>

28. class stack

29. {

30. protected:

31. T *_a;

32. size_t _top;

33. size_t _capacity;

34. public:

35. stack()

36. : _top(0)

37. , _capacity(3)

38. {

39. _a = new T[_capacity];

40. }

41. ~stack()

42. {

43. if (_a)

44. delete[] _a;

45. }

46. void  checkcapacity()

47. {

48. if (_top == _capacity)

49. {

50. _capacity = 2 * _capacity;

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

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

53. {

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

55. delete[]_a;

56. _a = tem;

57. }

58. else

59. {

60. int i = 0;

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

62. {

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

64. 
    

65. }

66. delete[]_a;

67. _a = tem;

68. }

69. }

70. }

71. void push(const T&x)

72. {

73. checkcapacity();

74. _a[_top] = x;

75. _top++;

76. }

77. void pop()

78. {

79. _top--;

80. }

81. bool Empty()

82. {

83. return _top == 0;

84. 
    

85. }

86. T &Top()

87. {

88. if (_top > 0)

89. 
    

90. {

91. size_t ret = _top;

92. _top--;

93. return _a[ret - 1];

94. }

95. }

96. 
    

97. };

98. int main()

99. {

100. stack<int> s1;

101. s1.push(1);

102. s1.push(2);

103. s1.push(3);

104. s1.push(4);

105. while (!s1.Empty())

106. {

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

109. }

110. getchar();

111. return 0;

112. }

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;

}