[数据结构与算法]【数据结构】栈和队列典例--纯C

?s???????20. 有效的括号

通过题目描述的问题，使用栈来解决是最优解。

思路：１）找到左括号们，将其入栈，遇到右括号就开始依次出栈，如果不符合匹配标准，就返回ｆａｌｓｅ

２）匹配过程中，会出现栈内数据为空但是需要从站内取数据的情况，出现遍历字符串结束后，栈内数据不为空的情况都需要额外考虑。

画图：

针对思路２的要额外处理

代码：

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//栈顶
	int capacity;//容量
}Stack;

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

//销毁
void StackDestroy(Stack* ps)
{
	
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

//入栈
void StackPush(Stack* ps, STDataType x)
{
	//断言
	assert(ps);
	//判断是否需要扩容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? ps->capacity = 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		//判断扩容是否成功
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	//插入数据
	//数组的下标从0开始，top指向的就是栈顶
	ps->a[ps->top] = x;
	ps->top++;
}

//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	//断言栈是否为空
	assert(ps->top > 0);

	ps->top--;
}

//获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps);
	//断言栈是否为空
	assert(ps->top);

	return ps->a[ps->top-1];
}

//检测栈是否为空
bool StackEmpty(Stack* ps)
{
	assert(ps);
	非空
	//if (ps->top > 0)
	//{
	//	return false;
	//}
	为空
	//else
	//	return true;
	//更优化的写法
	return ps->top == 0;
}

int StackSize(Stack* ps)
{
	assert(ps);
	//返回个数，top指的是栈顶数据的下一位。
	return ps->top;
}

bool isValid(char * s){
    Stack st;
    StackInit(&st);//初始化
    while(*s!='\0')//遍历
    {
        if(*s=='{'||*s=='['||*s=='(')
        {
            StackPush(&st,*s);//当为{,[,( 时入栈
            s++;//更新
        }
        else
        {
            if(!StackEmpty(&st))//当栈不为空时
            {
            char top = StackTop(&st);//取出栈顶数据
            StackPop(&st);//删除栈顶数据
            if((top == '{'&& *s!='}')||(top == '('&&*s!=')'||top == '['&&*s!=']'))//如果不匹配，就返回false
            {
                return false;
            }
            else
            {
                s++;
            }
            }
            else//当栈为空时，说明其缺少左括号，必然不能配对
            return false;
        }

    }
    //循环结束时
    int ret = StackEmpty(&st);//记录栈是否为空
    StackDestroy(&st);//销毁栈
    if(ret)//当栈为空，即结束了匹配
        return true;
    else//栈内有数据，就说明循环结束时，原字符串有单个左括号无法被匹配。
        return false;
    

}

225. 用队列实现栈

思路：队列的性质是：先入先出；栈的性质是：后入后出。

可以创建两个队列，先使用一个存数据，要取出数据时，可以将前N－１个数据移到另一个队列，取出（并删除）数据，以此往复，模拟实现栈的相关功能。

画图：

移除并返回栈顶元素：

取出５

将队列１中的数据清空

插入数据：

刚开始可以随意选择一个空的队列插入，在后面插入的元素都必须插入到非空队列中。

这里可以通过选择语句确立空与非空队列。

返回栈顶元素：

队列拥有访问队尾元素的功能，所以可以直接通过队列来实现。

判断是否为空：

队列１和　队列２　同时为空时，栈为空。

代码：

typedef int QDataType;

//链表的节点
typedef struct QueueNode
{
	QDataType data;//数据
	struct QueueNode* next;//标记下一个节点
}QNode;

typedef struct Queue
{
	QNode* head;//头指针
	QNode* tail;//尾指针
}Queue;
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

void QueueDestory(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, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	assert(newnode);

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

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

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail);

	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;
	}
}

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

	//return pq->head == NULL && pq->tail == NULL;
	return pq->head == NULL;
}

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

	return size;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail);

	return pq->tail->data;
}

typedef struct {
    //创建两个队列
    Queue q1;
    Queue q2;

} MyStack;


MyStack* myStackCreate() {
    //为结构体分配空间，不能使用
    //MyStack st;  栈上开辟的临时变量，出栈即销毁，返回的指针为空指针。
    //在堆上开辟空间，malloc动态开辟
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    //assert(pst);//可有可无
    //Mystack结构体成员初始化
    QueueInit(&pst->q1);

    QueueInit(&pst->q2);
    return pst;
}

void myStackPush(MyStack* obj, int x) {
    //非空的队列放入数据，始终保持存在一个空的队列
    if(!QueueEmpty(&obj->q1))//非空
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }

}

int myStackPop(MyStack* obj) {
    //assert(obj);
    //指定一个空队列和非空队列,定义q1为空
    Queue* empty = &obj->q1;
    Queue* nonempty = &obj->q2;
    //若不是，就交换
    if(!QueueEmpty(&obj->q1))
    {
        empty = &obj->q2;
        nonempty = &obj->q1;
    }
    while(QueueSize(nonempty)>1)//从非空队列中持续取数据放入空队列中，并删数据
    {
        QDataType front = QueueFront(nonempty);//获取数据
        QueuePush(empty,front);//插入数据
        QueuePop(nonempty);//删数据
    }
    //获取“栈顶”数据
    QDataType top = QueueFront(nonempty);
    移除栈顶数据
    QueuePop(nonempty);
    //返回“栈顶”元素
    return top;

}

int myStackTop(MyStack* obj) {
    //指定一个空队列和非空队列,定义q1为空
    Queue* empty = &obj->q1;
    Queue* nonempty = &obj->q2;
    //若不是，就交换
    if(!QueueEmpty(&obj->q1))
    {
        empty = &obj->q2;
        nonempty = &obj->q1;
    }

    return QueueBack(nonempty);

}

bool myStackEmpty(MyStack* obj) {
    assert(obj);
    //当q1和q2同时为空时，“栈”为空
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);

}

void myStackFree(MyStack* obj) {
    //释放内存时，先解决结构体内部的q1和q2
    assert(obj);
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);
    free(obj);
    //置空并不会改变实参的状态

}

用栈实现队列

思路：栈的性质：后入后出；队列的性质：先入先出。

创立两个栈，在两个栈上模拟实现队列的基本功能。

画图：

先入1　2　3　4　5　数据

ｐｏｐ

取出队头元素1

将栈1的所有元素移植至栈2

从栈二中提取目标元素1

ｐｅｅｋ

通过ｐｏｐ可以看出，栈２中的数据可以模仿队列出数据。

由此可以得出结论：模拟实现队列只需要导数据1次即可。

?

ｐｕｓｈ

?

根据已有的结论，将数据先导入栈1中，等到栈2中的数据被删空时再将栈1中的数据导入栈2中。

?

ｅｍｐｔｙ

栈1　和　栈2　同时为空时队列为空。

?

注意：在ｐｏｐ和　ｐｕｓｈ数据时，要判断是否为空的情况。

?

代码：

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//栈顶
	int capacity;//容量
}Stack;
void StackInit(Stack* ps)
{
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

//销毁
void StackDestroy(Stack* ps)
{
	
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

//入栈
void StackPush(Stack* ps, STDataType x)
{
	//断言
	assert(ps);
	//判断是否需要扩容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? ps->capacity = 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		//判断扩容是否成功
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	//插入数据
	//数组的下标从0开始，top指向的就是栈顶
	ps->a[ps->top] = x;
	ps->top++;
}

//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	//断言栈是否为空
	assert(ps->top > 0);

	ps->top--;
}

//获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps);
	//断言栈是否为空
	assert(ps->top);

	return ps->a[ps->top-1];
}

//检测栈是否为空
bool StackEmpty(Stack* ps)
{
	assert(ps);
	非空
	//if (ps->top > 0)
	//{
	//	return false;
	//}
	为空
	//else
	//	return true;
	//更优化的写法
	return ps->top == 0;
}

int StackSize(Stack* ps)
{
	assert(ps);
	//返回个数，top指的是栈顶数据的下一位。
	return ps->top;
}

typedef struct {
    Stack s1;//储存数据最初始的栈
    Stack s2;//取数据专用的栈

} MyQueue;
bool myQueueEmpty(MyQueue* obj);

MyQueue* myQueueCreate() {
    //分配空间
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    //初始化
    StackInit(&obj->s1);//放数据
    StackInit(&obj->s2);
    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    //插入数据,s1为储存初始数据的栈
    StackPush(&obj->s1,x);
}

int myQueuePop(MyQueue* obj) {
    //如果s2为空
    if(StackEmpty(&obj->s2))
    {
        //导数据
        while(StackSize(&obj->s1))
    {
        int top = StackTop(&obj->s1);
        StackPush(&obj->s2,top);
        StackPop(&obj->s1);
    }
    }
    int top = StackTop(&obj->s2);
    StackPop(&obj->s2);
    return top;
}

int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->s2))
    {
    while(StackSize(&obj->s1))
    {
        int top = StackTop(&obj->s1);
        StackPush(&obj->s2,top);
        StackPop(&obj->s1);
    }
    }
    int top = StackTop(&obj->s2);
    return top;
}

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

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

622. 设计循环队列

思路：

创建结构体变量，记录头尾，ｋ，指针数组。

判断为空的条件：当ｈｅａｄ　＝＝　ｔａｉｌ时表示队列为空。

但是队列已满的条件也为ｈｅａｄ　＝＝　ｔａｉｌ。

解决方案：

为空

为保证空间一定能存放下ｋ个元素，将数组空间＋１即可满足。

此时判断为空的条件：ｈｅａｄ　＝＝　ｔａｉｌ

　　判断为满的条件：ｈｅａｄ　＝　ｔａｉｌ＋１

注意：多出来的一个空间在数组中时随机的，并不是在数组末尾。

画图：

环形只存5个数据，开辟了6个空间

经过一系列插入，删除操作：

再插入值

此时已经插入了5个值了，队列已经满了，判定条件就成了ｔａｉｌ＋１　＝＝　ｈｅａｄ

这是多次插入和删除情况下的，若是不进行删除操作：

此时就已经满了。判定条件　ｔａｉｌ　＝＝　ｋ

?

代码：

typedef struct {
    //数组，头，尾，k
    int* a;
    int head;
    int tail;
    int k;

} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(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;
    }
    else
    {
        obj->a[obj->tail] = value;
        //更新tail
        //如果走到尾的话，就归0
        if(obj->tail == obj->k)
        {
            obj->tail = 0;
        }
        else
            obj->tail++;
    }
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        //更新头
        if(obj->head == obj->k)
        {
            obj->head = 0;
        }
        //数据覆盖即可
        else
            obj->head++;
        return true;
    }
    
}

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

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        if(obj->tail == 0)
        {
            return obj->a[obj->k];
        }
        else
            return obj->a[obj->tail-1];
    }

}

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

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if(obj->head==0 && obj->tail == obj->k)
    {
        return true;
    }
    else if(obj->tail+1 == obj->head)
    {
        return true;
    }
    else
        return false;

}

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