WHCSRL 技术网

栈和队列C语言实现附加力推演问题

在这里插入图片描述

栈的概念

1.栈
1.1栈的概念及结构
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端
称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

  • 压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
  • 出栈:栈的删除操作叫做出栈。出数据也在栈顶

在这里插入图片描述

栈的实现

栈的声明

typedef int STData;
typedef struct Stack 
{
	STData *a;
	int capacity;
	int top;
}Stack;

//初始化
void StackInit(Stack *ST);
//栈销毁
void StackDestroy(Stack *ST);
//入栈
void StackPush(Stack *ST, int x);
//弹栈
void StackPop(Stack *ST);
//获取栈顶元素
int StackTop(Stack *ST);
//判断栈是否空
bool StackEmpty(Stack *ST);
//获取栈顶元素个数
int StackSize(Stack *ST);
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

栈的实现

#include"Stack.h"
//初始化
void StackInit(Stack *ST) 
{
	assert(ST);
	ST->a = (STData *)malloc(sizeof(int) * 4);
	ST->capacity = 4;
	ST->top = 0;
}

//栈销毁
void StackDestroy(Stack *ST)
{
	assert(ST);
	free(ST->a);
	ST->a = NULL;
	ST->capacity = ST->top = 0;
}
//入栈
void StackPush(Stack *ST, int x) 
{
	assert(ST);
	if (ST->capacity == ST->top) 
	{
		STData *tmp = realloc(ST->a,sizeof(STData) * ST->capacity * 2);
		if (tmp == NULL) 
		{
			perror("relloc:");
			exit(-1);
		}
		ST->a = tmp;
		ST->capacity = ST->capacity * 2;
	}
	ST->a[ST->top++] = x;
}
//弹栈
void StackPop(Stack *ST) 
{
	assert(ST);
	if(!StackEmpty(ST))
	ST->top--;
}
//获取栈顶元素
int StackTop(Stack *ST) 
{
	assert(ST);
	return ST->a[ST->top - 1];
}
//判断栈是否空
bool StackEmpty(Stack *ST) 
{
	assert(ST);
	return ST->top == 0 ? true : false;
}
//获取栈顶元素个数
int StackSize(Stack *ST) 
{
	assert(ST);
	return ST->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

压栈

在这里插入图片描述

//入栈
void StackPush(Stack *ST, int x) 
{
	assert(ST);
	if (ST->capacity == ST->top) 
	{
		STData *tmp = realloc(ST->a,sizeof(STData) * ST->capacity * 2);
		if (tmp == NULL) 
		{
			perror("relloc:");
			exit(-1);
		}
		ST->a = tmp;
		ST->capacity = ST->capacity * 2;
	}
	ST->a[ST->top++] = x;
}

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

出栈

在这里插入图片描述

//弹栈
void StackPop(Stack *ST) 
{
	assert(ST);
	if(!StackEmpty(ST))
	ST->top--;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

队列

队列声明


typedef int QueDataTypef;

typedef struct QueueNode
{
	struct Queue *next;
	QueDataTypef data;
}QueueNode;

typedef struct Queue 
{
	QueueNode *head;
	QueueNode *tail;
}Queue;


//初始化
void QueueInit(Queue *q);
//销毁
void QueueDestroy(Queue *q);
//队尾入队
void QueuePush(Queue *q, int x);
//队头出队
void QueuePop(Queue *q);
//判断空
bool QueueEmpty(Queue *q);
//获取队头数据
QueDataTypef QueueFront(Queue *q);
//获取队尾数据
QueDataTypef QueueBack(Queue *q);
//求队列的元素个数
int QueueSize(Queue *q);
  • 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

队列实现

#include"Queue.h"

//初始化
void QueueInit(Queue *q) 
{
	assert(q);
	q->head = q->tail = NULL;
}
//销毁
void QueueDestroy(Queue *q) 
{
	QueueNode* cur = q->head;
	
	while (cur) 
	{
		QueueNode *next = (QueueNode *)cur->next;
		free(cur);
		cur = next;
	}
	q->head = q->tail = NULL;
}

//队尾入队
void QueuePush(Queue *q, int x) 
{
	assert(q);
	QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
	if (newNode == NULL)
	{
		exit(-1);
		perror("QueuePush::malloc");
	}
	newNode->data = x;
	newNode->next = NULL;
	
	if (q->tail == NULL) 
	{
		q->head = q->tail = newNode;
	}
	else 
	{
		q->tail->next = (Queue *)newNode;
		q->tail = newNode;
	}
}
//队头出队
void QueuePop(Queue *q) 
{
	assert(q);
	assert(!QueueEmpty(q));
	if (q->head->next == NULL) 
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	else 
	{
		QueueNode *next = (QueueNode *)q->head->next;
		free(q->head);
		q->head = next;
	}
}

//判断空
bool QueueEmpty(Queue *q) 
{
	assert(q);
	return q->head ==  NULL ? true : false;
}
//获取队头数据
QueDataTypef QueueFront(Queue *q) 
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->head->data;
}
//获取队尾数据
QueDataTypef QueueBack(Queue *q) 
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->tail->data;
}

//求队列的元素个数
int QueueSize(Queue *q) 
{
	assert(q);
	int size = 0;
	QueueNode *cur = q->head;
	while (cur) 
	{
		cur = (QueueNode *)cur->next;
		size++;
	}
	return 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

销毁

队列在销毁时,除了释放结点的内存,还要将头结点和尾结点置空

//销毁
void QueueDestroy(Queue *q) 
{
	QueueNode* cur = q->head;
	
	while (cur) 
	{
		QueueNode *next = cur->next;
		free(cur);
		cur = next;
	}
	q->head = q->tail = NULL;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

队尾入队

在这里插入图片描述

如果队头和队尾都是NULL的话,将新结点取下来做队头和队尾,如果队头不是空,就将新的结点尾插到tail的后面,让新结点做新的尾

//队尾入队
void QueuePush(Queue *q, int x) 
{
	assert(q);
	QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
	if (newNode == NULL)
	{
		exit(-1);
		perror("QueuePush::malloc");
	}
	newNode->data = x;
	newNode->next = NULL;
	//队头队尾都是NULL
	if (q->tail == NULL) 
	{
		q->head = q->tail = newNode;
	}
	//取结点尾插入队,新结点成为新的尾
	else 
	{
		q->tail->next = newNode;
		q->tail = newNode;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

队头出队

在这里插入图片描述

出队的时候考虑一种情况如果当只剩下一个结点了,不单独处理的话会让q->tail成为野指针
在这里插入图片描述

//队头出数据
void QueuePop(Queue *q) 
{
	//出队只剩一个结点时,防止tail成为野指针
	if (q->head->next == NULL) 
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	else 
	{
		QueueNode *next = q->head->next;
		free(q->head);
		q->head = next;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

判空

//判断空
bool QueueEmpty(Queue *q) 
{
	assert(q);
	return q->head ==  NULL ? true : false;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

获取队头数据

//获取队头数据
QueDataTypef QueueFront(Queue *q) 
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->head->data;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

获取队尾数据

//获取队尾数据
QueDataTypef QueueBack(Queue *q) 
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->tail->data;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

求元素个数

//求队列的元素个数
int QueueSize(Queue *q) 
{
	assert(q);
	int size = 0;
	QueueNode *cur = q->head;
	while (cur) 
	{
		cur = (QueueNode *)cur->next;
		size++;
	}
	return size;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

力扣题

20. 有效的括号

链接: link.

原题描述:
给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

解题思路:
遍历字符串遇到左括号就入栈,遇到右括号就取出栈中的元素来匹配,如果匹配不上,就返回false,如果匹配上了,就将栈顶元素弹出,直到字符串遍历完了,最后判断栈是否为空

typedef char STData;
typedef struct Stack 
{
	STData *a;
	int capacity;
	int top;
}Stack;
//栈销毁
void StackDestroy(Stack *ST)
{
	assert(ST);
	free(ST->a);
	ST->a = NULL;
	ST->capacity = ST->top = 0;
}
//判断栈是否空
bool StackEmpty(Stack *ST) 
{
	assert(ST);
	return ST->top == 0 ? true : false;
}
//初始化
void StackInit(Stack *ST) 
{
	assert(ST);
	ST->a = (STData *)malloc(sizeof(int) * 4);
	ST->capacity = 4;
	ST->top = 0;
    return;
}
//入栈
void StackPush(Stack *ST, int x) 
{
	assert(ST);
	if (ST->capacity == ST->top) 
	{
		STData *tmp = realloc(ST->a,sizeof(STData) * ST->capacity * 2);
		if (tmp == NULL) 
		{
			perror("relloc:");
			exit(-1);
		}
		ST->a = tmp;
		ST->capacity = ST->capacity * 2;
	}
	ST->a[ST->top++] = x;
}
//弹栈
void StackPop(Stack *ST) 
{
	assert(ST);
	if(!StackEmpty(ST))
	ST->top--;
}
//获取栈顶元素
int StackTop(Stack *ST) 
{
	assert(ST);
	return ST->a[ST->top - 1];
}
bool isValid(char * s){
    if(s == NULL)
    return false;
    Stack ST;
    StackInit(&ST);
    while(*s)
    {
        //左括号入栈
        if(*s == '(' 
        || *s == '{'
        || *s == '[')
        {
            StackPush(&ST,*s);
        }
        else //右括号出栈
        {
            //防止越界,如果上来就是右括号
            if(StackEmpty(&ST))
            {
                StackDestroy(&ST);
                return false;
            }
            char ch = StackTop(&ST);
            if(ch == '(' && *s != ')'
            || ch == '{' && *s != '}'
            || ch == '[' && *s != ']')
            {
                StackDestroy(&ST);
                return false;
            }
            else
            {
                StackPop(&ST);
            }
        }
        s++;
    }
    bool ret = StackEmpty(&ST);
    StackDestroy(&ST);
    return ret;
}
  • 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

225. 用队列实现栈

链接: link.
原题描述:

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。

实现 MyStack 类:

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的,返回 true ;否则,返回 false

实现思路:
用两个队列互相倒入数据,入数据,往不为空的那个队列入,保持另一个队列为空,出数据,不为空的队列前size-1个倒出队列存放到另一个空队列中,队列元素的交换,再输出队尾的数据,这样就实现了后进先出的原则
在这里插入图片描述


typedef int QueDataTypef;

typedef struct QueueNode
{
	struct Queue *next;
	QueDataTypef data;
}QueueNode;

typedef struct Queue 
{
	QueueNode *head;
	QueueNode *tail;
}Queue;
//初始化
void QueueInit(Queue *q);
//销毁
void QueueDestroy(Queue *q);
//队尾入队
void QueuePush(Queue *q, int x);
//队头出队
void QueuePop(Queue *q);
//判断空
bool QueueEmpty(Queue *q);
//获取队头数据
QueDataTypef QueueFront(Queue *q);
//获取队尾数据
QueDataTypef QueueBack(Queue *q);
//求队列的元素个数
int QueueSize(Queue *q);
//初始化
void QueueInit(Queue *q) 
{
	assert(q);
	q->head = q->tail = NULL;
}
//销毁
void QueueDestroy(Queue *q) 
{
	QueueNode* cur = q->head;
	
	while (cur) 
	{
		QueueNode *next = (QueueNode *)cur->next;
		free(cur);
		cur = next;
	}
	q->head = q->tail = NULL;
}

//队尾入队
void QueuePush(Queue *q, int x) 
{
	assert(q);
	QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
	if (newNode == NULL)
	{
		exit(-1);
		perror("QueuePush::malloc");
	}
	newNode->data = x;
	newNode->next = NULL;
	
	if (q->tail == NULL) 
	{
		q->head = q->tail = newNode;
	}
	else 
	{
		q->tail->next = (Queue *)newNode;
		q->tail = newNode;
	}
}
//队头出队
void QueuePop(Queue *q) 
{
	assert(q);
	assert(!QueueEmpty(q));
	if (q->head->next == NULL) 
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	else 
	{
		QueueNode *next = (QueueNode *)q->head->next;
		free(q->head);
		q->head = next;
	}
}

//判断空
bool QueueEmpty(Queue *q) 
{
	assert(q);
	return q->head ==  NULL ? true : false;
}
//获取队头数据
QueDataTypef QueueFront(Queue *q) 
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->head->data;
}
//获取队尾数据
QueDataTypef QueueBack(Queue *q) 
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->tail->data;
}

//求队列的元素个数
int QueueSize(Queue *q) 
{
	assert(q);
	int size = 0;
	QueueNode *cur = q->head;
	while (cur) 
	{
		cur = (QueueNode *)cur->next;
		size++;
	}
	return size;
}

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


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

void myStackPush(MyStack* obj, int x) {
    //往不为空的队列里面倒数据,保证一个队列是空的
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
    //非空队列往空队列里面倒数据,只剩一个数据的时候就将他释放并返回
    Queue *pnoEmpty = &obj->q1;
    Queue *pEmpty = &obj->q2;
    if(QueueEmpty(pnoEmpty))
    {
        pEmpty = &obj->q1;
        pnoEmpty = &obj->q2;
    }
    while(QueueSize(pnoEmpty) > 1)
    {
        QueuePush(pEmpty,QueueFront(pnoEmpty));
        QueuePop(pnoEmpty);
    }
    int ret = QueueBack(pnoEmpty);
    QueuePop(pnoEmpty);
    return ret;
}

int myStackTop(MyStack* obj) {
    //队列的尾部元素,等于栈顶的元素,取非空队列的尾部元素
    int ret = 0;
    if(!QueueEmpty(&obj->q1))
    {
       ret = QueueBack(&obj->q1);
    }
    else
    {
       ret = QueueBack(&obj->q2);
    }
    return ret;
}

bool myStackEmpty(MyStack* obj) {
    //两个队列都不为空栈就不为空
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); 
}

void myStackFree(MyStack* obj) {
    //两个队列都释放,最后释放obj
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    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
  • 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
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195

232. 用栈实现队列

链接: link.

题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):

实现 MyQueue 类:

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空,返回 true ;否则,返回 false

实现思路:
只需要在一个结构里面定义出来两个栈,一个栈用于存取数据push,一个栈用来出数据pop,既然要实现先进先出的原则,不妨push栈中的元素,依次取出来后倒入到用于出数据的栈中pop,最后再将数据从pop中倒出
在这里插入图片描述

typedef int STData;
typedef struct Stack 
{
	STData *a;
	int capacity;
	int top;
}Stack;

//初始化
void StackInit(Stack *ST);
//栈销毁
void StackDestroy(Stack *ST);
//入栈
void StackPush(Stack *ST, int x);
//弹栈
void StackPop(Stack *ST);
//获取栈顶元素
int StackTop(Stack *ST);
//判断栈是否空
bool StackEmpty(Stack *ST);
//获取栈顶元素个数
int StackSize(Stack *ST);


//初始化
void StackInit(Stack *ST) 
{
	assert(ST);
	ST->a = (STData *)malloc(sizeof(int) * 4);
	ST->capacity = 4;
	ST->top = 0;
}

//栈销毁
void StackDestroy(Stack *ST)
{
	assert(ST);
	free(ST->a);
	ST->a = NULL;
	ST->capacity = ST->top = 0;
}
//入栈
void StackPush(Stack *ST, int x) 
{
	assert(ST);
	if (ST->capacity == ST->top) 
	{
		STData *tmp = realloc(ST->a,sizeof(STData) * ST->capacity * 2);
		if (tmp == NULL) 
		{
			perror("relloc:");
			exit(-1);
		}
		ST->a = tmp;
		ST->capacity = ST->capacity * 2;
	}
	ST->a[ST->top++] = x;
}
//弹栈
void StackPop(Stack *ST) 
{
	assert(ST);
	if(!StackEmpty(ST))
	ST->top--;
}
//获取栈顶元素
int StackTop(Stack *ST) 
{
	assert(ST);
	return ST->a[ST->top - 1];
}
//判断栈是否空
bool StackEmpty(Stack *ST) 
{
	assert(ST);
	return ST->top == 0 ? true : false;
}
//获取栈顶元素个数
int StackSize(Stack *ST) 
{
	assert(ST);
	return ST->top;
}

typedef struct {
    Stack push;
    Stack pop;
} MyQueue;


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

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

int myQueuePop(MyQueue* obj) {
    int ret = myQueuePeek(obj);
    StackPop(&obj->pop);
    return ret;
}

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

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->push) && StackEmpty(&obj->pop);
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->pop);
    StackDestroy(&obj->push);
    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

设计循环队列

链接: link.

题目描述:
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。

你的实现应该支持如下操作:

MyCircularQueue(k): 构造器,设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空,返回 -1 。
Rear: 获取队尾元素。如果队列为空,返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

实现思路:
为了方便标记循环队列的满和空的状态,多开辟出一个位置用于判断队列是满的情况,而如果头跟尾都是在一个位置的情况就是空队,而入数据考虑从队尾入,出数据从队头出,从队尾入数据的话有tail记录队列的尾位置,直接可以将数据插入进去

在这里插入图片描述

typedef struct {
    int *a;//数组
    int front;//循环队列的头
    int tail;//循环队列的尾
    int k;//存放多少个元素
} MyCircularQueue;
bool myCircularQueueIsFull(MyCircularQueue* obj);
bool myCircularQueueIsEmpty(MyCircularQueue* obj);

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue *obj = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
    obj->a = (int *)malloc(sizeof(int) * (k + 1));
    obj->front = obj->tail = 0;
    obj->k = k;
    return obj;
}
//入数据,既然要设计成循环队列,那么他就可以无限制的入数据,只不过超出了一定长度,会覆盖掉原先数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //如果队列已经是满的了,就不需要入数据
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    //队列不满的情况,接着入数据,入进一次数据就表示成功
    else
    {
        obj->a[obj->tail++] = value;
       
        if(obj->tail == obj->k + 1)
        {
            obj->tail = 0;
        }
        return true;
    }
}
//出队,出一个数据,头来到下一个位置,当头到最后了整个数据都出完了,队列又为空,所以需要置零
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        obj->front++;
        if(obj->front == obj->k + 1)
        {
            obj->front = 0;
        }
        return true;
    }
}
//取队头
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return -1;
    return obj->a[obj->front];
}
//取队尾,取队尾的数据要取这个下标的前一个位置的值,如果队尾的位置是0呢,前一个位置就是-1,那不切实际,需要修正一下
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return -1;
    int prevtail = obj->tail - 1;
    if(prevtail == -1)
    {
        prevtail = obj->k;
    }
    return obj->a[prevtail];
}
//刚初始化时,头跟尾都是相同的,那时候还没入数据,就以头跟尾是相等的来判断
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->tail ? true : false;
}
//判断满,多开辟一个位置(原先是k,多开是k+1),最后一个位置用来记录满不满,如果tail等于k + 1,就表示已经满了
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    int tailnext = obj->tail + 1;
    if(tailnext == obj->k + 1)
    {
        tailnext = 0;
    }
    return tailnext == obj->front;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    obj->tail = obj->front = 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
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87

在这里插入图片描述

//入数据,既然要设计成循环队列,那么他就可以无限制的入数据,只不过超出了一定长度,会覆盖掉原先数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //如果队列已经是满的了,就不需要入数据
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    //队列不满的情况,接着入数据,入进一次数据就表示成功
    else
    {
        obj->a[obj->tail++] = value;
       
        if(obj->tail == obj->k + 1)
        {
            obj->tail = 0;
        }
        return true;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

在这里插入图片描述

实现功能:将数据依次出队,先进先出的原则,当obj->front走到了k+1的位置,就表示数据已经出完了,front又可以回到原来的位置,此时的队列是空的

//出队,出一个数据,头来到下一个位置,当头到最后了整个数据都出完了,队列又为空,所以需要置零
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        obj->front++;
        if(obj->front == obj->k + 1)
        {
            obj->front = 0;
        }
        return true;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

在这里插入图片描述

//判断满,多开辟一个位置(原先是k,多开是k+1),最后一个位置用来记录满不满,如果tail等于k + 1,就表示已经满了
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    int tailnext = obj->tail + 1;
    if(tailnext == obj->k + 1)
    {
        tailnext = 0;
    }
    return tailnext == obj->front;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

在这里插入图片描述

//取队尾,取队尾的数据要取这个下标的前一个位置的值,如果队尾的位置是0呢,前一个位置就是-1,那不切实际,需要修正一下
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return -1;
    int prevtail = obj->tail - 1;
    if(prevtail == -1)
    {
        prevtail = obj->k;
    }
    return obj->a[prevtail];
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
推荐阅读