C++数据结构深入探究栈与队列

Stack.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int bool;
#define TRUE 1;
#define FALSE 0;
typedef int STDataType;
struct Stack
{
	STDataType* a;
	int top;       //栈顶
	int capacity;  //容量，方便增容
};
//typedef struct Stack ST;
typedef struct Stack Stack;
//初始化
void StackInit(Stack* pst);
//销毁
void StackDestroy(Stack* pst);
//入栈
void StackPush(Stack* pst, STDataType x);
//出栈
void StackPop(Stack* pst);
//返回栈顶数据
STDataType StackTop(Stack* pst);
//判断栈是否为空,空返回1非空返回0
//int StackEmpty(Stack* pst);
bool StackEmpty(Stack* pst);
//栈中数据个数
int StackSize(Stack* pst);

Stack.c
#include "Stack.h"
//初始化
void StackInit(Stack* pst)
{
	assert(pst);
	
	//开始就申请空间，好处在于空间不够时直接容量*2即可(如果刚开始是0就要单独处理)
	pst->a = malloc(sizeof(STDataType) * 4);
	pst->top = 0;
	pst->capacity = 4;
}
//销毁
void StackDestroy(Stack* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}
//入栈
void StackPush(Stack* pst, STDataType x)
{
	assert(pst);
	//从top为0的位置开始放
	//如果满了就增容
	if (pst->top == pst->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * pst->capacity * 2);
		if (tmp == NULL)
		{
			//如果开辟空间失败
			printf("realloc fail\n");
			exit(-1);//结束整个程序(-1表示异常退出)
		}
		pst->a = tmp;
		pst->capacity *= 2;
	}
	//入数据
	pst->a[pst->top] = x;
	pst->top++;
}
//出栈
void StackPop(Stack* pst)
{
	assert(pst);//不能是空指针
	assert(!StackEmpty(pst)); //栈内还有元素才能出战
	pst->top--;
}
//返回栈顶数据
STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	return pst->a[pst->top - 1];
}
//判断栈是否为空,空返回1非空返回0
bool StackEmpty(Stack* pst)
{
	assert(pst);
	return pst->top == 0;
}
int StackSize(Stack* pst)
{
	assert(pst);
	return pst->top;
}

test.c
#include "Stack.h"
//对栈操作的测试
void TestStack()
{
	Stack st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	//栈遍历数据
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	//4 3 2 1
	StackDestroy(&st);
}
int main()
{
	TestStack();
	return 0;
}

Queue.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int QDataType;
//队列中的一个结点
typedef struct Queuenode
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;
//队列(由于需要两个指针，所以用结构体定义)
typedef struct Queue
{
	QueueNode* head; //头指针
	QueueNode* tail; //尾指针
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//计算队列元素个数
int QueueSize(Queue* pq);

Queue.c
#include "Queue.h"
//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	//不带哨兵位
	pq->head = pq->tail = NULL;
}
//销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}
//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL; //等于空就为真, 不为空就是假
}
//入队
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)//申请空间失败
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = 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)//只有一个结点的情况(如果不单独考虑，那当只有一个结点时，tail会仍然指向曾经的队尾)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}
//取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}
int QueueSize(Queue* pq)
{
	int size = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

test.c
#include "Queue.h"
//对队列操作的测试
void TestQueue()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	printf("%d\n", QueueSize(&q)); //4
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	//1 2 3 4
	QueueDestroy(&q);
}
int main()
{
	TestQueue();
	return 0;
}

bool isValid(char * s)
{
    Stack st;
    StackInit(&st);
    while(*s)
    {
        //左括号入栈，右括号找最近的左括号匹配
        if(*s == '[' || *s == '(' || *s == '{')
        {
            StackPush(&st, *s);
            s++;
        }
        else
        {
            if(StackEmpty(&st))//只有后括号的情况
            {
                StackDestroy(&st);
                return false;
            }
            char top = StackTop(&st);
            //不匹配的情况
            if ( (top == '[' && *s != ']') 
            || (top == '(' && *s != ')')
            || (top == '{' && *s != '}') ) 
            {
                StackDestroy(&st);
                return false;
            }
            else //匹配的情况
            {
                StackPop(&st);
                s++;
            }
        }
    }
    //如果最后栈内为空才说明是匹配的(防止最后栈内还剩下前括号的情况)
    bool ret = StackEmpty(&st);
    StackDestroy(&st);
    return ret;
    //特别注意:在return之前需要先把栈销毁掉
}

//思路:
//入栈: 向不为空的队列入数据,始终保持另一个队列为空
//出栈: 前size-1个数据导入空队列，删除最后一个
typedef struct 
{
    Queue q1;
    Queue q2;
} MyStack;
/
    //复用
    int top = myQueuePeek(obj);//易错点:不能写&obj->popST,因为该传入队列的指针
    StackPop(&obj->popST);
    return top;
}
bool myQueueEmpty(MyQueue* obj) 
{
    //push栈和pop栈同时为空,队列才为空
    return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}
void myQueueFree(MyQueue* obj)
{
    StackDestroy(&obj->pushST);
    StackDestroy(&obj->popST);
    free(obj);
}

//循环队列是逻辑上的循环(数组、链表都可以实现,本题使用数组)
//永远空出一个位置不存储数据(目的是区分空和满)
//当front = tail说明循环队列空
//当tail+1 = front说明循环队列满
typedef struct 
{
    int* a;     //数组
    int k;      //循环队列最多能存多少个数据
    int front;  //头指针
    int tail;   //尾指针(队尾数据的下一个位置)
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a = (int*)malloc(sizeof(int)*(k+1)); //需要多开一个空间
    obj->front = 0;
    obj->tail = 0;
    obj->k = k;
    return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    return obj->front == obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    int tailNext = obj->tail + 1;
    if(tailNext == obj->k+1)
    {
        //如果tail已经走到尾(不存放数据的位置),此时认为tailNext回到了数组首元素位置
        tailNext = 0;
    }
 
    return tailNext == obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    else
    {
        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))//如果obj为空了就不能出数据
    {
        return false;
    }
    else
    {
        obj->front++;
        //极端情况:front加到尾后重新回到数组首元素
        if(obj->front == obj->k+1)
        {
            obj->front = 0;
        }
        return true;
    }
}
int myCircularQueueFront(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        return obj->a[obj->front];
    }
}
int myCircularQueueRear(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        //由于取尾需要去tail的前一个,那么当tail就在首元素的时候,要把它挪到最后一个元素的位置去
        int tailPrev = obj->tail - 1;
        if(tailPrev == -1)
        {
            tailPrev = obj->k;
        }
        return obj->a[tailPrev];
    }
}
void myCircularQueueFree(MyCircularQueue* obj) 
{
    free(obj->a);
    free(obj);
}