文章目录

1.[有效的括号](https://leetcode.cn/problems/valid-parentheses/description/)1.1 题目要求1.2 利用栈解决

2. [用队列实现栈](https://leetcode.cn/problems/implement-stack-using-queues/description/)2.1 题目要求2.2 用队列实现栈

3.[用栈实现队列](https://leetcode.cn/problems/implement-queue-using-stacks/description/)3.1 题目要求3.2 用栈实现队列

4.[设计循环队列](https://leetcode.cn/problems/design-circular-queue/description/)4.1 题目要求4.2 设计循环队列

1.有效的括号

1.1 题目要求

判断所给字符串的括号是否有效。

有效的条件：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。

1.2 利用栈解决

遍历给定字符串时，当我们遇到左括号时，把它入栈。目的是为了期望在后续的遍历中有一个相同类型的右括号与其匹配。

当我们遍历时遇到的是右括号，此时有3种情况：

1.栈为空，无法匹配返回false。

2.栈不为空，但不是与之匹配的左括号，返回false。

3.栈不为空，是与之匹配的左括号，继续遍历。

在2，3情况下，为了简化书写，我们可以先把栈顶元素出栈，用一个临时变量保存。

如果我们在遍历时都顺利通过，也不能代表这个字符串就是有效的。

比如这种情况：( ( ( ) )

遍历完后，栈中还会剩下(.

为此最后我们还需要判断栈是否为空，不为空返回false，为空返回true。

注意记得销毁栈

typedef struct stack

{ -- -->

char* a;

int size;//写错了，代表top的意思

int capacity;

}stack;

void init(stack* ps)

{

assert(ps);

ps->a = (char*)malloc(sizeof(char)*4);

ps->size = 0;

ps->capacity = 4;

}

bool empty(stack* ps)

{

return ps->size == 0;

}

void push(stack* ps,char x)

{

assert(ps);

if(ps->size == ps->capacity)

{

char* tmp = (char*)realloc(ps->a,sizeof(char)*ps->capacity*2);

if(tmp == NULL)

{

perror("realloc");

exit(-1);

}

ps->a = tmp;

ps->capacity *= 2;

}

ps->a[ps->size] = x;

ps->size+=1;

}

void pop(stack* ps)

{

assert(ps);

assert(ps->size>0);

ps->size -= 1;

}

char Top(stack* ps)

{

assert(ps);

assert(ps->size>0);

return ps->a[ps->size-1];

}

void destory(stack* ps)

{

assert(ps);

free(ps->a);

ps->a = NULL;

ps->size = 0;

ps->capacity = 0;

}

bool isValid(char* s) {

stack st;

init(&st);

while(*s)

{

if(*s == '('||*s == '['||*s == '{')

push(&st,*s);

else if(*s == ')'||*s == ']'||*s == '}')

{

if(empty(&st))

{

destory(&st);

return false;

}

char top = Top(&st);

pop(&st);

if(*s == ')'&&top!='('||*s == ']'&&top!='['||*s == '}'&&top!='{')

{

destory(&st);

return false;

}

}

s+=1;

}

if(!empty(&st))

{

destory(&st);

return false;

}

destory(&st);

return true;

}

2. 用队列实现栈

2.1 题目要求

使用两个队列实现一个后入先出（LIFO）的栈

2.2 用队列实现栈

如何用两个队列来实现栈呢？我们知道队列是先进先出的。

先画两个队列出来。

此时插入了3个数据，为了让这两个队列实现后进先出的效果，我们得充分利用队列的特性。显然如果是栈，出数据是先出3的，但是队列的话是先出1。为了让队列先出3，我们就要把1和2先移动到另一个空队列中。

如此一来，就可以拿到3了。

那么用两个队列实现栈的主要逻辑就出来了。

首先是插入逻辑：有两种情况

1.两个队列都为NULL，随便插入一个队列

2.其中一个队列不为NULL，那么就把数据插入到不为NULL的队列。

然后就是删除逻辑：

在删除时，我们需要把有数据的一方队列的数据转移到没有数据的队列中，直到只剩下一个元素，这就是栈顶元素，用一个临时遍历存储完数据后就可以删除这个栈顶元素了。

再然后的返回栈顶元素：

因为不用删除的缘故，队列又提供返回队尾元素的功能，所以直接返回有数据的那个队尾元素即可。

最后都是一些简单的接口，相信大家没问题的。

<code>typedef struct node

{ -- -->

int data;

struct node* next;

}node;

typedef struct queue

{

node* head;

node* tail;

}queue;

void init(queue* q)

{

assert(q);

q->head = q->tail = NULL;

}

void push(queue* q,int x)

{

assert(q);

node* newnode = (node*)malloc(sizeof(node));

if(newnode == NULL)

{

perror("malloc");

exit(-1);

}

newnode->data = x;

newnode->next = NULL;

if(q->head == NULL)

{

q->head = q->tail = newnode;

}

else

{

q->tail->next = newnode;

q->tail = newnode;

}

}

void pop(queue* q)

{

assert(q);

assert(q->head);

if(q->head == q->tail)

{

free(q->head);

q->head = q->tail = NULL;

}

else

{

node* next = q->head->next;

free(q->head);

q->head = next;

}

}

int size(queue* q)

{

assert(q);

node* cur = q->head;

int count = 0;

while(cur)

{

count+=1;

cur = cur->next;

}

return count;

}

bool empty(queue* q)

{

assert(q);

return q->head == NULL;

}

int top(queue* q)

{

assert(q);

assert(q->head);

return q->head->data;

}

int back(queue* q)

{

assert(q);

assert(q->head);

return q->tail->data;

}

void destory(queue* q)

{

assert(q);

node* cur = q->head;

while(cur)

{

node* next = cur->next;

free(cur);

cur = next;

}

q->head = q->tail = NULL;

}

typedef struct {

queue q1;

queue q2;

} MyStack;

MyStack* myStackCreate() {

MyStack* s = (MyStack*)malloc(sizeof(MyStack));

init(&s->q1);

init(&s->q2);

return s;

}

void myStackPush(MyStack* s, int x) {

if(!empty(&s->q1))

{

push(&s->q1,x);

}

else

{

push(&s->q2,x);

}

}

int myStackPop(MyStack* s) {

queue* em = &s->q1;

queue* noem = &s->q2;

if(!empty(em))

{

em = &s->q2;

noem = &s->q1;

}

while(size(noem)>1)

{

push(em,top(noem));

pop(noem);

}

int t = top(noem);

pop(noem);

return t;

}

int myStackTop(MyStack* s) {

queue* em = &s->q1;

queue* noem = &s->q2;

if(!empty(em))

{

em = &s->q2;

noem = &s->q1;

}

return back(noem);

}

bool myStackEmpty(MyStack* s) {

return empty(&s->q1)&&empty(&s->q2);

}

void myStackFree(MyStack* s) {

destory(&s->q1);

destory(&s->q2);

free(s);

}

3.用栈实现队列

3.1 题目要求

请使用两个栈实现先入先出队列

3.2 用栈实现队列

要用两个后进先出的栈实现先进先出的队列。先看图

为了实现队列，我们要把栈设计为一个进进数据栈，一个出数据栈。

当我们需要删除数据时，因为队列先进先出的特性，要出的数据为1，可是栈顶元素是3，所以我们需要把进数据栈的数据全部移动到出数据栈中，移动完后如图：

这样的话，程序的主体逻辑都出来了。

开始我们入数据的时候，全部都存储到pusht栈中。

然后当我们想要删除数据/读取队首元素时：会有两种情况

1.popt栈为空，那么我们就把pusht栈中的元素全部转移到popt栈。

2.popt栈不为空，直接取popt的栈顶元素就可以了。

为了简化代码，我们可以复用函数。先实现读取队首元素的功能（peek）再在删除队列元素时复用读取对手元素的功能。详见代码

最后都是写简单功能，大家看代码。

<code>typedef struct stack

{ -- -->

int* a;

int size;//写错了，代表top的意思

int capacity;

}stack;

void init(stack* ps)

{

assert(ps);

ps->a = (int*)malloc(sizeof(int)*4);

ps->size = 0;

ps->capacity = 4;

}

bool empty(stack* ps)

{

return ps->size == 0;

}

void push(stack* ps,int x)

{

assert(ps);

if(ps->size == ps->capacity)

{

int* tmp = (int*)realloc(ps->a,sizeof(int)*ps->capacity*2);

if(tmp == NULL)

{

perror("realloc");

exit(-1);

}

ps->a = tmp;

ps->capacity *= 2;

}

ps->a[ps->size] = x;

ps->size+=1;

}

void pop(stack* ps)

{

assert(ps);

assert(ps->size>0);

ps->size -= 1;

}

int Top(stack* ps)

{

assert(ps);

assert(ps->size>0);

return ps->a[ps->size-1];

}

void destory(stack* ps)

{

assert(ps);

free(ps->a);

ps->a = NULL;

ps->size = 0;

ps->capacity = 0;

}

int size(stack* ps)

{

assert(ps);

return ps->size;

}

typedef struct {

stack pusht;

stack popt;

} MyQueue;

MyQueue* myQueueCreate() {

MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));

init(&q->pusht);

init(&q->popt);

return q;

}

void myQueuePush(MyQueue* q, int x) {

push(&q->pusht,x);

}

int myQueuePeek(MyQueue* q) {

if(empty(&q->popt))

{

while(!empty(&q->pusht))

{

push(&q->popt,Top(&q->pusht));

pop(&q->pusht);

}

}

return Top(&q->popt);

}

int myQueuePop(MyQueue* q) {

int top = myQueuePeek(q);

pop(&q->popt);

return top;

}

bool myQueueEmpty(MyQueue* q) {

return empty(&q->pusht)&&empty(&q->popt);

}

void myQueueFree(MyQueue* q) {

destory(&q->pusht);

destory(&q->popt);

free(q);

q = NULL;

}

4.设计循环队列

4.1 题目要求

设计一个大小为k的循环队列

4.2 设计循环队列

简单科普循环队列

这是一个循环队列

下面展示循环队列为空和为满时情形：

tail位置是不存储数据的，代表意思是队尾元素的下一个。

科普完成后，下面就是正式的题目讲解：

在初始化时，我们需要开k+1个空间，因为数组中的tial位是不存储数据的。

先写判断循环队列是否为空和为满的功能，写了两个函数书写其他函数时就比较轻松了。

正如上面所说，tail = head为空

为满的话，考虑到循环因素，我们需要利用取模操作。

为满就一种情况，head在tail前面，但是因为数组不像上面画的那样是一个环，所以为满就有了两种情况：

1.tial在head前面，多种情况

2.tail在head后面，在后面就一种情况，tail为k，head为0

(tail+1)%(k+1) = head就是判断条件。

后面的插入删除都没什么难点了，唯一要注意的就是当head和tial到达k时要注意下一步的操作。

还有返回队尾数据的，tail是指向队尾数据的下一个元素的！

<code>typedef struct { -- -->

int* a;

int head;

int tail;

int k;

} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {

MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));

q->a = (int*)malloc(sizeof(int)*(k+1));

q->head = q->tail = 0;

q->k = k;

return q;

}

//函数声明

bool myCircularQueueIsEmpty(MyCircularQueue* q);

bool myCircularQueueIsFull(MyCircularQueue* q);

bool myCircularQueueEnQueue(MyCircularQueue* q, int value) {

if(myCircularQueueIsFull(q))

return false;

q->a[q->tail] = value;

if(q->tail == q->k)

q->tail = 0;

else

q->tail+=1;

return true;

}

bool myCircularQueueDeQueue(MyCircularQueue* q) {

if(myCircularQueueIsEmpty(q))

return false;

if(q->head == q->k)

q->head = 0;

else

q->head+=1;

return true;

}

int myCircularQueueFront(MyCircularQueue* q) {

if(myCircularQueueIsEmpty(q))

return -1;

return q->a[q->head];

}

int myCircularQueueRear(MyCircularQueue* q) {

if(myCircularQueueIsEmpty(q))

return -1;

if(q->tail == 0)

return q->a[q->k];

else

return q->a[q->tail-1];

}

bool myCircularQueueIsEmpty(MyCircularQueue* q) {

if(q->head == q->tail)

return true;

return false;

}

bool myCircularQueueIsFull(MyCircularQueue* q) {

if((q->tail+1)%(q->k+1) == q->head)

return true;

return false;

}

void myCircularQueueFree(MyCircularQueue* q) {

free(q);

q = NULL;

}

完