栈和队列的几道OJ题（数据结构、C语言、LeetCode）

前言：

本篇博客整理了几道关于栈和队列的OJ题，着重介绍栈和队列之间的互相实现，以及循环队列
代码实现：C语言
题目来源：LeetCode
题目链接：

有效的括号
用队列实现栈
用栈实现队列
设计循环队列

文章目录

- - - 1. 有效的括号
    - 2. 用队列实现栈
    - 3. 用栈实现队列
    - 4. 设计循环队列（***）

1. 有效的括号

LeetCode链接：有效的括号
题目描述：

解决思路：利用栈的特性，先进后出，遍历字符串，把左边的符号（‘(’、‘[’、‘{’）依次存到栈中，然后再逐个出栈和字符串后面的右边的符号比对，符合题意的则继续往下操作。
AC代码如下：

typedef char STDateType;//细节
typedef struct Stack
{
	STDateType* a;
	int top;
	int capacity;
}ST;

void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDateType x);
void StackPop(ST* ps);
STDateType StackTop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);

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

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

void StackPush(ST* ps, STDateType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDateType* tmp = (STDateType*)realloc(ps->a, sizeof(STDateType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc failn");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}

	ps->a[ps->top] = x;
	ps->top++;
}

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

STDateType 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)
{
	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;
            }

            STDateType top = StackTop(&st);
            StackPop(&st);
            if((top == '{' && *s == '}') 
            || (top == '(' && *s == ')') 
            || (top == '[' && *s == ']'))
            {
                ++s;
            }
            else
            {
                StackDestroy(&st);
                return false;
            }

        }
    }

    bool ret = StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}

注意：在返回bool值之前，要将创建的栈销毁，防止内存泄漏。还有诸多控制细节，都在代码中。

2. 用队列实现栈

LeetCode链接：用队列实现栈
题目描述：

解决思路：用C语言解决的话，就得先把队列写出来，才能进行模拟，这里，我们直接调用之前写好的队列即可

AC代码如下：

//链式结构：表示队列
typedef int QDateType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDateType date;
}QNode;

//队列的结构
typedef struct Queue
{
	//int size;
	QNode* head;
	QNode* tail;
}Queue;

//初始化队列
void QueueInit(Queue* pq);

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

//队尾入队列
void QueuePush(Queue* pq, QDateType x);

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

//获取队列头部元素
QDateType QueueFront(Queue* pq);

//获取队列队尾元素
QDateType QueueBack(Queue* pq);

//检测队列是否为空
bool QueueEmpty(Queue* pq);

//获取队列的长度(队列中存放数据的个数)
int QueueSize(Queue* pq);


void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDateType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc fail");
		exit(-1);
	}

	newnode->date = x;
	newnode->next = NULL;

	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL)//只剩下一个结点
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else//多个结点
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

QDateType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->date;
}

QDateType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->date;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL;
}

int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}

	return size;
}

/

注意：本题利用队列模拟了栈，深度复习了栈和队列的相关知识

3. 用栈实现队列

LeetCode链接：用栈实现队列
题目描述：

解决思路：有了第二题的基础，这题也是利用两个栈来回倒数据，可实现队列先进先出的特性，有点类似，但又有一些细节。C语言解决，这里也是要先把栈给写出来，才能进行模拟队列，这里我们也是直接调用之前写好的栈。

AC代码如下：

//动态的栈 支持动态增长
typedef int STDateType;
typedef struct Stack
{
	STDateType* a;
	int top;//栈顶
	int capacity;//容量
}ST;


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

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

//入栈
void StackPush(ST* ps, STDateType x);

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

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

//检测栈是否为空
bool StackEmpty(ST* ps);

//获取栈的长度(栈中存放数据的个数)
int StackSize(ST* ps);


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

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

void StackPush(ST* ps, STDateType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDateType* tmp = (STDateType*)realloc(ps->a, sizeof(STDateType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc failn");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}

	ps->a[ps->top] = x;
	ps->top++;
}

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

STDateType 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)
{
	return ps->top;
}


/

4. 设计循环队列（***）

LeetCode链接：设计循环队列
题目描述：是比较恶心的一道题

解决思路：
下面先介绍循环队列

AC代码如下：

typedef struct {
    int* a;
    int k;
    int head;
    int tail;
} 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->head = obj->tail = 0;
    obj->k = k;

    return obj;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;

    obj->a[obj->tail] = value;
    obj->tail++;

    if(obj->tail == obj->k+1)
        obj->tail = 0;

    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return false;
    
    obj->head++;
    if(obj->head == obj->k+1)
        obj->head = 0;

    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    
    return obj->a[obj->head];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;

    int prev = obj->tail-1;
    if(obj->tail == 0)
        prev = obj->k;

    return obj->a[prev];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->head == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    int next = obj->tail + 1;
    if(next == obj->k+1)
        next = 0;
    
    return next ==  obj->head;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

学习记录：

本篇博客整理于2022.7.4
请多多指教

栈和队列的几道OJ题（数据结构、C语言、LeetCode）

C/C++/C#相关栏目本月热门文章