用C/C++实现栈和队列的封装

2023-07-23 03:24| 来源: 网络整理| 查看: 265

一、熟悉栈的概念以及特性它是一种运算符受限的线性表，因为栈顶是可以操作的一端，栈底不可操作！push压入，top弹出栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针像水桶呈东西一样，先进后出，后进先出二、数据结构中栈与程序中栈有什么不同？数据结构的栈：管理数据的一种手段或者是方法！可以用来存放数据和地址;内存中的栈：是确切存在的物理结构，是用来存放不同数据的内存空间；由系统自动分配和释放的，由高地址向低地址扩展的数据机构，是一段连续的内存区域，是对数据结构栈这种手段的实现！

一般来说：栈存放的是常量，栈中分配局部变量空间

三、实现栈的以下接口：

文章目录一、熟悉栈的概念以及特性二、数据结构中栈与程序中栈有什么不同？三、实现栈的以下接口：0.包含结构体和头文件1. 初始化栈2.入栈3.出栈4. 获取栈顶元素5.获取栈中有效元素个数6. 检测栈是否为空7.销毁栈8.测试使用 C++ 类封装栈四、熟悉队列的概念以及特性五、熟悉循环队列，并分析循环队列如何判断队列满六、实现队列的以下基本操作0.包含头文件和结构体1.初始化队列2.队尾入队列3.队头出队列4.获取队列头部元素5.获取队列队尾元素6.获取队列中有效元素个数7.检测队列是否为空8.销毁队列9.测试队列七、总结栈和队列的区别面试题精选：https://blog.csdn.net/qq_43763344/article/details/89388332

0.包含结构体和头文件 #include #include #include typedef int SDataType; typedef struct Stack { SDataType* _array; int _capacity; int _top; // 标记栈顶位置 }Stack; 1. 初始化栈

void StackInit(Stack* ps);

void StackInit(Stack* ps) { assert(ps); ps->_capacity = 10; ps->_top = 0; ps->_array = (SDataType*)malloc(sizeof(SDataType)*ps->_capacity); } 2.入栈

void StackPush(Stack* ps, SDataType data);

void StackPush(Stack* ps, SDataType data) { assert(ps); ps->_array[ps->_top++] = data; } 3.出栈

void StackPop(Stack* ps);

void StackPop(Stack* ps) { assert(ps); ps->_array[ps->_top--]; } 4. 获取栈顶元素

SDataType StackTop(Stack* ps);

SDataType StackTop(Stack* ps) { SDataType a = ps->_array[ps->_top-1]; return a; } 5.获取栈中有效元素个数

int StackSize(Stack* ps);

int StackSize(Stack* ps) { assert(ps); int count = 0; for (int i = 0; i _top; ++i) { ++count; } return count; } 6. 检测栈是否为空

如果为空返回非零结果，如果不为空返回0 int StackEmpty(Stack* ps);

int StackEmpty(Stack* ps) { assert(ps); if (ps->_top == 0) { return 1; } else{return 0;} } 7.销毁栈

void StackDestroy(Stack* ps);

void StackDestroy(Stack* ps) { assert(ps); if (ps->_array == NULL){return;} ps->_capacity = 0; ps->_top = 0; free(ps->_array); ps->_array = NULL; ps = NULL; } 8.测试 void print(Stack *ps) { assert(ps); for (int i = 0; i _top; ++i) { printf("%d ", ps->_array[i]); } printf("\n"); } void Test() { Stack s; StackInit(&s); //压栈 StackPush(&s, 1); StackPush(&s, 2); StackPush(&s, 3); StackPush(&s, 4); StackPush(&s, 5); StackPush(&s, 6); StackPush(&s, 7); StackPush(&s, 8); print(&s); if (StackEmpty(&s) == 0) { printf("不为空!"); } else { printf("为空！"); } printf("\n"); StackPop(&s);// 出栈 //StackPop(&s); //StackPop(&s); //StackPop(&s); print(&s); //获取栈顶元素 printf("%d\n", StackTop(&s)); //获取栈中有效元素个数 printf("%d\n", StackSize(&s)); // 销毁栈 StackDestroy(&s); // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 if (StackEmpty(&s) == 0) { printf("不为空!"); } else { printf("为空！"); } } 使用 C++ 类封装栈 #pragma once #include #include using namespace std; class Stack { public: Stack() { _array = new int; _capacity = 10; _top = 0; } void StackPush(int data) { _array[_top++] = data; } void StackPop() { --_top; } int StackTop() { static int top = _array[_top]; return top; } int StackSize() { return _top; } bool StackEmpty() { if (_top == 0) { return true; } return false; } ~Stack() { _capacity = 0; _top = 0; if (_array == nullptr) { return; } else { _array = nullptr; delete _array; } } private: int* _array; int _capacity; int _top; }; 四、熟悉队列的概念以及特性

一种特殊的线性表--------只允许在队头删除，队尾插入，受限制的线性表

五、熟悉循环队列，并分析循环队列如何判断队列满

顺序队列结构必须要静态或动态分配一块连续的内存空间，设置两个指针管理，一个指针指向队头，一个指向队尾

顺序队列溢出现象：

下溢：当队列为空时，做出队运算溢出的现象，常用作程序控制转移的条件，属于正常现象真上溢:当队列满时，队列无法进行插入–作进栈运算产生的空间溢出现象,要避免这种现象假上溢：由于入队和出队操作中，头指针只增不减，导致被删除的空间无法利用，当队列实际个数远远小于向量空间规模时，也可能由于尾指针已经超越向量空间的上界而不能做入队操作–

循环队列作用：为了使已经删除的队列空间重复使用方法是：无论插入或者删除操作，一旦两个指针超出了所分配的队列空间,就让他指向这片连续空间的起始位置

判断循环队列满的方法：

另设一个布尔变量少用一个元素空间，当入队时看尾指针是否等于头指针，如果相等则队满用一个计数器记录队列中元素的总数，只要队列元素等于向量空间就是队列已满六、实现队列的以下基本操作 0.包含头文件和结构体 // 链式结构：表示队列 typedef struct QListNode{ struct QListNode* _pNext; int _data; } QNode; // 队列的结构 typedef struct Queue{ QNode* _front; QNode* _rear; } Queue; 1.初始化队列

void QueueInit(Queue* q);

void QueueInit(Queue* q){ q->_front = q->_rear = NULL; } 2.队尾入队列

void QueuePush(Queue* q, QDataType data);

void QueuePush(Queue* q, int data){ QNode* node = (QNode*)malloc(sizeof(QNode)); node->_data = data; node->_pNext = NULL; if (q->_front == NULL){ q->_front = node; q->_rear = node; }else{ q->_rear->_pNext = node; q->_rear = node; } } 3.队头出队列

void QueuePop(Queue* q);

void QueuePop(Queue* q){ QNode* second = q->_front->_pNext; free(q->_front); q->_front = second; //更新尾指针 if (q->_front == NULL){ q->_rear = NULL; } } 4.获取队列头部元素

QDataType QueueFront(Queue* q);

int QueueFront(Queue* q){ if (q->_front == NULL){ return 0; } return q->_front->_data; } 5.获取队列队尾元素

QDataType QueueBack(Queue* q);

int QueueBack(Queue* q){ if (q->_rear == NULL){ return 0; } return q->_rear->_data; } 6.获取队列中有效元素个数

int QueueSize(Queue* q);

int QueueSize(Queue* q){ if (q->_front == NULL || q->_rear == NULL){ return 0; } int size = 0; for (QNode* cur = q->_front; cur != NULL; cur = cur->_pNext){ ++size; } return size; } 7.检测队列是否为空

如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* q);

int QueueEmpty(Queue* q){ if (q->_front == NULL){ return 1; } else { return 0; } } 8.销毁队列

void QueueDestroy(Queue* q);

void QueueDestroy(Queue* q){ QNode* cur = q->_front; QNode* next; for (; cur != NULL; cur = next){ next = cur->_pNext; free(cur); } q->_front = q->_rear = NULL; } 9.测试队列 void print1(Queue *m ,int num){ QNode* cur = m->_front; for (; cur!=NULL;cur = cur->_pNext){ printf("%d ", cur->_data); } printf("\n"); } void Test1() { Queue m; QueueInit(&m); QueuePush(&m, 1); QueuePush(&m, 2); QueuePush(&m, 3); QueuePush(&m, 4); QueuePush(&m, 5); QueuePush(&m, 6); int num = QueueSize(&m); printf("队列里共有%d个元素\n", num); printf("分别是："); print1(&m,num); QueuePop(&m); print1(&m, num); printf("%d\n",QueueFront(&m)); printf("%d\n", QueueBack(&m)); if (QueueEmpty(&m)) { printf("队列是空的!\n"); } else { printf("不为空!\n"); } QueueDestroy(&m); if (QueueEmpty(&m)) { printf("队列是空的!\n"); } else { printf("不为空！\n"); } } 七、总结栈和队列的区别队列是先进先出，栈是先进后出；队列只能在表的后端插入，在前端删除；而栈是只能在一端进行插入删除；遍历数据的速度不同，由于栈只能在一端取出数据，如果是最先放入的就要遍历整个栈，另外在遍历数据的时候还要开辟临时空间，保持数据在遍历前的一致性；队列是基于地址指针进行遍历，而且可以从头部或者尾部遍历，但不能同时遍历，不需要开辟临时空间。

相同点：操作受限的线性表

面试题精选：https://blog.csdn.net/qq_43763344/article/details/89388332

【本文地址】

公司简介

联系我们