数据结构的包装整理

daiyulong2024 · 2025-08-07 21:02:49 · 个人记录

:::align{center}

栈（stack)

:::

代码

:::info[note]{open} 底层使用数组实现，非常快。所有函数的时间复杂度为 O(1)。 :::

#include<bits/stdc++.h>
using namespace std;

template<typename T,int SIZE> 
class Stack {
    private:
        T stk[SIZE+5];
        int idx;
    public:
        Stack():idx(0){}
        bool empty() const {
            return !idx;
        }
        bool full() const {
            return idx==SIZE;
        }
        int size() const {
            return idx;
        } 
        T top() const {
            if(empty()) {
                throw out_of_range("Stack is empty.");
            }
            return stk[idx];
        }
        void push(T x) {
            if(full()) {
                throw out_of_range("Stack is full.");
            }
            stk[++idx]=x;
        } 
        void pop() {
            idx--;
        }
        void clear() {
            idx=0;
        }
}; 

使用说明

Stack<typename,SIZE> stk;

其中 typename 为任意数据类型，SIZE 为栈的最大大小（通常根据题目设定）。

::cute-table

:::align{center}

队列（queue)

:::

代码

:::info[note]{open} 底层使用循环队列，数组实现，非常快。所有函数的时间复杂度为 O(1)。 :::

#include<bits/stdc++.h>
using namespace std;

template<typename T,int SIZE>
class Queue {
    private:
        T q[SIZE+5];
        int front,back,cnt;
    public:
        Queue():front(0),back(0),cnt(0){}
        void push(T value) {
            if(full()) {
                throw overflow_error("Queue is full.");
            }
            q[back]=value;
            back=(back+1)%SIZE;
            cnt++;
        }
        void push() {
            if(empty()) {
                throw underflow_error("Queue is empty.");
            }
            front=(front+1)%SIZE;
            cnt--;
        }
        T front() const {
            if (empty()) {
                throw underflow_error("Queue is empty");
            }
            return q[front];
        }
        bool empty() const {
            return cnt==0;
        }
        bool full() const {
            return cnt==SIZE;
        }
        int size() const {
            return cnt;
        }
        void clear() {
            front=back=cnt=0;
        }
};

使用说明

Queue<typename,SIZE> q;

其中 typename 为任意数据类型，SIZE 为栈的最大大小（通常根据题目设定）。

::cute-table