顺序栈

  • 预先分配一块连续的内存用于存放栈中的元素,并设栈顶指针top 指示栈顶元素;
  • 初始值 top = -1
  • 入栈/出栈后,top++ / top--
  • top == -1时,为空栈;
  • top == MAX_SIZE-1时,栈溢出,需要内存扩容

栈声明:

#define DEFAULT_CAPACITY 10 

template <class T>
class MyStack
{
public:
    MyStack(int capacity = DEFAULT_CAPACITY);           // 构造函数
    MyStack(const MyStack<T>& other);                   // 复制构造函数
    ~MyStack();                                         // 析构函数
    MyStack<T>& operator=(const MyStack<T>& other);     // 赋值运算
    T& top() const;                                     // 返回栈顶元素
    bool empty() const;                                 // const修饰表明只读取数据成员
    int size() const;                                   // 返回元素个数
    void push(const T& item);                           // 压栈
    void pop();                                         // 出栈
    void emplace(const T& item);                        // 玄学压栈,不作实现
    void swap(MyStack& other);                          // 交换

private:
    T* stack;           // 栈容器
    int capacity;       // 当前容量
    int topIndex;       // 栈顶索引
    void expand();      // 容量扩充
};

栈实现:

template<class T>
inline MyStack<T>::MyStack(int _capacity) : capacity(_capacity)
{
    if (capacity <= 0) throw "stack capacity must be >0";
    stack = new T[capacity];
    topIndex = -1;
}

template<class T>
inline MyStack<T>::MyStack(const MyStack<T>& other)
{
    *this = other;
}

template<class T>
inline MyStack<T>::~MyStack()
{
    delete[] stack;
    stack = nullptr;
}

template<class T>
inline MyStack<T>& MyStack<T>::operator=(const MyStack<T>& other)
{
    delete[] stack;
    topIndex = other.topIndex;
    capacity = other.size();
    stack = new T[capacity];
    std::copy(other.stack, other.stack + other.size(), stack);
    return *this;
}

template<class T>
inline bool MyStack<T>::empty() const
{
    return -1 == topIndex;
}

template<class T>
inline int MyStack<T>::size() const
{
    return topIndex + 1;
}

template<class T>
inline T& MyStack<T>::top() const
{
    if (empty()) throw "ERROR: Stack is empty";
    return stack[topIndex];
}

template<class T>
inline void MyStack<T>::push(const T& item)
{
    if (topIndex == capacity - 1)
        expand();
    stack[++topIndex] = item;
}

template<class T>
inline void MyStack<T>::pop()
{
    if (empty()) throw "Stack is empty. Delete failed.";
    stack[topIndex--].~T();  // 指针递减,成员析构
}

template<class T>
inline void MyStack<T>::emplace(const T& item)
{
    push(item);
}

template<class T>
inline void MyStack<T>::swap(MyStack& other)
{
    MyStack<T> temp(other);
    other = *this;
    *this = temp;
}

template<class T>
inline void MyStack<T>::expand()
{
    capacity *= 2;
    T* temp = new T[capacity];
    std::copy(stack, stack + this->size(), temp);
    delete[] stack;
    stack = temp;
}

顺序队列

  • 预先分配一块连续的存储单元存放队列中的元素,并设队头指针front 指示队头元素、队尾指针rear指示队尾元素的下一个位置;
  • 初始值 front = rear = 0
  • 入队/出队后,rear++ / front++
  • front == rear时,队列为空;
  • rear==MAX_SIZE时,队列已满(假溢出),需要内存扩容,但此时可能存在内存闲置。

循环队列

循环队列是一种改进的顺序队列结构,操作表现同样基于 FIFO(先进先出)原则,但队尾被连接在队首之后形成一个循环,也被称为“环形缓冲器”。
优点是能够允许利用之前释放的空间,解决“假溢出”问题。

  • 为了更好地判断循环队列的队空和队满边界,需要牺牲 最后一个 存储单元
  • 预先分配一块连续的存储单元存放队列中的元素,并设队头指针front 指示队头元素、队尾指针rear指示队尾元素的下一个位置;
  • 初始值 front = rear = 0
  • 入队包括回绕入队rear = (rear+1) % MAX_SIZE
  • 出队包括回绕出队 front = (front+1) % MAX_SIZE
  • front == rear时,队列为空;
  • (rear+1) % MAX_SIZE == front时,队列溢出,需要内存扩容
/********************************************************* * Data Structures in C++ * @file MyQueue.h * @author QCH * @date 2020/03/19 * @brief 顺序队列的实现,注意回绕的处理方式,空出队头位置 * Copyright (c) 2016-2020. All rights reserved. *********************************************************/

#pragma once

#define DEFAULT_CAPACITY 10 

template<class T>
class MyQueue
{
public:
    MyQueue(int _capacity = DEFAULT_CAPACITY);
    MyQueue(const MyQueue<T>& other);
    ~MyQueue();
    MyQueue<T>& operator=(const MyQueue<T>& other);
    T& front();
    T& back();
    bool empty();
    int size();
    void push(const T& item);
    void pop();
    void emplace(const T& item);
    void swap(const MyQueue<T>& other);

private:
    T* queue;           // 队列容器
    int counter;        // 计数
    int capacity;       // 容量
    int frontIndex;     // 前项索引
    int backIndex;      // 后项索引
    void expand();      // 容量扩充
};

/********************************************************************* * 由于编译器只能通过include“看到”头文件而找不到模板实现代码 * 为避免产生链接问题, 模板类的声明和定义必须放在一起 *********************************************************************/

template<class T>
inline MyQueue<T>::MyQueue(int _capacity) : capacity(_capacity)
{
    if (capacity <= 0) throw "Capacity must be >0";
    queue = new T[capacity];
    frontIndex = backIndex = counter = 0;
}

template<class T>
inline MyQueue<T>::MyQueue(const MyQueue<T>& other)
{
    *this = other;
}

template<class T>
inline MyQueue<T>::~MyQueue()
{
    delete[] queue;
    queue = nullptr;
}

template<class T>
inline MyQueue<T>& MyQueue<T>::operator=(const MyQueue<T>& other)
{
    delete[] queue;
    capacity = other.capacity;
    queue = new T[capacity];
    std::copy(other.queue, other.queue + capacity, queue);
    frontIndex = other.frontIndex;
    backIndex = other.backIndex;
    counter = other.counter;
    return *this;
}

template<class T>
inline T& MyQueue<T>::front()
{
    if (empty()) throw "ERROR: Queue is empty!";
    return queue[(frontIndex + 1) % capacity];
}

template<class T>
inline T& MyQueue<T>::back()
{
    if (empty()) throw "ERROR: Queue is empty!";
    return queue[backIndex];
}

template<class T>
inline bool MyQueue<T>::empty()
{
    return frontIndex == backIndex;
}

template<class T>
inline int MyQueue<T>::size()
{
    return counter;
}

template<class T>
inline void MyQueue<T>::push(const T& item)
{
    if ((backIndex + 1) % capacity == frontIndex) // 队列满了
    {
        expand();
        frontIndex = 0;
        backIndex = capacity - 1;
        capacity *= 2;
    }

    //if (backIndex == capacity - 1)
    // backIndex = 0; 
    //else
    // backIndex++;
    backIndex = (backIndex + 1) % capacity;     // 回绕的高水平写法
    queue[backIndex] = item;
    counter++;
}

template<class T>
inline void MyQueue<T>::pop()
{
    if (empty()) throw "ERROR: Queue is empty!";
    frontIndex = (frontIndex + 1) % capacity;    // 回绕的高水平写法
    queue[frontIndex].~T();
    counter--;
}

template<class T>
inline void MyQueue<T>::emplace(const T& item)
{
    push(item);
}

template<class T>
inline void MyQueue<T>::swap(const MyQueue<T>& other)
{
    MyQueue<T> temp(other);
    other = *this;
    *this = temp;
}

template<class T>
inline void MyQueue<T>::expand()
{
    T* temp = new T[capacity * 2];
    if (frontIndex < backIndex)
        std::copy(queue, queue + capacity, temp);
    else
    {
        std::copy(queue + frontIndex, queue + capacity, temp);
        std::copy(queue, queue + frontIndex, temp + capacity - frontIndex);
    }
    delete[] queue;
    queue = temp;
}

模板类

由于编译器只能通过include <看到> 头文件而找不到模板实现代码。为避免产生链接问题,模板类的声明和定义必须放在一起。例如上述循环队列模板类的声明和定义。