将把元素添加到栈顶的操作叫作“入栈”删除栈顶元素的操作叫作“出栈”。只能在栈顶添加或删除元素,因此栈可以视为一种受限制的数组或链表基于链表实现栈的示例:/* 基于链表实现的栈 */typedef struct {ListNode* top; // 将头节点作为栈顶int size; // 栈的长度} LinkedListStack;/* 构造函数 */LinkedListStack* newLinkedListStack() {LinkedListStack* s malloc(sizeof(LinkedListStack));s-top NULL;s-size 0;return s;}/* 析构函数 */void delLinkedListStack(LinkedListStack* s) {while (s-top) {ListNode* n s-top-next;free(s-top);s-top n;}free(s);}/* 获取栈的长度 */int size(LinkedListStack* s) {return s-size;}/* 判断栈是否为空 */bool isEmpty(LinkedListStack* s) {return size(s) 0;}/* 入栈 */void push(LinkedListStack* s, int num) {ListNode* node (ListNode*)malloc(sizeof(ListNode));node-next s-top; // 更新新加节点指针域node-val num; // 更新新加节点数据域s-top node; // 更新栈顶s-size; // 更新栈大小}/* 访问栈顶元素 */int peek(LinkedListStack* s) {if (s-size 0) {printf(栈为空\n);return INT_MAX;}return s-top-val;}/* 出栈 */int pop(LinkedListStack* s) {int val peek(s);ListNode* tmp s-top;s-top s-top-next;// 释放内存free(tmp);s-size--;return val;}基于数组的实现使用数组实现栈时我们可以将数组的尾部作为栈顶。/* 基于数组实现的栈 */typedef struct {int* data;int size;} ArrayStack;/* 构造函数 */ArrayStack* newArrayStack() {ArrayStack* stack malloc(sizeof(ArrayStack));// 初始化一个大容量避免扩容stack-data malloc(sizeof(int) * MAX_SIZE);stack-size 0;return stack;}/* 析构函数 */void delArrayStack(ArrayStack* stack) {free(stack-data);free(stack);}/* 获取栈的长度 */int size(ArrayStack* stack) {return stack-size;}/* 判断栈是否为空 */bool isEmpty(ArrayStack* stack) {return stack-size 0;}/* 入栈 */void push(ArrayStack* stack, int num) {if (stack-size MAX_SIZE) {printf(栈已满\n);return;}stack-data[stack-size] num;stack-size;}/* 访问栈顶元素 */int peek(ArrayStack* stack) {if (stack-size 0) {printf(栈为空\n);return INT_MAX;}return stack-data[stack-size - 1];}/* 出栈 */int pop(ArrayStack* stack) {int val peek(stack);stack-size--;return val;}时间效率基于数组实现的栈在触发扩容时效率会降低但由于扩容是低频操作因此平均效率更高。基于链表实现的栈可以提供更加稳定的效率表现。空间效率在初始化列表时系统会为列表分配“初始容量”该容量可能超出实际需求并且扩容机制通常是按照特定倍率例如 2 倍进行扩容的扩容后的容量也可能超出实际需求。因此基于数组实现的栈可能造成一定的空间浪费。/* 基于环形数组实现的队列 */class ArrayQueue {private:int* nums; // 用于存储队列元素的数组int front; // 队首指针指向队首元素int queSize; // 队列长度int queCapacity; // 队列容量public:ArrayQueue(int capacity) {// 初始化数组nums new int[capacity];queCapacity capacity;front queSize 0;}~ArrayQueue() {delete[] nums;}/* 获取队列的容量 */int capacity() {return queCapacity;}/* 获取队列的长度 */int size() {return queSize;}/* 判断队列是否为空 */bool isEmpty() {return size() 0;}/* 入队 */void push(int num) {if (queSize queCapacity) {cout 队列已满 endl;return;}// 计算队尾指针指向队尾索引 1// 通过取余操作实现 rear 越过数组尾部后回到头部int rear (front queSize) % queCapacity;// 将 num 添加至队尾nums[rear] num;queSize;}/* 出队 */int pop() {int num peek();// 队首指针向后移动一位若越过尾部则返回到数组头部front (front 1) % queCapacity;queSize--;return num;}/* 访问队首元素 */int peek() {if (isEmpty())throw out_of_range(队列为空);return nums[front];}/* 将数组转化为 Vector 并返回 */vectorint toVector() {// 仅转换有效长度范围内的列表元素vectorint arr(queSize);for (int i 0, j front; i queSize; i, j) {arr[i] nums[j % queCapacity];}return arr;}};双向队列/* 初始化双向队列 */dequeint deque;/* 元素入队 */deque.push_back(2); // 添加至队尾deque.push_back(5);deque.push_back(4);deque.push_front(3); // 添加至队首deque.push_front(1);/* 访问元素 */int front deque.front(); // 队首元素int back deque.back(); // 队尾元素/* 元素出队 */deque.pop_front(); // 队首元素出队deque.pop_back(); // 队尾元素出队/* 获取双向队列的长度 */int size deque.size();/* 判断双向队列是否为空 */bool empty deque.empty();双向队列实现 *¶双向队列的实现与队列类似可以选择链表或数组作为底层数据结构。基于链表实现双向队列的入队出队操作/* 双向链表节点 */struct DoublyListNode {int val; // 节点值DoublyListNode* next; // 后继节点指针DoublyListNode* prev; // 前驱节点指针DoublyListNode(int val) : val(val), prev(nullptr), next(nullptr) {}};/* 基于双向链表实现的双向队列 */class LinkedListDeque {private:DoublyListNode* front, * rear; // 头节点 front 尾节点 rearint queSize 0; // 双向队列的长度public:/* 构造方法 */LinkedListDeque() : front(nullptr), rear(nullptr) {}/* 析构方法 */~LinkedListDeque() {// 遍历链表删除节点释放内存DoublyListNode* pre, * cur front;while (cur ! nullptr) {pre cur;cur cur-next;delete pre;}}/* 获取双向队列的长度 */int size() {return queSize;}/* 判断双向队列是否为空 */bool isEmpty() {return size() 0;}/* 入队操作 */void push(int num, bool isFront) {DoublyListNode* node new DoublyListNode(num);// 若链表为空则令 front 和 rear 都指向 nodeif (isEmpty())front rear node;// 队首入队操作else if (isFront) {// 将 node 添加至链表头部front-prev node;node-next front;front node; // 更新头节点// 队尾入队操作}else {// 将 node 添加至链表尾部rear-next node;node-prev rear;rear node; // 更新尾节点}queSize; // 更新队列长度}/* 队首入队 */void pushFirst(int num) {push(num, true);}/* 队尾入队 */void pushLast(int num) {push(num, false);}/* 出队操作 */int pop(bool isFront) {if (isEmpty())throw out_of_range(队列为空);int val;// 队列长度为 1 时, 头尾指向同一节点if (queSize 1) {val front-val;delete front; // 指向同一节点释放其一即可front nullptr;rear nullptr;}// 队首出队操作else if (isFront) {val front-val; // 暂存头节点值// 删除头节点DoublyListNode* fNext front-next;fNext-prev nullptr;front-next nullptr;delete front;front fNext; // 更新头节点// 队尾出队操作}else {val rear-val; // 暂存尾节点值// 删除尾节点DoublyListNode* rPrev rear-prev;rPrev-next nullptr;rear-prev nullptr;delete rear;rear rPrev; // 更新尾节点}queSize--; // 更新队列长度return val;}/* 队首出队 */int popFirst() {return pop(true);}/* 队尾出队 */int popLast() {return pop(false);}/* 访问队首元素 */int peekFirst() {if (isEmpty())throw out_of_range(双向队列为空);return front-val;}/* 访问队尾元素 */int peekLast() {if (isEmpty())throw out_of_range(双向队列为空);return rear-val;}/* 返回数组用于打印 */vectorint toVector() {DoublyListNode* node front;vectorint res(size());for (int i 0; i res.size(); i) {res[i] node-val;node node-next;}return res;}};基于数组实现双向队列出入对操作/* 基于环形数组实现的双向队列 */class ArrayDeque {private:vectorint nums; // 用于存储双向队列元素的数组int front; // 队首指针指向队首元素int queSize; // 双向队列长度public:/* 构造方法 */ArrayDeque(int capacity) {nums.resize(capacity);front queSize 0;}/* 获取双向队列的容量 */int capacity() {return nums.size();}/* 获取双向队列的长度 */int size() {return queSize;}/* 判断双向队列是否为空 */bool isEmpty() {return queSize 0;}/* 计算环形数组索引 */int index(int i) {// 通过取余操作实现数组首尾相连// 当 i 越过数组尾部后回到头部// 当 i 越过数组头部后回到尾部return (i capacity()) % capacity();}/* 队首入队 */void pushFirst(int num) {if (queSize capacity()) {cout 双向队列已满 endl;return;}// 队首指针向左移动一位// 通过取余操作实现 front 越过数组头部后回到尾部front index(front - 1);// 将 num 添加至队首nums[front] num;queSize;}/* 队尾入队 */void pushLast(int num) {if (queSize capacity()) {cout 双向队列已满 endl;return;}// 计算队尾指针指向队尾索引 1int rear index(front queSize);// 将 num 添加至队尾nums[rear] num;queSize;}/* 队首出队 */int popFirst() {int num peekFirst();// 队首指针向后移动一位front index(front 1);queSize--;return num;}/* 队尾出队 */int popLast() {int num peekLast();queSize--;return num;}/* 访问队首元素 */int peekFirst() {if (isEmpty())throw out_of_range(双向队列为空);return nums[front];}/* 访问队尾元素 */int peekLast() {if (isEmpty())throw out_of_range(双向队列为空);// 计算尾元素索引int last index(front queSize - 1);return nums[last];}/* 返回数组用于打印 */vectorint toVector() {// 仅转换有效长度范围内的列表元素vectorint res(queSize);for (int i 0, j front; i queSize; i, j) {res[i] nums[index(j)];}return res;}}; 
长河君 · 2026/11/5 3:53:20 · 阅读 1.2k 栈与队列
将把元素添加到栈顶的操作叫作“入栈”删除栈顶元素的操作叫作“出栈”。只能在栈顶添加或删除元素,因此栈可以视为一种受限制的数组或链表基于链表实现栈的示例:/* 基于链表实现的栈 */typedef struct {ListNode* top; // 将头节点作为栈顶int size; // 栈的长度} LinkedListStack;/* 构造函数 */LinkedListStack* newLinkedListStack() {LinkedListStack* s malloc(sizeof(LinkedListStack));s-top NULL;s-size 0;return s;}/* 析构函数 */void delLinkedListStack(LinkedListStack* s) {while (s-top) {ListNode* n s-top-next;free(s-top);s-top n;}free(s);}/* 获取栈的长度 */int size(LinkedListStack* s) {return s-size;}/* 判断栈是否为空 */bool isEmpty(LinkedListStack* s) {return size(s) 0;}/* 入栈 */void push(LinkedListStack* s, int num) {ListNode* node (ListNode*)malloc(sizeof(ListNode));node-next s-top; // 更新新加节点指针域node-val num; // 更新新加节点数据域s-top node; // 更新栈顶s-size; // 更新栈大小}/* 访问栈顶元素 */int peek(LinkedListStack* s) {if (s-size 0) {printf(栈为空\n);return INT_MAX;}return s-top-val;}/* 出栈 */int pop(LinkedListStack* s) {int val peek(s);ListNode* tmp s-top;s-top s-top-next;// 释放内存free(tmp);s-size--;return val;}基于数组的实现使用数组实现栈时我们可以将数组的尾部作为栈顶。/* 基于数组实现的栈 */typedef struct {int* data;int size;} ArrayStack;/* 构造函数 */ArrayStack* newArrayStack() {ArrayStack* stack malloc(sizeof(ArrayStack));// 初始化一个大容量避免扩容stack-data malloc(sizeof(int) * MAX_SIZE);stack-size 0;return stack;}/* 析构函数 */void delArrayStack(ArrayStack* stack) {free(stack-data);free(stack);}/* 获取栈的长度 */int size(ArrayStack* stack) {return stack-size;}/* 判断栈是否为空 */bool isEmpty(ArrayStack* stack) {return stack-size 0;}/* 入栈 */void push(ArrayStack* stack, int num) {if (stack-size MAX_SIZE) {printf(栈已满\n);return;}stack-data[stack-size] num;stack-size;}/* 访问栈顶元素 */int peek(ArrayStack* stack) {if (stack-size 0) {printf(栈为空\n);return INT_MAX;}return stack-data[stack-size - 1];}/* 出栈 */int pop(ArrayStack* stack) {int val peek(stack);stack-size--;return val;}时间效率基于数组实现的栈在触发扩容时效率会降低但由于扩容是低频操作因此平均效率更高。基于链表实现的栈可以提供更加稳定的效率表现。空间效率在初始化列表时系统会为列表分配“初始容量”该容量可能超出实际需求并且扩容机制通常是按照特定倍率例如 2 倍进行扩容的扩容后的容量也可能超出实际需求。因此基于数组实现的栈可能造成一定的空间浪费。/* 基于环形数组实现的队列 */class ArrayQueue {private:int* nums; // 用于存储队列元素的数组int front; // 队首指针指向队首元素int queSize; // 队列长度int queCapacity; // 队列容量public:ArrayQueue(int capacity) {// 初始化数组nums new int[capacity];queCapacity capacity;front queSize 0;}~ArrayQueue() {delete[] nums;}/* 获取队列的容量 */int capacity() {return queCapacity;}/* 获取队列的长度 */int size() {return queSize;}/* 判断队列是否为空 */bool isEmpty() {return size() 0;}/* 入队 */void push(int num) {if (queSize queCapacity) {cout 队列已满 endl;return;}// 计算队尾指针指向队尾索引 1// 通过取余操作实现 rear 越过数组尾部后回到头部int rear (front queSize) % queCapacity;// 将 num 添加至队尾nums[rear] num;queSize;}/* 出队 */int pop() {int num peek();// 队首指针向后移动一位若越过尾部则返回到数组头部front (front 1) % queCapacity;queSize--;return num;}/* 访问队首元素 */int peek() {if (isEmpty())throw out_of_range(队列为空);return nums[front];}/* 将数组转化为 Vector 并返回 */vectorint toVector() {// 仅转换有效长度范围内的列表元素vectorint arr(queSize);for (int i 0, j front; i queSize; i, j) {arr[i] nums[j % queCapacity];}return arr;}};双向队列/* 初始化双向队列 */dequeint deque;/* 元素入队 */deque.push_back(2); // 添加至队尾deque.push_back(5);deque.push_back(4);deque.push_front(3); // 添加至队首deque.push_front(1);/* 访问元素 */int front deque.front(); // 队首元素int back deque.back(); // 队尾元素/* 元素出队 */deque.pop_front(); // 队首元素出队deque.pop_back(); // 队尾元素出队/* 获取双向队列的长度 */int size deque.size();/* 判断双向队列是否为空 */bool empty deque.empty();双向队列实现 *¶双向队列的实现与队列类似可以选择链表或数组作为底层数据结构。基于链表实现双向队列的入队出队操作/* 双向链表节点 */struct DoublyListNode {int val; // 节点值DoublyListNode* next; // 后继节点指针DoublyListNode* prev; // 前驱节点指针DoublyListNode(int val) : val(val), prev(nullptr), next(nullptr) {}};/* 基于双向链表实现的双向队列 */class LinkedListDeque {private:DoublyListNode* front, * rear; // 头节点 front 尾节点 rearint queSize 0; // 双向队列的长度public:/* 构造方法 */LinkedListDeque() : front(nullptr), rear(nullptr) {}/* 析构方法 */~LinkedListDeque() {// 遍历链表删除节点释放内存DoublyListNode* pre, * cur front;while (cur ! nullptr) {pre cur;cur cur-next;delete pre;}}/* 获取双向队列的长度 */int size() {return queSize;}/* 判断双向队列是否为空 */bool isEmpty() {return size() 0;}/* 入队操作 */void push(int num, bool isFront) {DoublyListNode* node new DoublyListNode(num);// 若链表为空则令 front 和 rear 都指向 nodeif (isEmpty())front rear node;// 队首入队操作else if (isFront) {// 将 node 添加至链表头部front-prev node;node-next front;front node; // 更新头节点// 队尾入队操作}else {// 将 node 添加至链表尾部rear-next node;node-prev rear;rear node; // 更新尾节点}queSize; // 更新队列长度}/* 队首入队 */void pushFirst(int num) {push(num, true);}/* 队尾入队 */void pushLast(int num) {push(num, false);}/* 出队操作 */int pop(bool isFront) {if (isEmpty())throw out_of_range(队列为空);int val;// 队列长度为 1 时, 头尾指向同一节点if (queSize 1) {val front-val;delete front; // 指向同一节点释放其一即可front nullptr;rear nullptr;}// 队首出队操作else if (isFront) {val front-val; // 暂存头节点值// 删除头节点DoublyListNode* fNext front-next;fNext-prev nullptr;front-next nullptr;delete front;front fNext; // 更新头节点// 队尾出队操作}else {val rear-val; // 暂存尾节点值// 删除尾节点DoublyListNode* rPrev rear-prev;rPrev-next nullptr;rear-prev nullptr;delete rear;rear rPrev; // 更新尾节点}queSize--; // 更新队列长度return val;}/* 队首出队 */int popFirst() {return pop(true);}/* 队尾出队 */int popLast() {return pop(false);}/* 访问队首元素 */int peekFirst() {if (isEmpty())throw out_of_range(双向队列为空);return front-val;}/* 访问队尾元素 */int peekLast() {if (isEmpty())throw out_of_range(双向队列为空);return rear-val;}/* 返回数组用于打印 */vectorint toVector() {DoublyListNode* node front;vectorint res(size());for (int i 0; i res.size(); i) {res[i] node-val;node node-next;}return res;}};基于数组实现双向队列出入对操作/* 基于环形数组实现的双向队列 */class ArrayDeque {private:vectorint nums; // 用于存储双向队列元素的数组int front; // 队首指针指向队首元素int queSize; // 双向队列长度public:/* 构造方法 */ArrayDeque(int capacity) {nums.resize(capacity);front queSize 0;}/* 获取双向队列的容量 */int capacity() {return nums.size();}/* 获取双向队列的长度 */int size() {return queSize;}/* 判断双向队列是否为空 */bool isEmpty() {return queSize 0;}/* 计算环形数组索引 */int index(int i) {// 通过取余操作实现数组首尾相连// 当 i 越过数组尾部后回到头部// 当 i 越过数组头部后回到尾部return (i capacity()) % capacity();}/* 队首入队 */void pushFirst(int num) {if (queSize capacity()) {cout 双向队列已满 endl;return;}// 队首指针向左移动一位// 通过取余操作实现 front 越过数组头部后回到尾部front index(front - 1);// 将 num 添加至队首nums[front] num;queSize;}/* 队尾入队 */void pushLast(int num) {if (queSize capacity()) {cout 双向队列已满 endl;return;}// 计算队尾指针指向队尾索引 1int rear index(front queSize);// 将 num 添加至队尾nums[rear] num;queSize;}/* 队首出队 */int popFirst() {int num peekFirst();// 队首指针向后移动一位front index(front 1);queSize--;return num;}/* 队尾出队 */int popLast() {int num peekLast();queSize--;return num;}/* 访问队首元素 */int peekFirst() {if (isEmpty())throw out_of_range(双向队列为空);return nums[front];}/* 访问队尾元素 */int peekLast() {if (isEmpty())throw out_of_range(双向队列为空);// 计算尾元素索引int last index(front queSize - 1);return nums[last];}/* 返回数组用于打印 */vectorint toVector() {// 仅转换有效长度范围内的列表元素vectorint res(queSize);for (int i 0, j front; i queSize; i, j) {res[i] nums[index(j)];}return res;}};