栈和队列的应用-创新互联

目录

• 1.括号匹配问题
• • 1.1流程图
  • 1.2代码
  • 1.3复杂度
• 2.用队列实现栈
• • 2.1思路
  • 2.2画图
  • 2.3代码
• 3.用栈实现队列
• • 3.1思想
  • 3.2画图
  • 3.3代码
• 4.循环队列
• • 4.1思想
  • 4.2画图
  • 4.3代码

成都创新互联是一家集网站建设,朝阳企业网站建设,朝阳品牌网站建设,网站定制,朝阳网站建设报价,网络营销,网络优化,朝阳网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。1.括号匹配问题

  给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：(1)左括号必须用相同类型的右括号闭合。(2)左括号必须以正确的顺序闭合。(3)每个右括号都有一个对应的相同类型的左括号。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/valid-parentheses/

1.1流程图

1.2代码

//使用动态数组实现栈
typedef struct SeqStack
{char* arr;
    int top;
    int capacity;
}SeqStack;

//判空
bool IsEmpty(SeqStack* ps)
{if(ps->top == -1)
        return true;

    return false;
}

//初始化
void InitStack(SeqStack* ps)
{ps->arr = (char*)malloc(4*sizeof(char));
    if(ps->arr == NULL)
        return;
    ps->top = -1;
    ps->capacity = 4;
}

//进栈
void Push(SeqStack* ps,char ch)
{if(ps->top + 1 == ps->capacity)
    {char* tmp = (char*)realloc(ps->arr,ps->capacity*2*sizeof(char));
        if(tmp == NULL)
            return;

        ps->arr = tmp;
        ps->capacity *= 2;
    }
    ps->arr[++ps->top] = ch;
}

//出栈
void Pop(SeqStack* ps)
{if(ps->top == -1)
        return;

    ps->top--;
}

//取栈顶元素
char GetTopElement(SeqStack* ps)
{char ch = ps->arr[ps->top];
    return ch;
}

//栈的括号匹配
bool isValid(char * s){int len = strlen(s);

    SeqStack stack;
    InitStack(&stack);
	
	//遍历原数组
    for(int i = 0;i< len;i++)
    {//左括号进栈
        if(s[i] == '(' || s[i] == '[' || s[i] == '{')
        {Push(&stack,s[i]);
        }
        //右括号与栈顶元素比较
        else
        {	//右括号单身
            if(IsEmpty(&stack))
                return false;
			
			//取栈顶元素
            char ret = GetTopElement(&stack);
            //三种情况左右括号不匹配
            if(s[i] == ')' && ret != '(')
                return false;
            else if(s[i] == ']' && ret != '[')
                return false;
            else if(s[i] == '}' && ret != '{')
                return false;
            Pop(&stack);
        }
    }
	
	//左括号不单身
    if(IsEmpty(&stack))
        return true;
    //左括号单身
    else
        return false;
}

1.3复杂度

时间复杂度:O(n)
空间复杂度:O(1)

2.用队列实现栈

  请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/implement-stack-using-queues/

2.1思路

1.用两个队列实现栈的各个功能
2.创建栈
先创建栈malloc 再初始化两个队列
3.插入(push)
将数据插入到非空队列
4.删除(pop)
将非空队列(元素个数>1)倒到另外一个空队列当中，然后非空队列只剩一个元素，此时弹出该元素，就实现栈的删除
5.取栈顶元素
取非空队列的队尾元素
6.判空
当两个队列全为空时，栈为空
7.销毁栈(destroy)
先销毁两个队列，再释放栈

2.2画图

2.3代码

//方便修改数据类型
typedef int ElemType;

//定义队列结点
typedef struct QueueNode
{ElemType data;//数据域
	struct QueueNode* next;//指针域
}QueueNode;

//封装队头指针和队尾指针
typedef struct Queue
{QueueNode* head;
	QueueNode* tail;
	int size;
}Queue;

//初始化
void InitQueue(Queue* q)
{assert(q);

	q->head = q->tail = NULL;
	q->size = 0;
}

//判空
bool IsEmpty(Queue* q)
{assert(q);

	if (q->size == 0)
		return true;

	return false;
}

//入队
void Push(Queue* q,ElemType x)
{assert(q);

	if (q->size == 0)
	{QueueNode* tmp = (QueueNode*)malloc(sizeof(QueueNode));
		if (tmp == NULL)
			return;

		q->head = q->tail = tmp;
		tmp->data = x;
		tmp->next = NULL;
		q->size++;
	}
	else
	{QueueNode* tmp = (QueueNode*)malloc(sizeof(QueueNode));
		if (tmp == NULL)
			return;

		tmp->data = x;
		tmp->next = NULL;
		q->tail->next = tmp;
		q->tail = q->tail->next;
		q->size++;
	}
}

//出队
void Pop(Queue* q)
{assert(q && q->head);

	if (q->size == 0)
		return;

	if (q->head == q->tail)
	{free(q->head);
		q->head = q->tail = NULL;
		q->size--;
	}
	else
	{QueueNode* del = q->head;
		q->head = del->next;
		q->size--;
		free(del);
	}
}

//取队首元素
ElemType GetHeadElement(Queue* q)
{assert(q);
    assert(!IsEmpty(q));

	return q->head->data;
}

//取队尾元素
ElemType GetTailElement(Queue* q)
{assert(q && q->head);

	return q->tail->data;
}

//求队长
int QueueSize(Queue* q)
{assert(q);

	return q->size;
}

//销毁队列
void DestroyQueue(Queue* q)
{assert(q);
    

	QueueNode* cur = q->head;
	while (cur)
	{QueueNode* tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	q->head = q->tail = NULL;
	q->size = 0;
}

//封装两个队列定义栈结构
typedef struct {Queue q1;
    Queue q2;
} MyStack;

//先malloc在初始化两个队列
MyStack* myStackCreate() {//定义栈
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    
    //初始化队列q1和队列q2
    InitQueue(&obj->q1);
    InitQueue(&obj->q2);
	
	//返回栈
    return obj;
}

//进栈
void myStackPush(MyStack* obj, int x) {//在非空队列中插入数据
    if(!IsEmpty(&obj->q1))
        Push(&obj->q1,x);
    else
        Push(&obj->q2,x);
}

//出栈
int myStackPop(MyStack* obj) {//假设法找空队列
    Queue* empty = &obj->q1;
    Queue* nonempty = &obj->q2;
    if(!IsEmpty(&obj->q1))
    {empty = &obj->q2;
        nonempty = &obj->q1;
    }

	//当非空队列的元素个数>1,将其前面的元素插入到空队列当中实现倒数据
    while(QueueSize(nonempty) >1)
    {//往空队列中倒入一个元素,非空队列就删除该元素
        Push(empty,GetHeadElement(nonempty));
        Pop(nonempty);
    }
	
	//将非空队列的最后一个元素保存下来
    int top = GetHeadElement(nonempty);
    //删除非空队列的最后一个元素
    Pop(nonempty);
	
	//返回栈顶元素(非空队列的最后一个元素)
    return top;
}

//取栈顶元素
int myStackTop(MyStack* obj) {//将非空队列的队尾元素返回
    if(!IsEmpty(&obj->q1))
        return GetTailElement(&obj->q1);
    else
        return GetTailElement(&obj->q2);
}

//判空
bool myStackEmpty(MyStack* obj) {//当两个队列同时为空,栈就为空
    return IsEmpty(&obj->q1) && IsEmpty(&obj->q2);
}

//销毁栈
void myStackFree(MyStack* obj) {//销毁队列q1和队列q2
    DestroyQueue(&obj->q1);
    DestroyQueue(&obj->q2);

	//释放栈
    free(obj);
}

3.用栈实现队列

  请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/implement-queue-using-stacks/

3.1思想

1.用两个栈实现队列的各个功能
一个栈(pushStack)专门用来存数据，另外一个栈(popStack)用来删数据
2.创建队列
先创建队列malloc 再初始化两个栈
3.插入(push)
直接将元素插入到pushStack，也就是代码里的q1
4.取队首元素
将pushStack里的元素倒入到popStack中，然后再返回popStack的栈顶元素，并弹出该元素
5.删除(pop)
弹出popStack的栈顶元素
6.判空
当两个栈全为空，队列为空
7.销毁队列(destroy)
先销毁两个栈，再释放队列

3.2画图

3.3代码

//方便修改数据类型
typedef int ElemType;

//定义栈结构
typedef struct SeqStack
{ElemType* a;
	int top;//栈顶指针
	int capacity;//栈容量
}SeqStack;

//判空
bool IsEmpty(SeqStack* ps)
{//为什么assert,非常规思维
	assert(ps);

	if (ps->top == -1)
		return true;

	return false;
}

//初始化
void InitStack(SeqStack* ps)
{assert(ps);

	ps->a = (ElemType*)malloc(4 * sizeof(ElemType));
	if (ps->a == NULL)
	{		return;
	}
	ps->top = -1;
	ps->capacity = 4;
}

//取栈顶元素
ElemType GetTopElement(SeqStack* ps)
{assert(ps);

	ElemType x = ps->a[ps->top];

	return x;
}

//求栈长
int StackLength(SeqStack* ps)
{assert(ps);

	return ps->top + 1;
}

//进栈
void StackPush(SeqStack* ps, ElemType x)
{assert(ps);

	if (StackLength(ps) == ps->capacity)
	{ElemType* tmp = (ElemType*)realloc(ps->a, ps->capacity * 2 * sizeof(ElemType));
		if (tmp == NULL)
		{	return;
		}

		ps->a = tmp;
		ps->capacity *= 2;
	}

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

//出栈
void StackPop(SeqStack* ps)
{assert(ps);

	if (IsEmpty(ps))
		return;

	ps->top--;
}

//销毁栈
void DestroyStack(SeqStack* ps)
{assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = -1;
}

//定义两个栈创建队列
typedef struct {SeqStack q1;
    SeqStack q2;
} MyQueue;

//创建队列再初始化两个栈
MyQueue* myQueueCreate() {//创建队列
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));

	//初始化两个栈
    InitStack(&obj->q1);
    InitStack(&obj->q2);

	//返回队列
    return obj;
}

//入队
void myQueuePush(MyQueue* obj, int x) {assert(obj);

    StackPush(&obj->q1,x);
}

//出队
int myQueuePop(MyQueue* obj) {assert(obj);
    
    int peek = myQueuePeek(obj);
    StackPop(&obj->q2);

    return peek;
}

//取队首元素
int myQueuePeek(MyQueue* obj) {assert(obj);
    
    //如果popStack为空且pushStack不为空
    //就将pushStack的元素倒入到popStack当中
    if(IsEmpty(&obj->q2))
    {while(!IsEmpty(&obj->q1))
        {	//将pushStack当中的元素倒入到popStack当中
            StackPush(&obj->q2,GetTopElement(&obj->q1));
            //弹出pushStack的栈顶元素
            StackPop(&obj->q1);
        }
    }
	
	//返回队首元素(也就是popStack当中的栈顶元素)
    return GetTopElement(&obj->q2);
}

//判空
bool myQueueEmpty(MyQueue* obj) {assert(obj);
	
	//当两个栈同时为空时,队列为空
    return IsEmpty(&obj->q1) && IsEmpty(&obj->q2);
}

//销毁队列
void myQueueFree(MyQueue* obj) {assert(obj);

	//先销毁两个栈
    DestroyStack(&obj->q1);
    DestroyStack(&obj->q2);

	//释放队列
    free(obj);
}

4.循环队列

  设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/design-circular-queue

4.1思想

  使用链表或者数组实现循环队列，因为前者不能随机访问，所以我们选择用数组实现循环队列。循环队列头尾相连，大小固定。
两大问题:
1.如何判空判满
(1)增加加一个计数变量(size)
(2)创建一个空结点
2.如何用数组实现循环
(1)特殊处理
if(rear == Maxsize) rear = 0;
(2)循环取模
(rear + 1) % Maxsize

4.2画图

4.3代码

//定义循环队列结构
typedef struct {int* arr;//数组
    int front;//队头指针
    int rear;//队尾指针
    int k;//循环队列有效元素个数
} MyCircularQueue;

//创建循环队列(队列总大小为k+1)
MyCircularQueue* myCircularQueueCreate(int k) {//创建循环队列
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));

	//开辟k+1个数组元素
    obj->arr = (int*)malloc((k+1)*sizeof(int));
    //置空
    obj->front = obj->rear = 0;
    //循环队列有效元素个数
    obj->k = k;

	//返回循环队列
    return obj;
}

//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {assert(obj);

    if(obj->front == obj->rear)
        return true;
    
    return false;
}

//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {assert(obj);

    if((obj->rear + 1)%(obj->k + 1) == obj->front)
        return true;
    
    return false;
}

//入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {assert(obj);
	//判满
    if(myCircularQueueIsFull(obj))
        return false;
	//存值
    obj->arr[obj->rear] = value;
    //循环
    obj->rear = (obj->rear + 1) % (obj->k + 1);

    return true;
}

//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {assert(obj);
	//判空
    if(myCircularQueueIsEmpty(obj))
        return false;
	//循环
    obj->front = (obj->front + 1) % (obj->k + 1);

    return true;
}

//取队首元素
int myCircularQueueFront(MyCircularQueue* obj) {assert(obj);
	//判空
    if(myCircularQueueIsEmpty(obj))
        return -1;
	//取值
    return obj->arr[obj->front];
}

//取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {assert(obj);

	//判空
    if(myCircularQueueIsEmpty(obj))
        return -1;
	//找到rear的前一个结点
    int rear = (obj->rear + obj->k) % (obj->k + 1);
    return obj->arr[rear];
}

//销毁循环队列
void myCircularQueueFree(MyCircularQueue* obj) {assert(obj);
	//先释放开辟的k+1个数组大小的空间
    free(obj->arr);
	//再释放开辟的结构体变量
    free(obj);
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

当前名称：栈和队列的应用-创新互联
文章链接：http://cdxtjz.cn/article/dcpsie.html