【栈和队列】算法题 ---- 力扣

        通过前面栈和队列的学习，现在来看这些算法题目

一、有效的括号

        本题让判断括号是否有效

第一眼看可能没一点思路，但仔细分析一下；

        我们学习过栈数据结构，知道栈先进后出的原则，那我们就可以使用啊；把题目的左括号存储起来，让右括号跟左括号一一比较。

思路：

        遍历字符串，遇到左括号就括号入栈，遇到右括号就与栈顶数据进行对比，如果配对就继续；如果不配对，就返回false

画图分析：

  现在有这样的括号字符串

        遍历字符串，第一个是  {  左括号，就入栈

        ps接着遍历， [  依然是左括号，入栈

        ps接着遍历，  (  还是左括号，入栈

        ps接着遍历，  )  是右括号，与栈顶数据进行比较，括号匹配，出栈

        ps接着遍历，  ]  是右括号，与栈顶数据比较，括号匹配，出栈

        ps接着遍历，  }  是右括号，与栈顶数据进行比较，括号匹配，出栈

        ps遍历完字符串，再判断栈是否为空？如果为空，就代表所以括号都匹配了；如果栈不为空，括号就不匹配。

        此外，再遍历过程中，有依次括号不匹配就要直接返回false

力扣题代码如下：

typedef char stype;
typedef struct stack {
    stype* arr;
    int size; // 栈顶
    int num;  // 空间大小
} stack;

// 初始化
void stinit(stack* ps) {
    assert(ps);
    ps->arr = null;
    ps->size = ps->num = 0;
}
// 判断栈是否为空
bool stempty(stack* ps) {
    assert(ps);
    return ps->size == 0;
}
// 入栈
void stpush(stack* ps, stype x) {
    assert(ps);
    // 判断空间大小是否足够
    if (ps->num <= ps->size) {
        int newnum = (ps->num == 0) ? 4 : 2 * ps->num;
        stype* tmp = (stype*)realloc(ps->arr, newnum * sizeof(stack));
        if (tmp == null) {
            perror("realloc filed");
            exit(1);
        }
        ps->arr = tmp;
        ps->num = newnum;
    }
    ps->arr[ps->size++] = x;
}
// 出栈
void stpop(stack* ps) {
    assert(ps);           // 不能传null
    assert(!stempty(ps)); // 栈不能为空
    ps->size--;
}
// 取栈顶数据
stype sttop(stack* ps) {
    assert(ps);           // 不能传null
    assert(!stempty(ps)); // 栈不能为空
    return ps->arr[ps->size - 1];
}
// 获取栈中数据个数
int stsize(stack* ps) {
    assert(ps);
    return ps->size;
}
// 栈的销毁
void stdestroy(stack* ps) {
    assert(ps);
    if (ps->arr)
        free(ps->arr);
    ps->arr = null;
    ps->size = ps->num = 0;
}

bool isvalid(char* s) {
    stack arr;
    // 初始化
    stinit(&arr);
    char* ps = s;
    while (*ps != '\0') {
        if (*ps == '(' || *ps == '[' || *ps == '{') {
            // 入栈
            stpush(&arr, *ps);
        } else {
            // 取栈顶数据
            if (stempty(&arr)) {
                return false;
            }
            char ch = sttop(&arr);
            if ((ch == '(' && *ps == ')') || (ch == '[' && *ps == ']') ||
                (ch == '{' && *ps == '}')) {
                stpop(&arr);
            } else {
                return false;
            }
        }
        ps++;
    }
    if (stempty(&arr)) // 栈为空
    {
        return true;
    }
    return false;
}

二、用队列实现栈

        使用队列来实现栈，我们直到，队列是先进先出，而栈是先进后出。这里我们需要用两个队列来实现栈的相关操作

思路：

        保证两个队列中有一个为空，再两个队列之间来回导入导出数据。

假设依次插入了1，2，3三个数据，现在要出栈

        将q1中数据size-1（2个）导入到q2中。

        现在q1当中剩余的数据就是要出栈的数据（即栈顶）。这样就满足了栈先进先出的特点。

力扣题代码如下：

typedef int qtype;
typedef struct queuenode // 队列节结构
{
    qtype data;
    struct queuenode* next;
} queuenode;
typedef struct queue // 队列结构
{
    int size;         // 队列中的数据个数
    queuenode* phead; // 队头
    queuenode* ptial; // 队尾
} queue;

// 初始化
void queueinit(queue* pq) {
    assert(pq);
    pq->phead = pq->ptial = null;
    pq->size = 0;
}
// 判断队列是否为空
bool queueempty(queue* pq) {
    assert(pq);
    return pq->size == 0;
}
// 入队列--从队尾插入数据
void queuepush(queue* pq, qtype x) {
    assert(pq);
    queuenode* newnode = (queuenode*)malloc(sizeof(queuenode));
    newnode->data = x;
    newnode->next = null;
    if (queueempty(pq)) // 队列为空
    {
        pq->phead = pq->ptial = newnode;
    } else { // 队列不为空
        pq->ptial->next = newnode;
        pq->ptial = newnode;
    }
    pq->size++;
}
// 出队列--从对头删除数据
void queuepop(queue* pq) {
    assert(pq);              // 不能传null
    //assert(!queueempty(pq)); // 队列不能为空
    queuenode* del = pq->phead;
    pq->phead = pq->phead->next;
    if (pq->size == 1) // 队列只有一个节点
    {
        pq->ptial = null;
    }
    pq->size--;
    free(del);
    del = null;
}
// 取队头数据
qtype queuefront(queue* pq) {
    assert(pq);              // 不能传null
    //assert(!queueempty(pq)); // 队列不能为空
    return pq->phead->data;
}
// 取队尾数据
qtype queueback(queue* pq) {
    assert(pq);              // 不能传null
    //assert(!queueempty(pq)); // 队列不能为空
    return pq->ptial->data;
}
// 获取队列数据个数
int queuesize(queue* pq) {
    assert(pq); // 不能传null
    return pq->size;
}
// 销毁队列
void queuedestroy(queue* pq) {
    assert(pq);              // 不能传null
    //assert(!queueempty(pq)); // 队列不能为空
    queuenode* pcur = pq->phead;
    while (pcur) {
        queuenode* del = pcur;
        pcur = pcur->next;
        free(del);
        del = null;
    }
    pq->phead = pq->ptial = null;
    pq->size = 0;
}

typedef struct {
    queue q1;
    queue q2;
} mystack;

mystack* mystackcreate() {
    mystack* qst = (mystack*)malloc(sizeof(mystack));
    queueinit(&qst->q1);
    queueinit(&qst->q2);
    return qst;
}

void mystackpush(mystack* obj, int x) {
    // 往不为空的队列中插入数据
    if (queueempty(&obj->q1)) {
        queuepush(&obj->q2, x);
    } else {
        queuepush(&obj->q1, x);
    }
}

int mystackpop(mystack* obj) {
    // 先找到不为空的队列
    queue* empq = &obj->q1;
    queue* noneq = &obj->q2;
    if (!(queueempty(&obj->q1))) // 如果q1不为空
    {
        empq = &obj->q2;
        noneq = &obj->q1;
    }
    //empq --  空队列
    //noneq --  非空队列
    while(queuesize(noneq) > 1) {
        // 将noneq队列的数据导入到empq中去
        queuepush(empq, queuefront(noneq));
        queuepop(noneq);
    }
    int ret = queuefront(noneq);
    queuepop(noneq);
    return ret;
}

int mystacktop(mystack* obj) {
    if(queueempty(&obj->q1))
    {
        return queueback(&obj->q2);
    }else{
        return queueback(&obj->q1);
    }
}

bool mystackempty(mystack* obj) {
    return queueempty(&obj->q1) && queueempty(&obj->q2);
}

void mystackfree(mystack* obj) {
    free(obj);
    obj = null;
}

三、用栈实现队列

        上一个题让我们用队列来实现栈，这个用两个栈来实现队列。

定义两个栈

思路：

        往pushst中插入数据，再将数据导入到popst中，出栈即可；

分析：

        假设依次插入了1，2，3三个数据，现在出栈一次，再插入一个数据4，最后取队头数据，依次出栈。

        出栈一次，popst为空，就将pushst中数据导入到popst中去。

依次导入

        出栈；

再插入数据4

取队头数据：

最后依次出队列

现在，popst栈为空，就要先将pushst中数据先导入到popst中。

再出队列

力扣题代码如下：

typedef int stype;
typedef struct stack
{
	stype* arr;
	int size;  //栈顶
	int num;   //空间大小
}stack;
//初始化
void stinit(stack* ps)
{
	assert(ps);
	ps->arr = null;
	ps->size = ps->num = 0;
}
//判断栈是否为空
bool stempty(stack* ps)
{
	assert(ps);
	return ps->size == 0;
}
//入栈
void stpush(stack* ps, stype x)
{
	assert(ps);
	//判断空间大小是否足够
	if (ps->num <= ps->size)
	{
		int newnum = (ps->num == 0) ? 4 : ps->num * 2;
		stype* tmp = (stype*)realloc(ps->arr, newnum * sizeof(stack));
		if (tmp == null)
		{
			perror("realloc filed");
			exit(1);
		}
		ps->arr = tmp;
		ps->num = newnum;
	}
	ps->arr[ps->size++] = x;
}
//出栈
void stpop(stack* ps)
{
	assert(ps); //不能传null
	assert(!stempty(ps));  //栈不能为空
	ps->size--;
}
//取栈顶数据
stype sttop(stack* ps)
{
	return ps->arr[ps->size - 1];
}
//获取栈中数据个数
int stsize(stack* ps)
{
	assert(ps);
	return ps->size;
}
//栈的销毁
void stdestroy(stack* ps)
{
	assert(ps);
	if (ps->arr)
		free(ps->arr);
	ps->arr = null;
	ps->size = ps->num = 0;
}


typedef struct {
    stack s1;
    stack s2;
} myqueue;

//初始化
myqueue* myqueuecreate() {
    myqueue* queue=(myqueue*)malloc(sizeof(myqueue));
    stinit(&queue->s1);
    stinit(&queue->s2);
    return queue;
}
//插入数据
void myqueuepush(myqueue* obj, int x) {
    assert(obj);
    stpush(&obj->s1, x);
}

int myqueuepop(myqueue* obj) {
    assert(obj);
    if(stempty(&obj->s2))
    {
        //把s1中数据导入到s2
        while(!stempty(&obj->s1))
        {
            stpush(&obj->s2,sttop(&obj->s1));
            stpop(&obj->s1);
        }
    }
    int ret=sttop(&obj->s2);
    stpop(&obj->s2);
    return ret;
}

int myqueuepeek(myqueue* obj) {
    if(stempty(&obj->s2))
    {
        //把s1中数据导入到s2
        while(!stempty(&obj->s1))
        {
            stpush(&obj->s2,sttop(&obj->s1));
            stpop(&obj->s1);
        }
    }
    return sttop(&obj->s2);
}

bool myqueueempty(myqueue* obj) {
    return (stempty(&obj->s1)) && (stempty(&obj->s2));
}

void myqueuefree(myqueue* obj) {
    if(obj)
        free(obj);
    obj=null;
}

四、设计循环队列

        设计循环队列，这里使用数组来设计

这里会设计到的一些问题：

        插入数据，如何判断空间是否满了？       

这里多申请一个空间，便于判断空间是否满了

        删除数据，如何去删？

这里，删除front指向的数据，就是队头数据

详细代码如下：

typedef struct {
    int* arr;
    int front;
    int rear;
    int num;
} mycircularqueue;

mycircularqueue* mycircularqueuecreate(int k) {
    mycircularqueue* pq = (mycircularqueue*)malloc(sizeof(mycircularqueue));
    pq->arr = malloc((k + 1) * sizeof(int));
    pq->front = pq->rear = 0;
    pq->num = k;
    return pq;
}

bool mycircularqueueisempty(mycircularqueue* obj) {

    return (obj->rear == obj->front);
}

bool mycircularqueueisfull(mycircularqueue* obj) {
    return (obj->rear + 1) % (obj->num + 1) == obj->front;
}

bool mycircularqueueenqueue(mycircularqueue* obj, int value) {

    if (mycircularqueueisfull(obj)) // 队列满了
    {
        return false;
    }
    // 插入数据
    obj->arr[obj->rear++] = value;
    obj->rear %= (obj->num + 1);
    return true;
}

bool mycircularqueuedequeue(mycircularqueue* obj) {
    if (mycircularqueueisempty(obj)) {
        return false;
    }
    obj->front++;
    obj->front %= (obj->num + 1);
    return true;
}

int mycircularqueuefront(mycircularqueue* obj) {
    if (mycircularqueueisempty(obj))
        return -1;
    return obj->arr[obj->front];
}

int mycircularqueuerear(mycircularqueue* obj) {
    if (mycircularqueueisempty(obj))
        return -1;
    int ret=obj->rear-1;
    if(obj->rear==0)
    {
        ret=obj->num;
    }
    return obj->arr[ret];
}

void mycircularqueuefree(mycircularqueue* obj) {
    free(obj->arr);
    free(obj);
    obj = null;
}

感谢各位大佬支持并指出问题，

                        如果本篇内容对你有帮助，可以一键三连支持以下，感谢支持！！！