数据结构一栈和队列（1）

一、栈的定义--Stack
栈只允许在末端进行插入和删除的线性表。栈具有后进先出的特性（LIFO，Last In First Out）

栈的应用举例：

1、数制转换例（十进制---》八进制）

 void conversion()

  {
   stack<int> s;
   sacnf("%d",N);
   while(N)
  {
    s.push(N%8);
    N=N/8;
  }
  while(!s.empty())
  {
   int a=0;
   a=s.top();
   s.pop();
   printf("%d",a);
 }

2、括号匹配的检验

设置一个栈，若是左括号压入栈顶，使原来在栈中的未匹配的括号的优先级自然降了一级，若是右括号有两种情况1、刚好与栈顶的左括号匹配。2、或是不合法的情况。

3、行编辑器

行编辑器接受从用户终端输入的程序或数据，并存入数据区，由于在终端上输入时，不能保证不出差错，因此行编辑器设计了一个输入缓冲区这个缓冲区为栈的结构。

4、栈模拟压栈，实现递归转非递归

可以采用与顺序表相同的结构实现它，下面是栈的一些基本实现

 1 template<class T>
 2 class Stack
 3 {
 4 public:
 5     Stack()
 6         :_array(NULL)
 7         ,_capacity(0)
 8         ,_size(0)
 9     {}
10 
11     ~Stack()
12     {
13         if (_array)
14         {
15             delete[] _array;
16         }
17     }
18 
19     Stack<T>& operator=(const Stack<T>& s);
20 
21 public:
22     void Push(const T& x)
23     {
24         _CheckCapacity();
25 
26         _array[_size++] = x;
27     }
28 
29     void Pop()
30     {
31         assert(_size > 0);
32         --_size;
33     }
34 
35     size_t Size()
36     {
37         return _size;
38     }
39 
40     bool Empty()
41     {
42         return  _size == 0;
43     }
44 
45     const T& Top()//返回栈顶元素，不删除
46     {
47         assert(_size > 0);
48 
49         return _array[_size-1];
50     }
51 
52 protected:
53     void _CheckCapacity()//扩容
54     {
55         if (_size >= _capacity)
56         {
57             _capacity = _capacity*2 + 3;
58             T* tmp = new T[_capacity];
59                 for (size_t i = 0; i < _size; ++i)
60                 {
61                     tmp[i] = _array[i]; //operator=
62                 }
63             }
64 
65             delete[] _array;
66             _array = tmp;
67         }
68     }
69 
70 protected:
71     T* _array;
72     size_t _size;
73     size_t _capacity;
74 };

二、队列的定义
队列值允许在表的队尾进行插入，在表对头进行删除。队列具有先进先出的特性。（FIFO，first In First Out）

可以采用链表的结构，下面是队列的一些基本实现

template<class T>
struct QueueNode//链表
{
    T _data;
    QueueNode<T>* _next;

    QueueNode(const T& x)
        :_data(x)
        ,_next(NULL)
    {}
};

template<class T>
class Queue
{
public:    
    Queue()
        :_head(NULL)//指向头和尾的指针
        ,_tail(NULL)
    {}

    ~Queue()
    {}

public:
    void Push(const T& x)
    {
        if (_head == NULL)
        {
            _tail = _head = new QueueNode<T>(x);
        }
        else
        {
            _tail->_next = new QueueNode<T>(x);
            _tail = _tail->_next;
        }
    }

    void Pop()
    {
        assert(_head);
        if (_head == _tail)
        {
            delete _head;
            _tail = _head = NULL;
            return;
        }

        QueueNode<T>* del = _head;
        _head = _head->_next;
        delete del;
    }

    bool Empty()
    {
        return _head == NULL;
    }

    T& Fornt()
    {
        assert(_head);

        return _head->_data;
    }

    T& Back()
    {
        assert(_tail);

        return _tail->_data;
    }

protected:
    QueueNode<T>* _head;//指针
    QueueNode<T>* _tail;
};