文章目录
- 一、有效的括号
- 二、用队列实现栈
- 三、用栈实现队列
- 四、设计循环队列
一、有效的括号
(链接：ValidParentheses)
这道题用栈这种数据结构解决最好，因为栈有后进先出的性质。简单分析一下这道题：所给字符串不是空的也就是一定至少存在一个括号，而且字符串中只能含有’(‘、’)‘、’{‘、’}‘、’[‘、’]'这六种字符。我们要根据题目给的实例，运用栈来解决这道题：
bool isValid(char* s)
{ST st;STInit(&st);while (*s){if (*s == '('|| *s == '['|| *s == '{'){STPush(&st, *s);}else{if (STEmpty(&st))return false;char top = STTop(&st);STPop(&st);if ((*s == ')' && top != '(')|| (*s == ']' && top != '[')|| (*s == '}' && top != '{')){return false;}}s++;}char ret = STEmpty(&st);STDestroy(&st);return ret;
}
二、用队列实现栈
(链接：ImplementStackUsingQueues)
这道题是要用队列来实现栈，首先我们要了解到队列的性质是先进先出，而栈的性质是后进先出。那么就需要两个队列才能实现栈：
//用两个队列来实现栈
typedef struct
{Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate()
{//为自主实现的栈结构动态开辟空间MyStack* st = (MyStack*)malloc(sizeof(MyStack));if (st == NULL){exit(1);}//初始化两个队列QueueInit(&st->q1);QueueInit(&st->q2);return st;
}void myStackPush(MyStack* obj, int x)
{assert(obj != NULL);if (!QueueEmpty(&obj->q1)){QueuePush(&obj->q1, x);}else{QueuePush(&obj->q2, x);}
}int myStackPop(MyStack* obj)
{assert(obj != NULL);Queue* QEmpty = &obj->q1;Queue* QNonEmpty = &obj->q2;if (!QueueEmpty(&obj->q1)){QEmpty = &obj->q2;QNonEmpty = &obj->q1;}//将QNonEmpty队列的前size-1个数据倒入QEmpty队列中while (QueueSize(QNonEmpty) > 1){QueuePush(QEmpty, QueueFront(QNonEmpty));QueuePop(QNonEmpty);}//记录下QNonEmpty队列的队头元素int top = QueueFront(QNonEmpty);//移除并返回队头元素(即模拟返回栈的栈顶元素)QueuePop(QNonEmpty);return top;
}int myStackTop(MyStack* obj)
{assert(obj != NULL);if (!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}bool myStackEmpty(MyStack* obj)
{assert(obj != NULL);return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj)
{assert(obj != NULL);QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}
注意：上面是用两个队列来实现栈的数据结构，MyStack是匿名结构struct 的重命名。MyStack的成员不是队列指针，而是队列结构体变量，所以在myStackCreake中为MyStack动态开辟的空间大小是为两个队列结构体变量开辟的，这样做的好处是可以取q1和q2的地址，方便我们直接可以修改队列q1和q2。当然也可以在MyStack中定义两个队列指针，但这样做的话就要单独为q1和q2动态开辟空间：
typedef struct
{Queue* q1;Queue* q2;
} MyStack;MyStack* myStackCreate()
{MyStack* st = (MyStack*)malloc(sizeof(MyStack));if (st == NULL){exit(1);}st->q1 = (Queue*)malloc(sizeof(Queue));st->q2 = (Queue*)malloc(sizeof(Queue));QueueInit(st->q1);QueueInit(st->q2);return st;
}
第一种定义方式：
第二种定义方式：
注意：如果采用上面这种方式定义MyStack，则后面的函数都要做出相应的调整。在最后销毁自定义的栈时要先释放MyStack中的两个队列q1和q2，最后才销毁obj。因为q1和q2在后面通过QueuePush动态开辟了空间，则要通过obj才能找到q1和q2。所以要先销毁q1和q2，最后才释放obj。当然在做这题的基础上，要先实现一个队列才行。
三、用栈实现队列
(链接：ImplementQueueUsingStacks)
这道题就是上面一道题的兄弟题，要求我们用栈来实现队列。
//用两个栈来实现队列
typedef struct
{ST pushst;ST popst;
}MyQueue;MyQueue* myQueueCreate()
{MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));if (q == NULL){perror("malloc fail!");return NULL;}STInit(&q->pushst);STInit(&q->popst);return q;
}void myQueuePush(MyQueue* obj, int x)
{assert(obj != NULL);STPush(&obj->pushst, x);
}int myQueuePeek(MyQueue* obj)
{assert(obj != NULL);//如果popst里没有数据,则从pushst里倒数据到popst中if (STEmpty(&obj->popst)){while (!STEmpty(&obj->pushst)){STPush(&obj->popst, STTop(&obj->pushst));STPop(&obj->pushst);}}//返回popst的栈顶元素(即模拟队列出队头数据)return STTop(&obj->popst);
}int myQueuePop(MyQueue* obj)
{assert(obj != NULL);int front = myQueuePeek(obj);STPop(&obj->popst);return front;
}bool myQueueEmpty(MyQueue* obj)
{assert(obj != NULL);return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
}void myQueueFree(MyQueue* obj)
{assert(obj != NULL);STDestroy(&obj->pushst);STDestroy(&obj->popst);free(obj);
}
与栈实现队列很相似，这里需要借助两个栈相互倒数据才能实现队列。注意：上面是先实现myQueuePeek函数，即返回队头的数据但不从队头出数据。而后的myQueuePop函数正好可以调用myQueuePeek函数来获取队头的数据，但myQueuePop函数不仅会返回队头数据，而且还会将队头的数据出队。
四、设计循环队列
(链接：DesignCircularQueue)
实际中还有一种特殊的队列叫循环队列，环形队列首尾相连成环，环形队列可以使用数组实现，也可以使用循环链表实现：
💡思考：队列满的情况下，为什么Q.rear 不存储数据?
答：为了能使用 Q.rear == Q.front 来区别是队空还是队满，我们常常认为出现左图时的情况为队空，而出现右图的情况是队满。即: rear+1==front就表示队满。试想：如果(b)图中Q.rear位置再存储一个数据a6进去，那么Q.rear就会指向a1，此时Q.front也指向a1；由(a)图中一开始Q.front == Q.rear就表示队列为空，那么此时Q.front也等于Q.rear，这就矛盾了。所以循环队列中要留一个位置用来表示队满。
这里我们用数组来实现循环队列，但是队列就有一个问题：数组不像循环链表一样有首尾指针相连，但是我们选择数组是有一定好处的。当然链表也是可以实现循环队列的，要具体问题具体分析。那如何在数组中实现循环队列呢？看下图：
当数组中rear到达下标为5的位置时说明队列满了，那么就要删除数据留出空间才能继续存储数据；删除一个数据就直接让front+1即可，因为是模拟队列的先进先出，所以要从队头出数据。此时再入数据就要从rear的位置入，问题是入了数据后，rear+1就出了数组的下标范围，我们应该让rear回到0下标的位置才能真正实现循环队列：（注意：k是题目要求存储的元素个数）
当循环队列满了就要出数据后才能有空间继续入数据：
出数据了此时队列就不满了，那就可以继续往里入数据了，问题是要怎么让rear回到下标为0的位置？
答案是：🍓rear = （rear+1)%(k+1)🍓
这是一个很妙的公式，通过这个公式就可以解决让rear回到0下标处的问题，让队列变成循环队列。
typedef struct
{int* arr;int front;int rear;int k;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k)
{MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if (q == NULL){perror("malloc fail!");return NULL;}q->arr = (int*)malloc(sizeof(int)*(k + 1));if (q->arr == NULL){perror("Arr malloc fail!");return NULL;}q->front = q->rear = 0;q->k = k;return q;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{assert(obj != NULL);return obj->front == obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{assert(obj != NULL);return (obj->rear + 1) % (obj->k + 1) == obj->front;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{assert(obj != NULL);if (myCircularQueueIsFull(obj)){return false;}obj->arr[obj->rear] = value;obj->rear = (obj->rear + 1) % (obj->k + 1);return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{assert(obj != NULL);if (myCircularQueueIsEmpty(obj)){return false;}obj->front = (obj->front + 1) % (obj->k + 1);return true;
}
int myCircularQueueFront(MyCircularQueue* obj)
{assert(obj != NULL);if (myCircularQueueIsEmpty(obj)){return -1;}return obj->arr[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj)
{assert(obj != NULL);if (myCircularQueueIsEmpty(obj)){return -1;}return obj->arr[(obj->rear + obj->k) % (obj->k + 1)];
}
void myCircularQueueFree(MyCircularQueue* obj)
{assert(obj != NULL);free(obj->arr);free(obj);
}
不管是插入元素，还是移除元素都要提前判断队列是否满了或是空的。返回队头或是队尾的元素也是一样的，要提前判断队列是否为空。注意：上面myCircularQueueRear函数是用来返回队尾元素的。如果队列不为空，则队尾元素的下标可以表示为：
🔥(rear + k) % (k + 1)🔥
这也是一个很妙的公式，可以解决rear在下标为0的位置时，则队尾元素是在数组的末尾位置。
