• 【C语言实现简单的数据结构】栈和队列

    【C语言实现简单的数据结构】栈和队列

    心有所向，日复一日，必有精进

    文章目录

    前言

    顺序表链表到这里告一段落，在实现栈和队列的时候虽然在逻辑上和顺序变链表不同，但物理结构我们可以使用顺序变或者链表来实现。但是根据结构的逻辑不同，可以根据各自优缺来选择，所以请学好顺序表链表，接下来进入栈和队列。

    ---

    栈

    1. 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守**后进先出LIFO（Last In First Out）**的原则。
    2. 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
    3. 出栈：栈的删除操作叫做出栈。出数据也在栈顶。
      在这里插入图片描述
      栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
      在这里插入图片描述

    栈的接口

    //栈的初始化
void StackInit(Stack*ps);
//销毁
void StackDestroy(Stack* ps);
//入栈
void StackPush(Stack* ps,STData x);
//出栈
void StackPop(Stack* ps);

//取栈顶元素
STData StackTop(Stack* ps);
//销毁
bool StackEmpty(Stack* ps);
//栈的长度
int StackSize(Stack* ps);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    栈的具体实现

    //结构
typedef int STData;
typedef struct STACK{
	STData* arr;
	int top;
	int capacity;
}Stack;
//初始化
void StackInit(Stack* ps){
	assert(ps);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}
//销毁
void StackDestroy(Stack*ps){
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}
//出栈
void StackPush(Stack*ps,STData x){
	assert(ps);
	if (ps->top == ps->capacity){
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STData* tmp = (STData*)realloc(ps->arr, newcapacity*sizeof(Stack*));
		if (tmp == NULL){
			perror("realloc fail");
			exit(-1);
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
		ps->arr[ps->top] = x;
		ps->top++;		
}
//出栈
void StackPop(Stack* ps){
	assert(ps);
	assert(!StackEmpty(ps));
	--ps->top;
}
//取栈顶元素
STData StackTop(Stack*ps){
	assert(ps);
	return ps->arr[(ps->top)-1];
}
//判断是否为空
bool StackEmpty(Stack*ps){
	assert(ps);
	return ps->top == 0;
}
//栈的长度
int StackSize(Stack* ps)
{
	assert(ps);

	return ps->top;
}

    • 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
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59

    队列

    队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)

    1. 入队列：进行插入操作的一端称为队尾
    2. 出队列：进行删除操作的一端称为队头
      在这里插入图片描述
      队列就好比生活中的排队，队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

    循环队列

    在这里插入图片描述

    环形队列可以使用数组实现，也可以使用循环链表实现。
    循环队列，重要的是队列的停止，循环队列用数组实现比较好，在下面练习题中会实现循环队列；

    队列接口

    typedef int QTData;
typedef struct QNode
{
	QTData data;
	struct QNode*next;
}QNode;
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;
//队列初始化
void QueueInit(Queue* phead);
//销毁
void QueueDestroy(Queue* phead);
//入队
void QueuePush(Queue* phead ,int x);
//出队
void QueuePop(Queue* phead);
//队头元素
QTData QueueFront(Queue* phead);
//队尾元素
QTData QueueBack(Queue* phead);
//判空
bool QueueEmpty(Queue* phead);
//队列长度
int QueueSize(Queue* phead);

    • 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

    队列具体实现

    void QueueInit(Queue* phead){
	phead->head = phead->tail = NULL;
	phead->size = 0;
}
void QueueDestroy(Queue* phead){
	QNode*cur = phead->head;
	while (cur){
		Queue*next = cur->next;
		free(cur);
		cur = next;
	}
}
void QueuePush(Queue* phead, int x){
	QNode*newnode = (QNode*)malloc(sizeof(QNode));
	newnode->data = x;
	newnode->next = NULL;
	if (phead->head == NULL){
		phead->head = phead->tail = newnode; 
	}
	else{
		phead->tail->next = newnode;
		phead->tail = newnode;
	}
	phead->size++;
}
void QueuePop(Queue* phead){
	Queue*cur =phead->head;
	phead->head = phead->head->next;
	free(cur);
	cur = NULL; 
	phead->size--;
}
QTData QueueFront(Queue* phead){

	return phead->head->data;
}
QTData QueueBack(Queue* phead){
	return phead->tail->data;
}
bool QueueEmpty(Queue* phead){
	return  phead->head == NULL;
}
int QueueSize(Queue* phead){
	return phead->size;
}

    • 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
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    栈和队列练习题

    1、括号匹配

    思路： 遇到左括号入栈，利用先进后出的的性质，遇到右括号出栈匹配，发现是一对括号，就可以匹配成功。

    在这里插入图片描述

    比较简单直接上代码

    题目：有效的括号

    typedef char  STData;
typedef struct STACK{
	STData* arr;
	int top;
	int capacity;
}Stack;
bool StackEmpty(Stack*ps);
void StackInit(Stack* ps){
	assert(ps);
	ps->arr = NULL;
	ps->top = 0;
    ps->capacity = 0;
}
void StackDestroy(Stack*ps){
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}
void StackPush(Stack*ps,STData x){
	assert(ps);
	if (ps->top == ps->capacity){
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STData* tmp = (STData*)realloc(ps->arr, newcapacity*sizeof(Stack*));
		if (tmp == NULL){
			perror("realloc fail");
			exit(-1);
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
		ps->arr[ps->top] = x;
		ps->top++;		
}
void StackPop(Stack* ps){
	assert(ps);
	assert(!StackEmpty(ps));
	--ps->top;
}
STData StackTop(Stack*ps){
	assert(ps);
	return ps->arr[(ps->top)-1];
}
bool StackEmpty(Stack*ps){
	assert(ps);
	return ps->top == 0;

}
int StackSize(Stack* ps)
{
	assert(ps);

	return ps->top;
}
bool isValid(char * s){
Stack sl;
StackInit(&sl);

while(*s){
    if(*s=='('||*s=='['||*s=='{'){
        StackPush(&sl,*s);
    }else{
    if(StackEmpty(&sl)){StackDestroy(&sl); return false;}
    char top = StackTop(&sl);
    StackPop(&sl);
     if((*s==')'&&top!='(')
        ||(*s=='}'&&top!='{')
        ||(*s==']'&&top!='[')){
            StackDestroy(&sl);
            return false;
        }
    }
++s;   
}
bool falg = StackEmpty(&sl);
StackDestroy(&sl);
return falg;
}

    • 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
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78

    在c语言中，我们只能先自己实现一个栈，然后实现，在c++或java中实现较为简单。

    2、实现循环队列

    实现队列有一个关键问题：循环队列真正的问题是如何判空和判满？
    back指向队尾元素的下一个的时候，无法判断队列为空还是为满！

    back直接指向队尾元素讷？
    这样很烦讷，不信你试试？

    在这里插入图片描述

    循环队列，在为空和满的时候back所指向的和front所指向的相同，如何解决？
    增加一个空间，在队列为满时候，总会剩下一个空间

    那么实现循环队列是用数组还是链表？

    前面队列使用的是链表结构，在链表也存在循环链表，是不是适合实现循环队列呢？
    但实际上二者都可以，

    （灵幻拷问）但是链表有一个操作如何取队尾元素？
    如果是单链表那有点难讷，还是选数组吧；

    在这里插入图片描述
    back的next是front，为满，

    两种为满的情况：

    在这里插入图片描述

    （很巧妙，非常巧妙，简直是米老鼠进了妙妙屋吃妙脆角）

    bool myCircularQueueIsFull(MyCircularQueue* obj) {
  return ((obj->Back)+1)%(obj->N)==obj->Front;
}

    • 1
    • 2
    • 3

    back==front，为空

    bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
	return obj->Front==obj->Back;
}

    • 1
    • 2
    • 3

    返回队尾元素，这种方式还是喵~

    int myCircularQueueRear(MyCircularQueue* obj) {
if(obj->Front==obj->Back){
        return -1;
    }
    return obj->arr[(obj->Back-1+(obj->N))%(obj->N)];
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    题目：设计实现循环队列

    typedef struct {
    int *arr;
    int Front;
    int Back;
    int N;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
       MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
       int*a = (int*)malloc(sizeof(int)*(k+1));
       obj->arr= a;
       obj->Front = 0;
       obj->Back = 0;
       obj->N = k+1;
       return obj;                 
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(((obj->Back)+1)%(obj->N)==obj->Front){
        return false;
    }
    if(obj->Back==(obj->N)-1){
        obj->arr[obj->Back] = value; 
         (obj->Back)  = ((obj->Back)+1)%(obj->N) ;
    }else{
      obj->arr[obj->Back] = value; 
    (obj->Back)++;   

    }
    // obj->arr[obj->Back] = value;
    // obj->Back++;
    //  (obj->Back)  %= obj->N;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(obj->Front==obj->Back){
        return false;
    }
if(obj->Front==(obj->N)-1){
    (obj->Front)  = ((obj->Front)+1)%(obj->N) ;
}else{
    obj->Front++;
}
return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(obj->Front==obj->Back){
        return -1;
    }
return obj->arr[obj->Front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
if(obj->Front==obj->Back){
        return -1;
    }
    return obj->arr[(obj->Back-1+(obj->N))%(obj->N)];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->Front==obj->Back;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
  return ((obj->Back)+1)%(obj->N)==obj->Front;
}

void myCircularQueueFree(MyCircularQueue* obj) {

    free(obj->arr);
    obj->arr==NULL;
    obj->Front = 0;
    obj->Back = 0;
    obj->N = 0;
    free(obj);
}

    • 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
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
  • 相关阅读:
    【Latex】模板设置及使用教程
    装配式施工在建筑装修中的应用研究
    大数据-玩转数据-Python Sftp Mysql 数据
    AR手势识别交互，让应用更加“得心应手”
    LeetCode_54_螺旋矩阵
    MongoDB 6.1 及以上版本使用配置文件的方式启动报错 Unrecognized option: storage.journal.enabled
    一种基于金鹰优化和灰狼优化的混合算法
    Nacos配置文件管理、微服务获取Nacos配置文件
    [Err] 1093 - You can‘t specify target table ‘*****‘ for update in FROM clause
    【移动端网页特效】02-移动端轮播图（原生JS）
  • 原文地址：https://blog.csdn.net/m0_62824408/article/details/126216133