【数据结构】链表实现队列

实现了基本功能

#include <iostream>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
template<class T>
struct Node
{
  T data;
  Node<T> *next_pos;
};

template<class T>
class LinkedQueue
{
public:
  LinkedQueue();
  ~LinkedQueue();
  T getFront();
  T popFront();
  void Push(T x);
  int getLength();
private:
  Node<T> *first, *p, *s, *tail;
};

template<class T>
LinkedQueue<T>::LinkedQueue()//带头结点的队列
{
  s = new Node<T>;
  s->next_pos = NULL;
  first = tail = s;
}

template<class T>
LinkedQueue<T>::~LinkedQueue()
{
  while (first->next_pos)
  {
    p = first->next_pos;
    s = p;
    first->next_pos = p->next_pos;
    delete s;
  }
}

template<class T>
T LinkedQueue<T>::getFront()
{
  p = first->next_pos;
  return p == NULL ? -1 : p->data;
}

template<class T>
T LinkedQueue<T>::popFront()
{
  p = first->next_pos;
  T re = p->data;
  s = p;
  first->next_pos = p->next_pos;
  delete s;
  return re;
}


template<class T>
void LinkedQueue<T>::Push(T x)
{
  s = new Node<T>;
  s->data = x;
  s->next_pos = NULL;
  tail->next_pos = s;
  tail = s;
}

template<class T>
int LinkedQueue<T>::getLength()
{
  p = first->next_pos;
  long long int count = 0;
  while (p != NULL)
  {
    p = p->next_pos; count++;
  }
  return count;
}

int main()
{
  int n = 0;
  cin >> n;
  LinkedQueue<int> que;
  for (int i = 0; i < n; i++)
  {
    int temp = 0;
    cin >> temp;
    que.Push(temp);
  }
  for (int i = 0; i < n; i++)
  {
    cout << que.getFront() << endl;
    que.popFront();
  }
}

 

发表评论

电子邮件地址不会被公开。