栈的物理实现有 顺序队列 和 链式队列

一、顺序队列

用向量存储队列元素，用两个变量分别指向队列的前端(front)和尾端(rear)

  • 关键是如何防止假溢出

队列假溢出

  1. 队列溢出

    • 上溢
    • 下溢
    • 假溢出：当 rear = mSize-1 时，再作插入运算就会产生溢出，如果这时队列的前端还有许多空位置，这种现象称为假溢出

  2. 循环队列

    • 为了解决假溢出的问题，需要采用循环队列的方式： % mSize
    • 另外一个问题就是如何区分空队列还是满队列？空一个队列空间，空队列状态时，令 front = rear，若 (rear + 1) % mSize == front，我们认为此时队列已满，但实际上 rear 指向的空间并没有被利用

  3. 循环队列类定义

template <class T>
class arrQueue: public Queue<T> { 
private: 
    int mSize; // 存放队列的数组的大小
    int front; // 表示队头所在位置的下标
    int rear; // 表示待入队元素所在位置的下标
    T *qu; // 存放类型为T的队列元素的数组
public: // 队列的运算集
    arrQueue(int size) { // 创建队列的实例
        mSize = size + 1; // 浪费一个存储空间，以区别队列空和队列满
        qu = new T[mSize];
        front = rear = 0;
    }
    ~arrQueue() { // 消除该实例，并释放其空间
        delete[] qu;
    }
}

// 入队操作
template<class T>
bool arrQueue<T> :: enQueue(const T item) { 
    // item入队，插入队尾
    if (((rear + 1 ) % mSize) == front) {
        cout << "队列已满，溢出" << endl;
        return false;
    }
    qu[rear] = item;
    rear = (rear + 1) % mSize; // 循环后继
    return true;
}

// 出队操作
bool arrQueue<T> :: deQueue(T& item) { 
    // 返回队头元素并从队列中删除
    if ( front == rear) {
        cout << "队列为空" << endl;
        return false;
    }
    item = qu[front];
    front = (front + 1) % mSize; // 这里并没有真的删除队列空间的元素，而是把头指针循环后移
    return true;
}

二、链式队列

  1. 用单链表方式存储，队列中每个元素对于链表中的一个结点

    • 单链表队列
    • 链接指针的方向是从队列的前端向尾端链接

    链式队列

  2. 链式队列类定义

template <class T>
class lnkQueue: public Queue<T> {
private:
    int size; // 队列中当前元素的个数
    Link<T>* front; // 表示队头的指针
    Link<T>* rear; // 表示队尾的指针
public: // 队列的运算集
    lnkQueue(int size); // 创建队列的实例
    ~lnkQueue(); // 消除该实例，并释放其空间
}

// 入队操作
template <class T>
bool enQueue(const T item) { // item入队，插入队尾
    if (rear == nullptr) { // 空队列
        front = rear = new Link<T>(item, nullptr);
    }
    else { // 添加新的元素
        rear->next = new Link<T>(item, nullptr); 
        rear = rear->next; // 向后移动尾指针
    }
    size++; // 队列大小加一
    return true;
}

// 出队操作
template <class T>
bool deQueue(T* item) { // 返回队头元素并从队列中删除
    Link<T>* tmp;
    if (size == 0) { // 队列为空，没有元素可出队
        cout << "队列为空" << endl;
        return false;
    }
    *item = front->data;
    tmp = front;
    front = front->next;  // 向后移动头指针
    delete tmp; // 删除原来的头结点空间
    if (front == nullptr)
        rear = nullptr;
    size--;
    return true;
}

三、顺序队列与链式队列的比较

  • 顺序队列有固定的存储空间
  • 链式队列可以满足大小无法估计的情况
  • 它们都不允许访问队列内部的元素