返回顶部

收藏

c++用List实现Stack和Queue

更多

数据结构

test.cpp

#include <iostream>
#include "list.hpp"
#include "stack.hpp"
#include "queue.hpp"

int main(void)
{
  //test list
  List<int> l;

  l.push_front(1);
  l.push_front(2);
  l.push_front(3);
  l.push_back(4);
  l.print_list();

  List<int> l2;
  l2.push_front(4);
  l2.push_front(5);
  l2.push_back(6);
  l2.print_list();

  l2 = l;
  l2.print_list();  
  List<int>::const_iterator a,b;
  if (a == b)
    std::cout << "We are equal!\n";

  //test stack
  Stack<int> s;
  Stack<int> s2;

  s.push(5);
  s.push(4);
  try
    {
      std::cout << s.top() << std::endl;
      s.pop();
      std::cout << s.top() << std::endl;

      s2 = s;
      std::cout << s2.top() << std::endl;
      s2.pop();
      std::cout << s2.top() << std::endl;
    }
  catch(const char *line)
    {
      std::cout << line << std::endl;
    }

  //test queue
  Queue<int> q;
  try
    {
      q.inqueue(1);
      q.inqueue(2);
      std::cout << q.top() << std::endl;
      q.dequeue();
      std::cout << q.top() << std::endl;
      q.inqueue(3);

      q.dequeue();
      std::cout << q.top() << std::endl;

      q.inqueue(4);
      q.inqueue(5);
      q.inqueue(6);

      Queue<int> q2;
      q2 = q;

      std::cout << q2.top() << std::endl;
      q2.dequeue();
      std::cout << q2.top() << std::endl;
      q2.dequeue();
      std::cout << q2.top() << std::endl;

    }
  catch (const char *error)
    {
      std::cout << error << std::endl;
    }
  return 0;
}

来自《数据结构与算法分析》,做了小修改

#ifndef ALGORITHM_LIST_H
#define ALGORITHM_LIST_H

#include <iostream>

template <class T>
class List
{
private:
  struct Node
  {
    T data;
    Node *prev;
    Node *next;
    Node():data(T()),prev(NULL),next(NULL){}; 
  };
public:
  // class iterator
  // {

  // };
  class const_iterator
  {
  public:
    const_iterator() : current(NULL){}
    const T & operator*() const
    {
      return retrieve();
    }

    const_iterator & operator++()
    {
      current = current->next;
      return *this;
    }

    const_iterator operator++(int)
    {
      const_iterator old = (*this);
      ++(*this);

      return old;
    }

    bool operator==(const const_iterator & rhs) const
    {
      return current == rhs.current;
    }

    bool operator!=(const const_iterator &rhs) const
    {
      return !(*this == rhs);
    }

  private:
    Node * current;
    T & retrieve() const
    {
      return current->data;
    }
    const_iterator(Node *p):current(p){}

    friend class List<T>;
  };

  List()
  {
    init();
  }

  List(const List *rhs)
  {
    init();
    *this = rhs;
  }

  void print_list()
  {
    Node *node = head->next;

    while (node != tail)
      {
    std::cout << node->data << std::endl;
    node = node->next;
      }
  }

  void push_front(const T &t)
  {
    Node *node = new Node;

    node->data = t;
    node->next = head->next;
    node->prev = head;
    head->next->prev = node;
    head->next = node;
    count++;
  }

  void push_back(const T &t)
  {
    Node *node = new Node;

    node->data = t;
    node->next = tail;
    node->prev = tail->prev;
    tail->prev->next = node;
    tail->prev = node;
    count++;
  }

  void pop_front()
  {
    if (empty())
      throw "Empty List!";
    Node *node = head->next;
    head->next = node->next;
    node->next->prev = head;
    count--;

    delete node;
  }

  const_iterator  begin() const
  {
    return const_iterator(head->next);
  }

  const_iterator end() const
  {
    return const_iterator(tail);
  }

  void pop_back()
  {
    if (empty())
      throw "Empty List!";
    Node node = tail->prev;
    tail->prev = node->prev;
    node->prev->next = tail;
    count--;

    delete node;
  }

  const List & operator=(const List &rhs)
  {
    if (this == &rhs)
      return *this;
    clear();

    for (const_iterator itr = rhs.begin(); !(itr == rhs.end()); ++itr)
      push_back(*itr);

    return *this;
  }

  int size() const
  {
    return count;
  }

  bool empty()
  {
    return size() == 0;
  }

  void clear()
  {
    while (!empty())
      pop_front();
  }

  virtual ~List()
  {
    clear();
    delete head;
    delete tail;
  }

private:

  int count;
  Node *head;
  Node *tail;
  void init()
  {
    count = 0;
    head = new Node;
    tail = new Node;
    head->next = tail;
    head->prev = NULL;
    tail->prev = head;
    tail->next = NULL;
  }

};

#endif

stack.hpp

#ifndef ALGORITHM_STACK_H
#define ALGORITHM_STACK_H
#include "list.hpp"

template <class T>
class Stack
{
public:
  Stack()
  {
    list = new List<T>;
  }
  ~Stack()
  {
    delete list;
  }
  void push(const T & t)
  {
    list->push_front(t);
  }

  void pop()
  {
    list->pop_front();
  }

  T top()
  {
    list->top();
  }

  bool empty()
  {
    return list->empty();
  }

  const Stack & operator=(const Stack & stack)
  {
    if (!list->empty())
      list->clear();
    *list = *(stack.list);

    return *this;
  }

private:
  List<T> *list;
};

#endif

queue.hpp

#ifndef ALGORITHM_QUEUE_H
#define ALGORITHM_QUEUE_H
#include "list.hpp"

template <class T>
class Queue
{
public:
  Queue()
  {
    list = new List<T>;
  }
  ~Queue()
  {
    delete list;
  }
  void inqueue(const T & t)
  {
    list->push_back(t);
  }

  void dequeue()
  {
    list->pop_front();
  }

  T top()
  {
    list->top();
  }

  bool empty()
  {
    return list->empty();
  }

  const Queue & operator=(const Queue & queue)
  {
    if (!list->empty())
      list->clear();
    *list = *(queue.list);

    return *this;
  }

private:
  List<T> *list;
};

#endif

标签:c++,数据结构,队列,堆栈

收藏

0人收藏

支持

0

反对

0

发表评论