数据结构-栈队列OJ题
文章目录
- 一、有效的括号
- 二、用队列实现栈
- 三、用栈实现队列
- 四、设计循环队列
一、有效的括号
(链接：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的位置时，则队尾元素是在数组的末尾位置。