利用 C++ 单向链表实现队列

利用C++ 单向链表实现数据结构队列,其实和上一篇基本内容相同,仅仅是插入的时候在链表的尾部插入,取元素都是一样的,都从头部取。

 

[cpp][/cpp] 

  1. #pragma once
  2. #include “stdio.h”
  3. //利用链表来实现队列,先进先出
  4. class queue
  5. {
  6. public:
  7.     queue(void);
  8.     queue(int value);
  9.     ~queue(void);
  10. private:
  11.     int m_value;
  12.     queue* m_pnext;
  13. public:
  14.     void push(int value);
  15.     bool pop(int *value);
  16.     bool top(int *value);
  17.     bool empty();
  18.     int size();
  19.     void output();
  20.     void destroy();
  21. };
  22. #include “stdafx.h”
  23. #include “queue.h”
  24. //构造一个空的队列头指针
  25. queue::queue(void)
  26. {
  27.     m_value = 0x00;
  28.     m_pnext = NULL;
  29. }
  30. //构建一个队列结点
  31. queue::queue(int value)
  32. {
  33.     m_value = value;
  34.     m_pnext = NULL;
  35. }
  36. //输出被删除掉的结点
  37. queue::~queue(void)
  38. {
  39.     printf(“destroy node its value=%d\n”, m_value);
  40. }
  41. //元素入队列
  42. void queue::push(int value)
  43. {
  44.     queue *pnode = this;
  45.     while(pnode->m_pnext != NULL)
  46.     {
  47.         pnode = pnode->m_pnext;
  48.     }
  49.     queue *newnode = new queue(value);
  50.     pnode->m_pnext = newnode;
  51.     m_value++;
  52. }
  53. //元素出队列
  54. bool queue::pop(int *value)
  55. {
  56.     bool result = false;
  57.     if (m_pnext != NULL)
  58.     {
  59.         *value = m_pnext->m_value;
  60.         m_pnext = m_pnext->m_pnext;
  61.         result = true;
  62.         m_value–;
  63.     }
  64.     return result;
  65. }
  66. //得到队列顶部的元素
  67. bool queue::top(int *value)
  68. {
  69.     bool result = false;
  70.     if (m_pnext != NULL)
  71.     {
  72.         *value = m_pnext->m_value;
  73.         result = true;
  74.     }
  75.     return result;
  76. }
  77. //判断队列是否为空
  78. bool queue::empty()
  79. {
  80.     bool result = false;
  81.     if (m_pnext == NULL)
  82.     {
  83.         result = true;
  84.     }
  85.     return result;
  86. }
  87. //得到队列大小
  88. int queue::size()
  89. {
  90.     return m_value;
  91. }
  92. //输出队列中的元素
  93. void queue::output()
  94. {
  95.     queue* pnode = this;
  96.     while(pnode->m_pnext != NULL)
  97.     {
  98.         printf(“index=%d\n”, pnode->m_pnext->m_value);
  99.         pnode = pnode->m_pnext;
  100.     }
  101. }
  102. //销毁队列
  103. void queue::destroy()
  104. {
  105.     while(m_pnext != NULL)
  106.     {
  107.         queue* pnode = m_pnext;
  108.         m_pnext = m_pnext->m_pnext;
  109.         delete pnode;
  110.     }
  111. }

主程序测试

 

[cpp][/cpp] 

  1. // myqueue.cpp : Defines the entry point for the console application.
  2. //
  3. #include “stdafx.h”
  4. #include “queue.h”
  5. int _tmain(int argc, _TCHAR* argv[])
  6. {
  7.     queue myqueue;
  8.     for(int i=0; i<10; i++)
  9.     {
  10.         myqueue.push(i * 10);
  11.     }
  12.     myqueue.output();
  13.     printf(“queue size=%d\n”, myqueue.size());
  14.     if (myqueue.empty())
  15.     {
  16.         printf(“queue is empty\n”);
  17.     }
  18.     else
  19.     {
  20.         printf(“queue is not empty\n”);
  21.     }
  22.     myqueue.destroy();
  23.     int value = 0;
  24.     for(int i=0; i<10; i++)
  25.     {
  26.         if (myqueue.pop(&value))
  27.         {
  28.             printf(“pop value=%d successfully\n”, value);
  29.         }
  30.         else
  31.         {
  32.             printf(“pop unsuccessfully\n”);
  33.         }
  34.     }
  35.     printf(“queue size=%d\n”, myqueue.size());
  36.     if (myqueue.empty())
  37.     {
  38.         printf(“queue is empty\n”);
  39.     }
  40.     else
  41.     {
  42.         printf(“queue is not empty\n”);
  43.     }
  44.     getchar();
  45.     return 0;
  46. }

标签