棧和隊列及模拟實作

1、棧

棧作為一種資料結構，是一種隻能在一端進行插入和删除操作的特殊線性表。它按照後進先出的原則存儲資料。

先進入的資料被壓入棧底，最後的資料在棧頂；需要讀資料的時候從棧頂開始彈出資料（最後一個資料被第一個讀出來）。

棧具有記憶作用，對棧的插入與删除操作中，不需要改變棧底指針。

結構比較簡單，基本操作如下：

#pragma once
#include<iostream>
using namespace std;
template<class T>
class Stack
{
public:
  Stack()             //構造函數
    :_d(NULL)
    , _size(0)
    , _capacity(0)
  {} 
  ~Stack()             //析構函數
  {
    if (_d)
    {
      delete _d;
      _d = NULL;
    }
  }
public:
  void Push(T d)       //壓棧
  {
    CheckCapacity();
    _d[_size] = d;
    _size++;
  }
  void Pop()          //出棧
  {
    if (Top() != NULL)  //如果棧不為空
    {
      _size--;
    }
  }
  T& Top()            //棧頂元素
  {
    return _d[_size - 1];
  }
  size_t Size()       //傳回棧大小
  {
    return _size;
  }  
  bool Empty()       //判斷是否為空
  {
    return Top() == NULL;
  }

  void Display()
  {
    for (size_t i = 0; i < _size; i++)
    {
      cout << _d[i] << " ";
    }
    cout << endl;
  }
private:
  void CheckCapacity()   //檢查容量
  {
    if (_size == _capacity)
    {
      size_t NewCapacity = _capacity * 2 + 3;
      T *tmp = new T[NewCapacity];
      for (size_t i = 0; i < _size; i++)
      {
        tmp[i] = _d[i];
      }
      delete[] _d;
      _d = tmp;
      _capacity = NewCapacity;
    }
  }
protected:
  T *_d;
  size_t _size;
  size_t _capacity;
};

void test()
{
  Stack<int> s1;
  s1.Push(1);
  s1.Push(2);
  s1.Push(3);
  s1.Push(4);
  s1.Display();

  s1.Pop();
  s1.Display();

  cout << s1.Empty() << endl;
  cout << s1.Size() << endl;
  cout << s1.Top() << endl;
}

int main()
{
  test();
  system("pause");
  return 0;
}      

看運作結果：

這裡，1是棧底，第一個入棧，4是棧頂，彈出時從棧頂開始彈出資料（最後一個資料被第一個讀出來），是以第二次列印為1，2，3

是以有三個元素，棧頂元素為3.

2.隊列

隊列(Queue)：也是運算受限的線性表。是一種先進先出(First In First Out ，簡稱FIFO)的線性表。隻允許在表的一端front進行插入，而在另一端rear進行删除。

隊首(front) ：允許進行删除的一端稱為隊首。

隊尾(rear) ：允許進行插入的一端稱為隊尾。

例如：排隊購物。作業系統中的作業排隊。先進入隊列的成員總是先離開隊列。

基本操作實作如下：

template<class T>
class LinkQueue           //隊列節點
{
public:
  LinkQueue()
    :_d(NULL)
    ,next(NULL)
  {}
  LinkQueue(T& d)
    :_d(d)
    ,next(NULL)
  {}
  ~LinkQueue()
  {}
public:
  T _d;
  LinkQueue *next;
};
template<class T>
class Queue
{
public:
  Queue()
    :_front(NULL)
    , _rear(NULL)
  {}
  void Push(T d)            //尾插
  {
    if (_front == NULL)
    {
      _front = new LinkQueue<T>;    //頭結點
      _front->next= new LinkQueue<T>(d);  //插入d
      _rear = _front->next;
    }
    else
    {
      _rear->next= new LinkQueue<int>(d);
      _rear = _rear->next;
    }
  }
  void Pop()                   //頭删
  {
    assert(_front&&_rear);
    if (_front == _rear)  //隊列為空
    {
      return;
    }
    else
    {
      LinkQueue<int> *tmp = _front->next;
      _front->next = tmp->next;
      delete tmp;
      tmp = NULL;
    }
  }
  size_t Size()                   //隊列節點個數
  {
    assert(this);
    size_t size = 0;
    LinkQueue<int> *tmp = _front->next;
    while (tmp != NULL)
    {
      size++;
      tmp = tmp->next;
    }
    return size;
  }
  bool Empty()              //隊列是否為空
  {
    return _front == _rear;
  }
  T Top()                //隊頭元素
  {
    if (!Empty())
    {
      LinkQueue<int> *tmp = _front->next;
      return tmp->_d;
    }
    return 0;
  }
  ~Queue()
  {
    LinkQueue<int> *tmp = _front->next;
    while (tmp != NULL)
    {
      delete _front;
      _front = tmp;
      tmp = tmp->next;
    }
  }

  void display()
  {
    LinkQueue<int> *tmp = _front->next;
    while (tmp != NULL)
    {
      cout << tmp->_d << " ";
      tmp = tmp->next;
    }
    cout << endl;
  }
private:
  LinkQueue<T> *_front;
  LinkQueue<T> *_rear;
};

void test()
{
  Queue<int> q1;
  q1.Push(1);
  q1.Push(2);
  q1.Push(3);
  q1.Push(4);
  q1.display();

  q1.Pop();
  q1.display();

  cout << q1.Empty() << endl;
  cout << q1.Size() << endl;
  cout << q1.Top() << endl;

}
int main()
{
  test();
  system("pause");
  return 0;
}