The solution to Implement a circular buffer of size N

额，拖了好久，都没时间做~一开始想成用数组实现没有看清楚题目啊。

链表操作就是要画出来，写的时候细心点，特别是注意之前的变量有没有改变，要加个临时变量来存。

链表易于插入，删除。数组是随机访问。把两者结合起来用就更好。

  1 #include <iostream>
  2 #include <string>
  3 
  4 using namespace std;
  5 
  6 typedef unsigned int UINT;
  7 typedef struct SingleNode
  8 {
  9     SingleNode():next(NULL){}
 10     string data;
 11     SingleNode * next;
 12 }SingleNode;
 13 
 14 class CircularBuffer
 15 {
 16 public:
 17     CircularBuffer(UINT size):m_nBufferSize(size),m_nCurrentSize(0)
 18     {
 19         m_pHead = new SingleNode();
 20         m_pTail = m_pHead;
 21     }
 22     ~CircularBuffer(){ Release();}
 23 public:
 24     bool Append(UINT num);
 25     bool Remove(UINT num);
 26     bool List();
 27 private:
 28     bool IsFull();
 29     bool IsEmpty();
 30     bool Release();
 31 private:
 32     UINT m_nBufferSize;
 33     UINT m_nCurrentSize;
 34     SingleNode * m_pHead;
 35     SingleNode * m_pTail;
 36 };
 37 //
 38 bool CircularBuffer::IsFull()
 39 {
 40     return m_nCurrentSize >= m_nBufferSize;
 41 }
 42 bool CircularBuffer::IsEmpty()
 43 {
 44     return !m_nCurrentSize;
 45 }
 46 bool CircularBuffer::Release()
 47 {
 48     if(NULL == m_pHead || NULL == m_pHead->next)
 49         return true;
 50     SingleNode * currentNode = m_pHead->next, *tempNode = NULL;
 51     while(m_pHead != currentNode)
 52     {
 53         tempNode = currentNode->next;
 54         delete currentNode;
 55         currentNode = tempNode;
 56     }
 57     return true;
 58 }
 59 bool CircularBuffer::Append(UINT num)
 60 {
 61     for(int i = 0; i < num; i++)
 62     {
 63         SingleNode * newNode = new SingleNode();
 64         cin >> newNode->data;
 65         m_pTail->next = newNode;
 66         m_pTail       = newNode;
 67         m_pTail->next = m_pHead;
 68         if(IsFull())
 69         {
 70             SingleNode * tempNode = m_pHead->next;
 71             m_pHead->next = tempNode->next;
 72             delete tempNode;
 73         }
 74         else m_nCurrentSize ++;
 75     }
 76     return true;
 77 }
 78 bool CircularBuffer::Remove(UINT num)
 79 {
 80     SingleNode * tempNode;
 81     for(int i = 0; i < num; i++)
 82     {
 83         tempNode = m_pHead->next;
 84         if(m_pHead == tempNode) break;
 85         m_pHead->next = tempNode->next;
 86         delete tempNode;
 87         m_nCurrentSize --;
 88     }
 89     if(IsEmpty())
 90     {
 91         m_pHead->next = NULL;
 92         m_pTail = m_pHead;
 93     }
 94     return true;
 95 }
 96 bool CircularBuffer::List()
 97 {
 98     if(NULL == m_pHead || NULL == m_pHead->next)
 99         return true;
100     SingleNode * tempNode = m_pHead->next;
101     while(m_pHead != tempNode)
102     {
103         cout << tempNode->data << endl;
104         tempNode = tempNode->next;
105     }
106     return true;
107 }
108 void parseCmd(CircularBuffer&cb)
109 {
110     char cmd;
111     UINT pram;
112     while(cin >> cmd)
113     {
114         switch(cmd)
115         {
116         case 'A':
117             cin >> pram;
118             cb.Append(pram);
119             break;
120         case 'R':
121             cin >> pram;
122             cb.Remove(pram);
123             break;
124         case 'L':
125             cb.List();
126             break;
127         case 'Q':
128             return;
129         default:break;
130         }
131     }    
132 }
133 int main()
134 {
135     UINT size;
136     while(cin >> size)
137     {
138         CircularBuffer cb(size);
139         parseCmd(cb);
140     }
141     return 0;
142 }

秒客网

The solution to Implement a circular buffer of size N

相关文章