• 【数据结构】栈和队列&&OJ练习

    文章目录

    1. 栈

    1.1 栈的概念及其结构

    🐶 栈的定义：

    一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

    🐱 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

    🐭 出栈：栈的删除操作叫做出栈。出数据也在栈顶。

    在这里插入图片描述

    1.2 栈的实现

    💖 栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小

    在这里插入图片描述

    在这里插入图片描述

    Stack.h

    #pragma once
#include
#include
#include
#include
typedef int STDataType;
typedef struct Stak {
	STDataType* a;
	int top;
	int capacity;
}ST;

//初始化栈
void StackInit(ST* ps);

//销毁栈
void StackDestroy(ST* ps);

//元素入栈
void StackPush(ST* ps, STDataType x);

//元素出栈
void StackPop(ST* ps);

//取栈顶元素
STDataType StackTop(ST* ps);

//栈的判空操作
bool StackEmpty(ST* ps);

//返回栈中的元素个数
int StackSize(ST* ps);

    • 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

    Stack.c

    #define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"

//初始化栈
void StackInit(ST* ps)
{
	assert(ps);
	ST* tmp = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (!tmp){
		perror("malloc fail::");
		exit(-1);
	}
	else 
	{
		ps->a = tmp;
		ps->capacity = 4;
		ps->top = 0;
	}
}

//销毁栈
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->capacity = 0;
	ps->top = 0;
}

//元素入栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//考虑是否需要扩容
	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity * 2;
		ST* tmp = realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
		if (!tmp){
			perror("relloc fail::");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top++] = x;
}

//元素出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

//取栈顶元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

//栈的判空操作
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

//返回栈中的元素个数
int StackSize(ST* 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
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77

    Test.c

    #define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void StackTest1()
{
	ST st;
	StackInit(&st);
	printf("入栈：1 2 3 4 5");
	for (int i = 0; i < 5; i++) {
		StackPush(&st, i+1);//压栈
	}
	printf("\n出栈：");
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));//取栈顶元素
		StackPop(&st);
	}
	StackDestroy(&st);
}
int main()
{
	StackTest1();
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    2. 队列

    2.1 队列的概念及其结构

    🐶 队列的定义：

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

    🐱 性质：入队列：进行插入操作的一端称为队尾。出队列：进行删除操作的一端称为队头

    在这里插入图片描述

    2.2 队列的实现

    💖 队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

    在这里插入图片描述

    Queue.h

    #pragma once
#include 
#include 
#include 
#include
typedef int QDataType;
typedef struct QueueNode
{
    QDataType data;
    struct QueueNode* next;
}QNode;
typedef struct Queue {
    QNode* head;
    QNode* tail;
    int size;
}Queue;
//初始化队列
void QueueInit(Queue* pq);

//销毁队列
void QueueDestroy(Queue* pq);

//入队
void QueuePush(Queue* pq, QDataType x);

//出队
void QueuePop(Queue* pq);

//返回队头元素
QDataType QueueFront(Queue* pq);

//返回队尾元素
QDataType QueueBack(Queue* pq);

//队列判空
bool QueueEmpty(Queue* pq);

//队列中元素个数
int QueueSize(Queue* pq);

    • 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

    Queue.c

    #include"Queue.h"

//初始化队列
void QueueInit(Queue* pq)
{
    assert(pq);
    pq->head = pq->tail = NULL;
    pq->size = 0;
}

//销毁队列
void QueueDestroy(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->head;
    while (cur)
    {
        QNode* del = cur;
        cur = cur->next;
        free(del);
    }
    pq->head = pq->tail = NULL;
}

//入队
void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (NULL == newnode)
    {
        exit(-1);
    }
    else
    {
        newnode->data = x;
        newnode->next = NULL;
    }
    if (pq->tail == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
    pq->size++;
}

//出队
void QueuePop(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    if (pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else
    {
        QNode* del = pq->head;
        pq->head = pq->head->next;
        free(del);
        del = NULL;
    }
    pq->size--;
}

//返回队头元素
QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->data;
}

//返回队尾元素
QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->data;
}

//判断队空
bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->head == NULL && pq->tail == NULL;
}

//队列元素个数
int QueueSize(Queue* pq)
{
    return pq->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
    • 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
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98

    Test.c

    #define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void TestQueue()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);
	QueuePush(&q, 6);
	QueuePop(&q);
	QueuePop(&q);
	QueuePop(&q);
	printf("队列中元素个数：%d\n", QueueSize(&q));
	printf("队头元素：%d\n", QueueFront(&q));
	printf("队尾元素：%d\n", QueueBack(&q));
	//打印队列中的元素
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n队列是否为空：");
	int ret = QueueEmpty(&q);
	printf("%d\n", ret);
	QueueDestroy(&q);
}
int main()
{
	TestQueue();
	return 0;
}

    • 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

    3. 栈和队列面试题

    3.1 括号匹配问题

    在这里插入图片描述
    有效的括号

    💖 思路：

    这道题目是一个典型的用栈解决的问题，题目的意思是让我们实现左右括号匹配的问题，我们知道栈的特性是先进后出，大致思路是这样的：

    （1）题目给了我们一个字符串，我们需要遍历这个字符串，当遇到的字符是左括号时，我们就将它入栈，当遇到右括号时，我们先看栈是否为空栈，若为空栈，说明没有与之匹配的左括号。直接销毁栈并且返回false。

    （2）若栈不为空，在进行匹配，如果匹配成功，先s++，并弹出栈顶的元素，然后在进行下一次入栈或者匹配操作；如果匹配失败，则说明整个字符串的括号是不匹配的，直接返回false即可。

    💕 代码实现

    这里我们需要注意的是，由于C语言中没有栈相关的库函数，所以我们需要先把上面实现的栈先拷贝一份拿来用。

    typedef char STDataType;
typedef struct Stak {
	STDataType* a;
	int top;
	int capacity;
}ST;
//初始化栈
void StackInit(ST* ps);
//销毁栈
void StackDestroy(ST* ps);
//元素入栈
void StackPush(ST* ps, STDataType x);
//元素出栈
void StackPop(ST* ps);
//取栈顶元素
STDataType StackTop(ST* ps);
//栈的判空操作
bool StackEmpty(ST* ps);
//返回栈中的元素个数
int StackSize(ST* ps);
//初始化栈
void StackInit(ST* ps)
{
	assert(ps);
	ST* tmp = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (!tmp){
		perror("malloc fail::");
		exit(-1);
	}
	else {
		ps->a = tmp;
		ps->capacity = 4;
		ps->top = 0;
	}
}
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->capacity = 0;
	ps->top = 0;
}
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//考虑是否需要扩容
	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity * 2;
		ST* tmp = realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
		if (!tmp){
			perror("relloc fail::");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top++] = x;
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

bool isValid(char * s){
    ST st;
    StackInit(&st);
    while(*s)
    {
        if(*s=='('||*s=='['||*s=='{'){
            StackPush(&st,*s);
            ++s;
        }
        else
        {
            if(StackEmpty(&st))
            {
                StackDestroy(&st);
                return false;
            }
            char tmp=StackTop(&st);
            if((*s==')'&&tmp=='(')
            ||(*s==']'&&tmp=='[')
            ||(*s=='}'&&tmp=='{')){
                s++;
                StackPop(&st);
            }
            else
            {
                StackDestroy(&st);
                return false;
            }
        }
    }
    if(StackEmpty(&st))
        return true;
    return false;
}

    • 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
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116

    在这里插入图片描述

    3.2 用队列实现栈

    在这里插入图片描述
    用队列实现栈

    💖 思路：

    我们知道队列的性质是先进先出，而栈的性质却是后进先出，那么如何用两个队列来实现栈后进先出的功能呢？这就需要我们利用两个队列来相互导数据了。具体思路如下：

    （1）先定义两个队列并初始化为空队列，始终往一个空队列中入数据，第一次入数据时，由于两个队列都为空，随便选一个入数据即可。

    在这里插入图片描述

    （2）myStackPop——弹出栈顶元素，定义两个指针empty和nonEmpty分别指向空队列和非空队列，将非空队列中的数据一一导入空队列，直到非空队列中剩下一个数据为止。这时非空队列中的那一个元素就相当于栈顶元素，将其返回则可以实现取栈顶元素，将此队列出队则为出栈操作。

    在这里插入图片描述
    （3）由于出栈时，其中一个队列已经置为了空队列，所以下次入栈时直接往另一个不为空的队列中入数据即可；取栈顶的元素即为非空队列中队尾的元素，直接将其返回即可。栈的判空操作即判断两个队列是否全部为空即可。

    💕 代码实现：

    typedef int QDataType;
typedef struct QueueNode
{
    QDataType data;
    struct QueueNode*next;
}QNode;
typedef struct Queue{
    QNode*head;
    QNode*tail;
    int size;
}Queue;

void QueueInit(Queue*pq);
void QueueDestroy(Queue*pq);
void QueuePush(Queue*pq,QDataType x);
void QueuePop(Queue*pq);
QDataType QueueFront(Queue*pq);
QDataType QueueBack(Queue*pq);
bool QueueEmpty(Queue*pq);
QDataType QueueSize(Queue*pq);


void QueueInit(Queue*pq)
{
    assert(pq);
    pq->head = pq->tail =  NULL;
    pq->size = 0;
}
void QueueDestroy(Queue*pq)
{
    assert(pq);
    QNode*cur = pq->head;
    while(cur)
    {
        QNode*del = cur;
        cur = cur->next;
        free(del);
    }
    pq->head = pq->tail = NULL;
}
void QueuePush(Queue*pq,QDataType x)
{
    assert(pq);
    QNode*newnode = (QNode*)malloc(sizeof(QNode));
    if(NULL == newnode)
    {
        exit(-1);
    }
    else
    {
        newnode->data = x;
        newnode->next = NULL;
    }
    if(pq->tail == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
       pq->tail->next = newnode;
       pq->tail = newnode;
    }
    pq->size++;
}
void QueuePop(Queue*pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    if(pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else
    {
        QNode*del = pq->head;
        pq->head = pq->head->next;
        free(del);
        del = NULL;
    }
    pq->size--;
}
QDataType QueueFront(Queue*pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->data;
}
QDataType QueueBack(Queue*pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->data;
}
bool QueueEmpty(Queue*pq)
{
    assert(pq);
    return pq->head == NULL&&pq->tail == NULL;
}
QDataType QueueSize(Queue*pq)
{
    return pq->size;
}

//定义了两个队列，一个为q1和q2
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack*obj = (MyStack*)malloc(sizeof(MyStack));
    if(NULL == obj)
    {
        exit(-1);
    }
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}

void myStackPush(MyStack* obj, int x) {
    //看哪个是否为空
    if(!QueueEmpty(&obj->q1))
    {
        //队列不为空就插入数据
        QueuePush(&obj->q1,x);
    }
    //q2可能为空或不为空
    else
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
    //删除栈顶的元素
    Queue*empty = &obj->q1;
    Queue*nonEmpty = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        empty = &obj->q2;
        nonEmpty = &obj->q1;
    }
    while(QueueSize(nonEmpty)>1)
    {
        //取队头数据存放到空的队列,最后剩下一个，这个就是栈顶的元素
        QueuePush(empty,QueueFront(nonEmpty));
        QueuePop(nonEmpty);
    }
    int top = QueueFront(nonEmpty);
    QueuePop(nonEmpty);
    return top;
}

int myStackTop(MyStack* obj) {
    //取栈的头相当于非空的队列的队尾
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
}

    • 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
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176

    在这里插入图片描述

    3.3 用栈实现队列

    在这里插入图片描述
    用栈实现队列

    💖 思路：

    栈的性质是后进先出，队列的性质是先进先出，我们要使用两个栈来实现队列先进先出的性质，如果将一个栈中的元素导入另一个栈中，是不是另一个栈中的元素出栈时是不是就变成了队列的出队顺序呢？好了，具体思路如下：

    （1）先定义两个空栈，一个栈用来入数据为push栈，另一个栈用来出数据为pop栈。第一次入数据时，将数据全部往push栈中入。

    （2）myQueuePop——返回并移除队头元素，先判断pop栈是否为空，如果不为空，先将pop栈中的栈顶元素保存，然后在移除栈顶元素，最后返回此元素即可；如果pop栈为空，我们需要先将push栈中的元素导入pop栈中，然后在进行刚刚的操作即可。
    在这里插入图片描述

    （3）myQueuePeek——返回队头元素，要返回队头元素，如果pop栈为空，就必须先将push栈中的元素导入pop栈中，然后直接返回pop栈中的栈顶元素即可。否则只需要直接返回栈顶元素即可。

    💖 代码实现：

    typedef int STDataType;
typedef struct Stak {
	STDataType* a;
	int top;
	int capacity;
}ST;
//初始化栈
void StackInit(ST* ps);
//销毁栈
void StackDestroy(ST* ps);
//元素入栈
void StackPush(ST* ps, STDataType x);
//元素出栈
void StackPop(ST* ps);
//取栈顶元素
STDataType StackTop(ST* ps);
//栈的判空操作
bool StackEmpty(ST* ps);
//返回栈中的元素个数
int StackSize(ST* ps);
void StackInit(ST* ps)
{
	assert(ps);
	ST* tmp = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (!tmp){
		perror("malloc fail::");
		exit(-1);
	}
	else {
		ps->a = tmp;
		ps->capacity = 4;
		ps->top = 0;
	}
}

void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->capacity = 0;
	ps->top = 0;
}

void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//考虑是否需要扩容
	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity * 2;
		ST* tmp = realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
		if (!tmp){
			perror("relloc fail::");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top++] = x;
}

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

typedef struct {
    ST pushST;
    ST popST;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&obj->pushST);
    StackInit(&obj->popST);
    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    StackPush(&obj->pushST,x);
}

int myQueuePop(MyQueue* obj) {
    if(StackEmpty(&obj->popST)){
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    int tmp=StackTop(&obj->popST);
    StackPop(&obj->popST);
    return tmp;
}

int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->popST)){
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    return StackTop(&obj->popST);
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->popST)&&StackEmpty(&obj->pushST);
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->popST);
    StackDestroy(&obj->pushST);
    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
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138

    在这里插入图片描述

    3.4 设计循环队列

    这里我们先来介绍一下循环队列：循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。

    在这里插入图片描述

    在这里插入图片描述
    设计循环队列OJ链接

    💖 思路：

    循环队列相对普通队列新增了一个队首的指针front，队尾的指针为tail，即初始化时队列的队首和队尾指向同一个位置。在入队时，队尾的指针不再是向后加一位，而是在向后加一位的基础上还要对队列的长度取余运算。因为当队尾的指针在最后一位时，如果此时队列未满，即表明队列前方还有空余的空间，所以此时队尾需要对队列长度取余回到队列头部空余的位置。

    💕 代码实现：

    typedef struct {
    int *a;
    int front;
    int rear;
    int k;
} MyCircularQueue;

//初始化循环队列
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    obj->front=obj->rear=0;
    obj->k=k;
    return obj;
}
//判断队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj);
    return obj->front==obj->rear;
}
//判断队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj);
    return (obj->rear+1)%(obj->k+1)==obj->front;
}
//循环队列入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    assert(obj);
    if(myCircularQueueIsFull(obj))
        return false;
    obj->a[obj->rear++]=value;
    obj->rear=(obj->rear)%(obj->k+1);
    return true;
}
//循环队列出数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
        return false;
    obj->front++;
    obj->front=obj->front%(obj->k+1);
    return true;
}
//返回队头数据
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->a[obj->front];
}
//返回队尾数据
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->rear==0?obj->a[obj->k]:obj->a[obj->rear-1];
}
//释放队列
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    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

    在这里插入图片描述

  • 相关阅读:
    微服务架构之：Redis的分布式锁---搭建生产可用的Redis分布式锁
    【大数据入门核心技术-Hadoop】Hadoop非高可用集群搭建
    【操作系统】内存的非连续分配管理
    【第二阶段：java基础】第11章：Exception异常（P442-P459）
    torch、(三) Random sampling
    2.3 为何使用Pthreads
    【Vue3】vue3中组合式Api的setup写法快速入门上手起步
    Acwing-反转链表
    python循环的花样玩法（一）
    Azkaban环境配置-尚硅谷大数据培训
  • 原文地址：https://blog.csdn.net/m0_67595314/article/details/127905185