数据结构——栈和队列1

1.栈

1.1 概念与结构

栈：一种特殊的线性表，只允许在固定的一端进行插入和删除数据操作。进行数据的插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据遵循先进后出的原则。

压栈：栈的插入操作称为进栈/压栈/入栈，入数据在栈顶。

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

栈底层结构选型:

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

1.2栈的实现

Stack.c

#include"Stack.h"

//栈的初始化
void StackInit(Stack* ps) {
	assert(ps);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

//栈的销毁
void StackDestroy(Stack* ps) {
	if (ps->arr != NULL)
		 free(ps->arr);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;

}


//入栈 --  栈顶  -- 顺序表的尾插
void StackPush(Stack* ps, STDataType x) 
{
	assert(ps);
	//空间不够 --- 增容
	if (ps->top == ps->capacity)
	{
		//扩容
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!\n");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
		

	}
	//空间足够 --- 直接插入数据
	ps->arr[ps->top] = x;
	ps->top++;

	
}

//判空
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == NULL;
	//top=NULL   返回 true
	//top!=NULL  返回 false
}

//出栈  -- 栈顶
void StackPop(Stack* ps)
{
	assert(!StackEmpty(ps));
	ps->top--;
}

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

2.队列

2.1 概念与结构

概念：只允许在一段进行数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特点。

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

队列底层结构选型

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

2.2 队列的实现

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QDataType;

//定义队列结点的结构
typedef struct QueueNode {
	QDataType data;
	struct QueueNode* next;
}QueueNode;

//定义队列的结构

typedef struct Queue {
	QueueNode* phead;  //节点结构的指针
	QueueNode* ptail;  //节点结构的指针
	int size;          //队列有效元素个数

}Queue;

//这样定义了头结点和尾节点会使入队列和出队列的复杂度为O(1)


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

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

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

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

//计算队列里面的数据个数
QDataType QueueSize(Queue* pq);

//取队列头数据
QDataType QueueFront(Queue* pq);

//取队列尾数据
QDataType QueueBack(Queue* pq);

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

Queue.c

#include"Queue.h"


//初始化
void QueueInit(Queue* pq) {
	assert(pq);
	//队列里面只有phead和ptail

	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

//入队列
void QueuePush(Queue* pq, QDataType x) {
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!\n");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//队列为空,队头队尾都是newnode
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else {
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;

}

//判空
bool QueueEmpty(Queue* pq) {
	assert(pq);
	return pq->phead == NULL;  //pq->phead为空，返回true
	
}

//计算队列里面的有效元素个数
QDataType QueueSize(Queue* pq)
{
	
	//QueueNode* pcur = pq->phead;
	//int size = 0;
	//while (pcur)
	//{
	//	size++;
	//	pcur = pcur->next;
	//	//时间复杂度为O(N)
	//	//其余的队列接口复杂度都是O(1)
	//	//尝试换一种方法来实现，达到此接口的时间复杂度为O(1)
	//}
	//return size;
	
	return pq->size;
}


//出队列
void QueuePop(Queue* pq) {
	assert(pq);//传过来的pq不为空 or 有效的队列结构
	assert(!QueueEmpty(pq));//空队列不可取出数据
	//只有一个节点
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else {
		QueueNode* next=pq->phead->next;
		free(pq->phead);
		pq->phead = next;

	}
	pq->size--;

}

//取队列头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);//传过来的pq不为空 or 有效的队列结构
	assert(!QueueEmpty(pq));//空队列不可取出数据
	return pq->phead->data;
}

//取队列尾数据
QDataType QueueBack(Queue* pq) {
	assert(pq);//传过来的pq不为空 or 有效的队列结构
	assert(!QueueEmpty(pq));//空队列不可取出数据
	return pq->ptail->data;
}

//销毁队列
void QueueDestroy(Queue* pq) {
	assert(pq);
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	//将队列的两个指针置为空，防止变为野指针
	pq->size = 0;
}

3. 栈和队列算法题

3.1 有效的括号

typedef char STDataType;
//定义栈的数据结构
//栈的底层结构 链表或者是数组都是可以的 但是数组的实现会更加简单（有点像顺序表） 

typedef struct Stack {
	STDataType* arr;
	int top;
	int capacity;
}Stack;
//栈的初始化
void StackInit(Stack* ps) {
	assert(ps);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

//栈的销毁
void StackDestroy(Stack* ps) {
	if (ps->arr != NULL)
		 free(ps->arr);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;

}


//入栈 --  栈顶  -- 顺序表的尾插
void StackPush(Stack* ps, STDataType x) 
{
	assert(ps);
	//空间不够 --- 增容
	if (ps->top == ps->capacity)
	{
		//扩容
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!\n");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
		

	}
	//空间足够 --- 直接插入数据
	ps->arr[ps->top] = x;
	ps->top++;

	
}

//判空
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == NULL;
	//top=NULL   返回 true
	//top!=NULL  返回 false
}

//出栈  -- 栈顶
void StackPop(Stack* ps)
{
	assert(!StackEmpty(ps));
	ps->top--;
}

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

    //1.遇左括号入栈
    //2.遇右括号出栈，进行匹配,匹配不成功返回false，匹配成功，pi越界且栈为空返回true
    //3.只有一个左括号，pi越界的时候，且栈不为空，返回false
    //4.只有一个右括号，空栈不可进行出栈，返回false
bool isValid(char* s) {
    Stack st;
    StackInit(&st);
    char* pi=s;
    while(*pi!='\0')
    {
        if(*pi=='(' || *pi=='{' || *pi=='[')
        {
            //入栈
            StackPush(&st,*pi);
        }else
        {
            //取栈顶，进行匹配
            if(StackEmpty(&st))
            {
                //栈为空，说明只有有括号的情况，没有左括号
                StackDestroy(&st);
                return false;
            }
            char top=StackTop(&st);
            if((top=='(' && *pi !=')') 
                ||(top=='[' && *pi !=']') 
                ||(top=='{' && *pi !='}'))
                {
                    StackDestroy(&st);
                    return false;
                }
                //出栈
                StackPop(&st);
            
        }
        pi++;
        }
        
        
    
    //*pi='\0' 跳出循环 两种情况：1.栈为空返回是有效的字符串 2.栈不为空（只有左括号的字符）返回的是无效的字符串
    bool ret=StackEmpty(&st)? true :false;
    StackDestroy(&st);
    return ret;

}

栈和队列的算法题后续还有哟~~