当前位置： 首页 > article >正文

栈和队列的算法题目（C语言）

article 2024/11/15 5:46:05

1. 括号匹配问题

20. 有效的括号 - 力扣（LeetCode）

利用栈后入先出的特性解题

1.判断字符串是否为空 为空返回

2.创建栈，遍历字符串

        第一个字符是左括号的情况：入栈->继续遍历下一个字符

        第一个字符是右括号的情况：从栈顶取元素，判断当前右括号是否匹配栈顶的左括号

3.遍历结束，判断栈是否为空，为空说明所有括号都已匹配，不为空说明有左括号没有匹配上

bool isValid(char* s) {
    Stack st;
    StackInit(&st);
    int count = 0;
    while(s[count])
    {
        if(s[count] == '(' 
        || s[count] == '['
        || s[count] == '{')
        {
            StackPush(&st,s[count]);
        }
        else
        {
            if(StackEmpty(&st))
            {
                StackDestory(&st);
                return false;
            }
            char top = StcakTop(&st);
            if(top == '(' && s[count] != ')'
            ||top == '{' && s[count] != '}'
            ||top == '[' && s[count] != ']')
            {
                StackDestory(&st);
                return false;
            }
            StackPop(&st);
        }
        count++;
    }
    int  result = StackEmpty(&st);
    StackDestory(&st);
    return result;
}

2. 用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）

队列的特性是先入先出 栈的特性是后入先出

创建两个队列

为空的情况：两个队列都为空

1.push插入：直接插入队列中

2.需要pop的时候，将队列的元素导到另一个队列，最后一个元素就是栈顶元素

3.当有元素需要插入，判断哪个队列不为空，就直接插入

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


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

void myStackPush(MyStack* obj, int x) {
    Queue* empty = obj->q1;
    Queue* noempty = obj->q2;
    if(QueueEmpty(noempty))
    {
        empty = obj->q1;
        noempty = obj->q2;
    }
    QueuePush(noempty,x);
}

int myStackPop(MyStack* obj) {
    Queue* empty = obj->q1;
    Queue* noempty = obj->q2;
    int val = 0;
    if(QueueEmpty(noempty))
    {
        empty = obj->q2;
        noempty = obj->q1;
    }
    while(noempty->_size > 1)
    {
        int val = QueueFront(noempty);
        QueuePush(empty,val);
        QueuePop(noempty);
    }
    if(noempty->_size == 1)
    {
        val = QueueFront(noempty);
        QueuePop(noempty);
    }
    return val;
}

int myStackTop(MyStack* obj) {

    Queue* empty = obj->q1;
    Queue* noempty = obj->q2;
    int val = 0;
    if(QueueEmpty(noempty))
    {
        empty = obj->q2;
        noempty = obj->q1;
    }
    val = noempty->_rear->_data;
    return val;
}

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

void myStackFree(MyStack* obj) {
    Queue* empty = obj->q1;
    Queue* noempty = obj->q2;
    if(QueueEmpty(noempty))
    {
        empty = obj->q2;
        noempty = obj->q1;
    }
    QueueDestory(noempty);
    free(obj->q1);
    free(obj->q2);
    free(obj);
}

3. 用栈实现队列

stack1存放要进栈的元素

stack2存放要出栈的元素

当stack2为空时   将stack1的所有元素都导到stack2中

插入：

1.直接使用StackPush插入到stack1中

删除：

1.判断stack2是否为空，为空将stack1的数据导到stack2内

2.直接使用StackPop()取到栈顶元素返回

232. 用栈实现队列 - 力扣（LeetCode）

typedef struct {
    Stack* s1;
    Stack* s2;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* newQueue = (MyQueue*)malloc(sizeof(MyQueue));
    newQueue->s1 = (Stack*)malloc(sizeof(Stack));
    newQueue->s2 = (Stack*)malloc(sizeof(Stack));
    StackInit(newQueue->s1);
    StackInit(newQueue->s2);
    return newQueue;
}

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

int myQueuePop(MyQueue* obj) {
    if(StackEmpty(obj->s2))
    {
        while(!StackEmpty(obj->s1))
        {
            StackPush(obj->s2,StackPop(obj->s1));
        }
    }
    return StackPop(obj->s2);
}

int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(obj->s2))
    {
        while(!StackEmpty(obj->s1))
        {
            StackPush(obj->s2,StackPop(obj->s1));
        }
    }
    return StcakTop(obj->s2);
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(obj->s1) && StackEmpty(obj->s2);
}

void myQueueFree(MyQueue* obj) {
    StackDestory(obj->s1);
    StackDestory(obj->s2);
    free(obj->s1);
    free(obj->s2);
    free(obj);
}

4. 设计循环队列

622. 设计循环队列 - 力扣（LeetCode）

使用数组来设计循环队列，当head走到最后一个元素就使用%来使数组循环

head就是队头，tail就是队尾

从队头出数据，队尾入数据

题目要求队列长度为k，我们申请k+1个空间用来区分队列满和不满的情况

当head==tail就是队列为空
当tail的下一个位置的元素==head就表示队列为满




typedef struct {
    int *Queue;
    int k;
    int head;
    int tail;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* newQueue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    newQueue->tail = newQueue->head = 0;
    newQueue->k = k + 1; 
    newQueue->Queue = (int*)malloc(sizeof(int)*(k+1));
    return newQueue;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->head == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail+1)%(obj->k) == obj->head;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->Queue[obj->tail] = value;
    obj->tail = (obj->tail+1)%(obj->k);
    return true;
}

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

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

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->Queue[(obj->tail-1+obj->k) % obj->k];
}



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

栈的C语言代码：

typedef char StackDataType;
	
typedef struct StackNode
{
	StackDataType* _stack;
	int _capacity;
	int _top;
}Stack;

void StackInit(Stack* st);
void StackPush(Stack* st, StackDataType data);
void StackPop(Stack* st);
StackDataType StcakTop(Stack* st);
int StackSize(Stack* st);
int StackEmpty(Stack* st);
void StackDestory(Stack* st);
void StackInit(Stack* st)
{
	st->_stack = NULL;
	st->_capacity = 0;
	st->_top = 0;
}
void StackPush(Stack* st, StackDataType data)
{
	assert(st);
	if (st->_capacity == st->_top)
	{
        int newCapacity = st->_capacity == 0?4:st->_capacity*2;
		st->_stack = (StackDataType*)realloc(st->_stack, newCapacity * sizeof(StackDataType));
        st->_capacity = newCapacity;
	}
	st->_stack[st->_top] = data;
	st->_top++;
}
void StackPop(Stack* st)
{
	assert(st);
	assert(st->_top);
	st->_top--;
}
StackDataType StcakTop(Stack* st)
{
	assert(st);
	return st->_stack[st->_top-1];
}
int StackSize(Stack* st)
{
	assert(st);
	return st->_top;
}
int StackEmpty(Stack* st)
{
	assert(st);
	if (st->_top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}
void StackDestory(Stack* st)
{
	assert(st);
	free(st->_stack);
    st->_stack = NULL;
	st->_capacity = st->_top = 0;

}

队列的C语言代码：

typedef int QueueNodeDataType;
typedef struct QListNode
{
	struct QListNode* _pNext;
	QueueNodeDataType _data;
}QNode;

typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
	int _size;
}Queue;

void QueueInit(Queue* q);
void QueuePush(Queue* q, QueueNodeDataType val);
void QueuePop(Queue* q);
bool QueueEmpty(Queue* q);
int QueueSize(Queue* q);
QueueNodeDataType QueueFront(Queue* q);
QueueNodeDataType Queuerear(Queue* q);
void QueueDestory(Queue* q);
void QueueInit(Queue* q)
{
	assert(q);
	q->_front = NULL;
	q->_rear = NULL;
	q->_size = 0;
}
void QueuePush(Queue* q, QueueNodeDataType val)
{
	assert(q);
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	assert(newNode);
	newNode->_data = val;
	newNode->_pNext = NULL;
	if (q->_front == NULL)//队列没有结点
	{
		q->_front = q->_rear = newNode;
	}
	else
	{
		q->_rear->_pNext = newNode;
		q->_rear = newNode;
	}
	q->_size++;
}
void QueuePop(Queue* q)
{
	assert(q);
	if (q->_front == NULL)
	{
		return;
	}
	else
	{
		if (q->_front == q->_rear)//说明只有一个结点
		{
			free(q->_front);
			q->_front = q->_rear = NULL;
		}
		else
		{
			QNode* cur = q->_front->_pNext;
			free(q->_front);
			q->_front = cur;
		}
	}
	q->_size--;
}
bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->_front == NULL;
}
int QueueSize(Queue* q)
{
	assert(q);
	return q->_size;
}
QueueNodeDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->_front);
	return q->_front->_data;
}
QueueNodeDataType Queuerear(Queue* q)
{
	assert(q);
	assert(q->_rear);
	return q->_rear->_data;
}
void QueueDestory(Queue* q)
{
	assert(q);
	QNode* cur = q->_front;
	while (cur)
	{
		QNode* tmp = cur;
		cur = cur->_pNext;
		free(tmp);
	}
	q->_front = q->_rear = NULL;

}


http://www.kler.cn/a/302408.html

相关文章：

  • C++中string的新特性
  • WordPress 6.7 “Rollins”发布
  • 2024-11-13 学习人工智能的Day26 sklearn(2)
  • 【MySQL】MySQL函数之JSON_EXTRACT
  • 【专题】计算机网络之网络层
  • DevOps工程技术价值流：加速业务价值流的落地实践与深度赋能
  • 8月更新速递丨秋风送爽，EasyTwin产品能力升级不停~
  • 叉车智能ai防撞系统解决方案
  • TS 常用类型
  • 小程序的右侧抽屉开关动画手写效果
  • Linux网络服务只iptables防火墙工具
  • 网络编程day04（UDP、Linux IO 模型）
  • Hive SQL基础语法及查询实践
  • Linux网络：网络套接字-TCP回显服务器——多进程/线程池(生产者消费者模型)
  • “区块链积分系统：支付安全与效率的新篇章
  • 内外网文件安全交换如何做到？
  • 春日美食汇：基于SpringBoot的订餐平台
  • windows vscode ssh 连接远程服务器
  • 工厂模式（二）：工厂方法模式
  • 使用Python或者GO实现OTP令牌的获取
  • ＜Linux＞ 基础IO
  • 利用物化视图刷新同步表记录
  • 从概念到现实，国际数字影像产业园如何打造数字文创产业标杆？
  • Android 开发避坑经验（2）：深入理解Fragment与Activity交互
  • 宽哥之家小程序任务脚本
  • 服务器深度解析：五大关键问题一网打尽