首页 数据结构（C++）

  1. 顺序栈
    1.1 栈的抽象数据类型
    1.2 顺序栈的类定义
    1.3 构造函数
    1.4 析构函数
    1.5 栈溢出处理函数
    1.6 进栈操作
    1.7 出栈操作
    1.8 取栈顶操作

  2. 链式栈
    2.1 链式栈类的定义
    2.2 清空操作
    2.3 进栈操作
    2.4 出栈操作
    2.5 取栈顶操作

  3. 双栈共享一个栈空间
    3.1 进栈操作
    3.2 出栈操作

  4. 顺序队列
    4.1 队列的抽象数据类型
    4.2 顺序队列的类定义
    4.3 入队操作
    4.4 出队操作

  5. 循环队列
    5.1 首尾结合的实现
    5.2 "空"" 满 " 问题的实现
    5.3 判满操作
    5.4 计算元素个数

  6. 链式队列
    6.1 链式队列结点类定义
    6.2 链式队列类定义
    6.3 入队操作
    6.4 出队操作
    6.5 取队头元素操作
    6.6 析构函数

# 一、顺序栈

# 1. 栈的抽象数据类型

// 栈的抽象数据类型
template<class T>
class Stack // 栈的类定义
{
    Stack();    // 构造函数
    virtual void Push(T x)=0;   // 进栈
    virtual bool Pop(T &x)=0;   // 出栈
    virtual bool getTop(T &x)=0;    // 取栈顶
    virtual bool IsEmpty()=0;   // 判栈空
    virtual bool IsFull()=0;    // 判栈满
};

# 2. 顺序栈的类定义

image-20251007201956592
template<class T>
class SeqStack  // 顺序栈类定义
{
    T *elements;    // 栈元素存放数组
    int top;    // 栈顶指针
    int maxSize;    // 栈最大容量
    void overflowProcess(); // 栈的溢出处理
public:
    SeqStack(int sz=50);    // 构造函数
    ~SeqStack();    // 析构函数
    void Push(T x); // 进栈
    bool Pop(T &x); // 出栈
    bool getTop(T &x);  // 取栈顶内容
    bool IsEmpty() const
    {
        return top==-1;
    }
    bool IsFull() const
    {
        return top==maxSize-1;
    }
};

# 3. 构造函数
template<class T>
SeqStack<T>::SeqStack(int sz) : maxSize(sz)// 构造函数
{
    top=-1;
    elements=new T[maxSize];
    assert(elements!=NULL);// 判断是否分配成功
}

# 4. 析构函数
template<class T>
SeqStack<T>::~SeqStack()// 析构函数
{
    delete []elements;
}

# 5. 栈溢出处理函数
template<class T>
void SeqStack<T>::overflowProcess()// 栈溢出处理函数
{
    // 当栈满，则执行扩充栈存储空间处理
    T *newArray=new T[2*maxSize];// 创建更大的存储数组
    for(int i=0;i<=top;++i)
    {
        newArray[i]=elements[i];
    }
    maxSize+=maxSize;
    delete []elements;
    elements=newArray;// 改变 elements 指针
}

# 6. 进栈操作
image-20251007205124199
template<class T>
void SeqStack<T>::Push(T x)// 进栈操作
{
    if(IsFull()==true)// 栈满 -> 扩充
    {
        overflowProcess();
    }
    elements[++top]=x;// 栈顶指针先 + 1，再进栈
}

# 7. 出栈操作
image-20251007211011505
template<class T>
bool SeqStack<T>::Pop(T &x)// 出栈操作
{
    if(IsEmpty()==true)
    {
        return false;
    }
    x=elements[top--];// 栈顶指针 - 1
    return true;// 退栈成功
}

# 8. 取栈顶操作
template<class T>
bool SeqStack<T>::getTop(T &x)// 取栈顶操作
{
    if(IsEmpty()==true)// 若栈不空，则函数返回该栈栈顶元素的地址
    {
        return false;
    }
    x=elements[top];
    return true;
}
​
以上算法时间复杂度均为 O (1)

# 二、链式栈
# 1. 链式栈类的定义
image-20251007211935833
template<class T>
struct StackNode// 栈结点类定义
{
public:
    T data; // 栈结点数据
    StackNode<T> *link; // 结点链指针
    StackNode(T d=0,StackNode<T> *next=NULL) : data(d),link(next){}// 构造函数
};
template<class T>
class LinkedStack// 链式栈类定义
{
private:
    StackNode<T> *top;  // 栈顶指针
    void output(ostream *os,StackNode<T> *ptr,int i);// 递归输出栈的所有元素
public:
    LinkedStack() : top(NULL){} // 构造函数
    ~LinkedStack()  // 析构函数
    {
        makeEmpty();
    }
    void Push(T x);// 进栈
    bool Pop(T &x);// 出栈
    bool getTop(T &x) const;// 取栈顶
    bool IsEmpty() const
    {
        return top==NULL;
    }
    void makeEmpty();// 清空栈的内容
    friend osetream &operator<<(ostream &os,LinkedStack<T> &s)// 输出栈元素的重载操作 & lt;<
    {
        output(os,s.top,1);
    }
};

# 2. 清空操作
template<class T>
void LinkedStack<T>::makeEmpty()// 清空操作
{
    StackNode<T> *p;
    while(top!=NULL)
    {
        p=top;
        top=top->link;
        delete p;
    }
}

# 3. 进栈操作
image-20251007215009912
template<class T>
void LinkedStack<T>::Push(T x)// 进栈操作
{
    // 将元素值 x 插入到链式栈的栈顶，即链头
    top=new StackNode<T>(x,top);// 创建新结点
    assert(top!=NULL);// 创建失败退出
}

# 4. 出栈操作
image-20251007222324493
template<class T>
bool LinkedStack<T>::Pop(T &x)// 出栈操作
{
    // 删除栈顶结点，返回被删栈顶元素的值
    if(IsEmpty()==true)
    {
        return false;// 栈空返回
    }
    StackNode<T> *p=top;// 暂存栈顶元素
    top=top->link;// 退栈顶指针
    x=p->data;
    delete p;// 释放结点
    return true;
}

进栈和出栈算法等等时间复杂度均为 O (1)

# 5. 取栈顶操作
image-20251007224054592
template<class T>
bool LinkedStack<T>::getTop(T &x) const
{
    if(IsEmpty()==true)
    {
        return false;// 栈空返回
    }
    x=top->data;    // 返回栈顶元素的值
    return true;
}

# 三、双栈共享一个栈空间
image-20251007230048368
# 1. 进栈操作
// 同一个数组 V [] 来同时存放两个栈
//top0: 栈 0（左栈）的栈顶指针
//top1: 栈 1（右栈）的栈顶指针
bool push(DualStack &DS,Type x,int i)// 向双栈中的第 i 个栈压入元素 x
{
    if(DS.top0+1==DS.top1)// 栈满
    {
        return false;
    }
    if(i==0)// 若要向第 0 个栈压入元素
    {
        DS.top0++;   // 栈顶指针右移一位
        DS.V[DS.top0]=x;    // 新元素放入栈顶
    }
    else// 向第 1 个栈压入元素
    {
        DS.top1--;  // 栈顶指针左移一位
        DS.V[DS.top1]=x;    // 新元素放入栈顶
    }
    return true;// 压栈成功
}

# 2. 出栈操作
bool Pop(DualStack &DS,Type &x,int i)// 向双栈中的第 i 个栈弹出元素，赋值给 x
{
    if(i==0)// 左栈
    {
        if(DS.top0==-1)// 栈空
        {
            return false;
        }    
        x=DS.V[DS.top0];
        DS.top0--;
    }
    else// 右栈
    {
        if(DS.top1==maxsize)// 栈空
        {
            return false;
        }
        x=DS.V[DS.top1];
        DS.top1++;
    }
    return true;
}

# 四、顺序队列
image-20251007233819075 image-20251007234437167
# 1. 队列的抽象数据类型
template<class T>
class Queue
{
public:
    Queue(){}   // 构造函数
    ~Queue(){}  // 析构函数
    virtual bool EnQueue(T x)=0;    // 进队列
    virtual bool DeQueue(T &x)=0;   // 出队列
    virtual bool getFront(T &x)=0;  // 取队头
    virtual bool IsEmpty() const=0; // 判队列空
    virtual bool IsFull() const=0;  // 判队列满
};

# 2. 顺序队列的类定义
image-20251007234521611 image-20251007234536335
template<class T>
class SeqQueue// 队列类定义
{
protected:
    int rear,front; // 队尾与队头指针
    T *elements;    // 队列存放数组
    int maxSize;    // 队列最大容量
public:
    SeqQueue(int sz=10);    // 构造函数
    ~SeqQueue()    // 析构函数
    {
        delete []elements;
    }
    bool EnQueue(const T &x);   // 新元素进队列
    bool DeQueue(T &x); // 退出队头元素
    bool getFront(T &x);    // 取队头元素值
    void makeEmpty()
    {
        front=rear=-1;
    }
    bool IsEmpty() const    // 判队列空
    {
        return front==rear;
    }
    bool IsFull() const     // 判队列满
    {
        return(rear==maxSize-1);
    }
    int getSize() const     // 获取当前元素个数
    {
        return rear-front;
    }
};

# 3. 入队操作
image-20251008000108342
template<class T>
bool SeqQueue<T>::EnQueue(const T &x)// 入队操作
{
    if(rear==maxSize-1) // 队列已满
    {
        cout <<"overflow";
        return false;
    }
    else
    {
        rear++; // 队尾位置指示器后移一个位置
        elements[rear]=x;   // 填入新元素
        return true;
    }
}

# 4. 出队操作
image-20251008000539196
template<class T>
bool SeqQueue<T>::DeQueue(T &x)// 出队操作
{
    if(front==rear) // 队列为空
    {
        cout <<"underflow";
        return false;
    }
    else
    {
        front++;    // 队头置位指示器后移一个位置
        x=elements[front]; // 暂存对头元素
        return true;    // 出列成功
    }
}

入队和出队算法是时间复杂度均为 O (1)

# 五、循环队列
image-20251008001004364 image-20251008001457736 image-20251008001508229
# 1. 首尾结合的实现
# 方法一
// 用条件判断实现首尾结合
if(r==maxSize-1)// 队尾指针到数组最后一个位置
{
	r=0;// 回到数组开头（循环）
}
else
{
    r++;// 没到末尾，正常后移
}

# 方法二
// 把队头、队尾指示器对 maxSize 取模后 + 1
// 注意：为了算法的方便，约定：初始时，队头、队尾指示器均指向最后一个单元位置，
//	   即 front=rear=maxSize-1		或者初始化时 front=rear=0
i=(i+1)%maxSize//i 可以是 front（队头）或 rear（队尾）

# 2.” 空”“满” 问题的实现
image-20251008003105090 image-20251008003512542 image-20251008003309783
# 入队操作
template<class T>
bool SeqQueue<T>::EnQueue(const T &x)// 入队操作
{
    if((rear+1)%maxSize==front) // 判满
    {
        return false;
    }
    else
    {
        rear=(rear+1)%maxSize;  // 队尾指针后移一位
        elements[rear]=x;   // 新元素存储队尾指针指向的位置
        return true;    // 入队成功
    }
}

# 出队操作
image-20251008003907600
template<class T>
bool SeqQueue<T>::DeQueue(T &x)// 出队操作
{
    if(rear==front)// 判空操作
    {
        return false;
    }
    else
    {
        front=(front+1)%maxSize;    // 队头指针后移一位
        x=elements[front];  // 新队头位置的元素赋值给引用参数 x
        return true;    // 出队成功
    }
}

# 3. 判满操作
template<class T>
bool SeqQueue::IsFull() const   // 判满操作
{
    return ((rear+1)%maxSize==front);
}


# 4. 计算元素个数
template<class T>
int SeqQueue::getSize() const   // 计算元素个数
{
    return (rear-front+maxSize)%maxSize;
}


# 六、链式队列
image-20251008121458129
# 1. 链式队列结点类定义
template<class T>
struct QueueNode    // 队列结点类定义
{
public:
    T data; // 队列结点数据
    QueueNode<T> *link; // 结点链指针
    QueueNode(T d=0,QueueNode<T> *next=NULL) : data(d),link(next){}// 构造函数
};

# 2. 链式队列类定义
template<class T>
class LinkedQueue
{
private:
    QueueNode<T> *front,*rear;  // 队头、队尾指针
public:
    LinkedQueue() : rear(NULL),front(NULL) {}   // 构造函数
    ~LinkedQueue(); // 析构函数
    bool EnQueue(const T &x);   // 入队操作
    bool DeQueue(T &x); // 出队操作
    bool GetFront(T &x);
    void MakeEmpty();   // 实现与～Queue () 同
    bool IsEmpty() const    // 判空函数
    {
        return front==NULL;
    }
};

# 3. 入队操作
image-20251008123239297
template<class T>
bool LinkedQueue<T>::EnQueue(const T &x)// 入队操作
{
    // 将新元素 x 插入到队列的队尾
    if(front==NULL)// 队列为空
    {
        front=rear=new QueueNode<T>(x);// 创建第一个结点
        if(front==NULL) // 分配失败
        {
            return false;// 分配失败
        }
    }
    else// 队列不空
    {
        rear->link=new QueueNode<T>(x);// 插入
        if(rear->link==NULL)// 分配失败
        {
            return false;// 分配失败
        }
        rear=rear->link;
    }
    return true;
}

# 4. 出队操作
template<class T>
bool LinkedQueue<T>::DeQueue(T &x)// 出队操作
{
    // 如果队列不空，将队头结点从链式队列中删去
    if(IsEmpty()==true) // 判空
    {
        return false;
    }
    QueueNode<T> *p=front;
    x=front->data;
    front=front->link;
    delete p;
    return true;
}

入队和出队算法的时间复杂度均为 O (1)

# 5. 取队头元素操作
template<class T>
bool LinkedQueue<T>::GetFront(T &x) // 取队头元素操作
{
    // 若队列不空，则函数返回队头元素的值
    if(IsEmpty()==true) // 判空
    {
        return false;
    }
    x=front->data;
    return true;
}


# 6. 析构函数
template<class T>
LinkedQueue<T>::~LinkedQueue()// 析构函数
{
    QueueNode<T> *p;
    while(front!=NULL)// 不空
    {
        p=front;
        front=front->link;
        delete p;
    }
}
   
 更新于