栈队列相关-Aet

Bingliaolong 2024-09-18 21:06 Aet | 隐藏边栏 | 抢沙发 | 4 0

文章评分 1 次，平均分 5.0 ：

栈

概述

栈是一种具有后进先出特性的线性数据结构

数组栈

概述
1. 栈的数组实现是一种简单、静态大小的栈，操作通过数组索引来进行
定义与实现

#include <iostream>

#include <stdexcept>

class ArrStack {

private:

int* data;

int top;

int max_size;

public:

ArrStack(int size) {

data = new int[size];

top = -1;

max_size = size;

}

~ArrStack() {

delete[] data;

}

void push(int value) {

if (is_full()) {

return;

}

data[++top] = value;

}

int pop() {

if(is_empty()) {

throw std::underflow_error("stack underflow");

}

return data[top--];

}

int peek() {

if (is_empty()) {

throw std::underflow_error("stack underflow");

}

return data[top];

}

bool is_empty() const {

return top == -1;

}

bool is_full() const {

return top == max_size - 1;

}

int size() const {

return top + 1;

}

void clear() {

top = -1;

}

};

// 示例用法

int main() {

ArrayStack stack(5); // 创建一个容量为 5 的栈

stack.push(10);

stack.push(20);

stack.push(30);

std::cout << "Top element: " << stack.peek() << std::endl; // 输出 30

stack.pop();

std::cout << "Top element after pop: " << stack.peek() << std::endl; // 输出 20

stack.clear();

std::cout << "Stack is empty: " << stack.isEmpty() << std::endl; // 输出 1 (true)

return 0;

}

链表栈

概述
1. 链表实现栈不受大小限制，能够动态调整大小，是更灵活的实现方式
定义

struct node {

int data;

Node* next;

Node() : data(0), next(nullptr) {}

Node(int value) : data(value), next(nullptr) {}

};

#include <iostream>

#include <stdexcept>

class ListStack {

private:

Node* top;

public:

ListStack() : top(nullptr) {}

~ListStack() {

clear();

}

void clear() {

while(!is_empty()) {

pop();

}

void push(int value) {

Node* node = new Node(value);

node->next = top;

top = node;

}

bool is_empty() const {

return top == nullptr;

}

int pop() {

if (is_empty()) {

throw std::underflow_error("stack underflow");

}

Node* tmp = top;

int value = top->data;

top = top->next;

delete tmp;

return value;

}

int peek() {

if (is_empty()) {

throw std::underflow_error("stack underflow");

}

return top->data;

}

int size() const {

int count = 0;

Node* tmp = top;

while(tmp) {

count++;

tmp = tmp->next;

}

return count;

}

};

// 示例用法

int main() {

LinkedListStack stack; // 创建一个链表实现的栈

stack.push(10);

stack.push(20);

stack.push(30);

std::cout << "Top element: " << stack.peek() << std::endl; // 输出 30

stack.pop();

std::cout << "Top element after pop: " << stack.peek() << std::endl; // 输出 20

stack.clear();

std::cout << "Stack is empty: " << stack.isEmpty() << std::endl; // 输出 1 (true)

return 0;

}

比较

数组栈
1. 适合固定大小的栈
2. 内存连续，效率高，但大小受限
链表栈
1. 适合动态大小的栈
2. 内存分散，但插入和删除操作更灵活

队列

概述

队列（Queue）是一种线性数据结构，遵循先进先出的原则
其中元素在一端插入（队尾），在另一端删除（队头）

数组队列

#include <iostream>

#include <stdexcept>

class ArrQueue {

private:

int* data; // 动态数组指针

int front; // 队头索引

int rear; // 队尾索引

int max_size; // 队列的最大容量

int count; // 当前队列中的元素数量

public:

ArrQueue(int size) {

data = new int[size];

max_size = size;

front = 0;

rear = -1;

count = 0;

}

~ArrQueue() {

delete[] data;

}

void enqueue(int value) {

if (is_full()) {

throw std::overflow_error("queue overflow");

}

rear = (rear + 1) % max_size;

data[rear] = value;

count++;

}

int dequeue() {

if(is_empty()) {

throw std::underflow_error("queue underflow");

}

int value = data[front];

front = (front + 1) % max_size;

count--;

return value;

}

int peek() {

if(is_empty()) {

throw std::underflow_error("queue is empty");

}

return data[front];

}

bool is_empty() const {

return count == 0;

}

bool is_full() const {

return count == max_size;

}

int size() const {

return count;

}

void clear() {

front = 0;

rear = -1;

count = 0;

}

};

// 示例用法

int main() {

ArrayQueue queue(5); // 创建一个容量为 5 的队列

queue.enqueue(10);

queue.enqueue(20);

queue.enqueue(30);

std::cout << "Front element: " << queue.peek() << std::endl; // 输出 10

queue.dequeue();

std::cout << "Front element after dequeue: " << queue.peek() << std::endl; // 输出 20

queue.clear();

std::cout << "Queue is empty: " << queue.isEmpty() << std::endl; // 输出 1 (true)

return 0;

}

链表队列

#include <iostream>

#include <stdexcept>

struct Node {

int data;

Node* next;

Node() : data(0), next(nullptr) {}

Node(int value) : data(value), next(nullptr) {}

};

class ListQueue {

private:

Node* front; // 队头指针

Node* rear; // 队尾指针

int count; // 当前队列中的元素数量

public:

ListQueue() : front(nullptr), rear(nullptr), count(0) {}

~ListQueue() {

clear();

}

void enqueue(int value) {

Node* node = new Node(value);

if(is_empty()) {

front = rear = node;

} else {

rear->next = node;

rear = node;

}

count++;

}

bool is_empty() const {

return front == nullptr;

}

int dequeue() {

if (is_empty()) {

throw std::underflow_error("queue underflow");

}

Node* tmp = front;

int value = front->data;

front = front->next;

delete tmp;

count--;

if (is_empty()) {

rear = nullptr;

}

return value;

}

int peek() {

if(is_empty()) {

throw std::underflow_error("queue is empty");

}

return front->data;

}

int size() const {

return count;

}

void clear() {

while(!is_empty()) {

dequeue();

}

};

// 示例用法

int main() {

LinkedListQueue queue; // 创建一个链表实现的队列

queue.enqueue(10);

queue.enqueue(20);

queue.enqueue(30);

std::cout << "Front element: " << queue.peek() << std::endl; // 输出 10

queue.dequeue();

std::cout << "Front element after dequeue: " << queue.peek() << std::endl; // 输出 20

queue.clear();

std::cout << "Queue is empty: " << queue.isEmpty() << std::endl; // 输出 1 (true)

return 0;

}

栈队列

#include <iostream>

#include <stack>

#include <stdexcept>

class StackQueue {

private:

std::stack<int> stack1;

std::stack<int> stack2;

public:

viod enqueue(int value) {

stack1.push(value);

}

void dequeue() {

if (is_empty()) {

throw std::underflow_error("queue underflow");

}

if (stack2.empty()) {

while(!stack1.empty()) {

stack2.push(stack.top());

stack1.pop();

}

int front = stack2.top();

stack2.pop();

return front;

}

int front() {

if (is_empty()) {

throw std::underflow_error("queue empty");

}

if (stack2.empty()) {

while(!stack1.empty()) {

stack2.push(stack1.top());

stack1.pop();

}

return stack2.top();

}

bool is_empty() const {

return stack1.empty() && stack2.empty();

}

};

比较

数组队列
1. 适合固定大小的队列，操作简单，但受大小限制
链表队列
1. 灵活大小，适合需要动态调整的情况，插入和删除操作更高效

其他总结

underflow_error

C++ 标准库中定义的一种异常类型，用于指示数值或操作下溢的错误
或者在某些数据结构操作中表明操作无法进行，因为数据结构为空（例如栈或队列的出队、出栈操作）
它继承自 std::runtime_error，是 C++ 标准异常处理机制的一部分

overflow_error

C++ 标准库中定义的一种异常类型，用于指示数值溢出或其他操作超出合理范围的错误
继承自 std::runtime_error，用于报告由于超出限制而发生的错误

int safeAdd(int a, int b) {

// 检测是否会发生整数溢出

if ((b > 0) && (a > std::numeric_limits<int>::max() - b)) {

throw std::overflow_error("Overflow error: Integer addition exceeds maximum limit.");

}

if ((b < 0) && (a < std::numeric_limits<int>::min() - b)) {

throw std::overflow_error("Overflow error: Integer addition exceeds minimum limit.");

}

return a + b;

}

栈
概述
数组栈
链表栈
比较
队列
概述
数组队列
链表队列
栈队列
比较
其他总结
underflow_error
overflow_error

本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！

Bingliaolong 关注：0 粉丝：0 最后编辑于：2024-12-31

Everything will be better.

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

栈

概述

数组栈

链表栈

比较

队列

概述

数组队列

链表队列

栈队列

比较

其他总结

underflow_error

overflow_error

你可能也喜欢

热评文章

发表评论

标签云集