(目录)

---

题目

序号	题目	链接
1	括号匹配问题	LeetCode
2	用队列实现栈	LeetCode
3	用栈实现队列	LeetCode
4	设计循环队列	LeetCode

---

1.括号匹配问题

这个题目比较有意思的点在于可以用栈的方式进行实现，但是由于博主目前学习的数据结构主要是由c语言进行编写，所以在使用栈的时候需要引入栈的相关函数和一些结构体的定义。

题目的具体思路比较简单，将左括号放入堆栈，同时进行字符指针s++，如果遇到右括号则与栈顶的括号进行比较，如果不匹配，则为false，如果匹配则左括号出栈，接着重复步骤继续运行直至*s == '\0’时停止循环，如下：

循环结束后，返回true，另外我们需要考虑字符串里的两种情况：

① “}}”：这种情况进入循环体的时候，栈为空，无法执行StackPush命令，所以进入循环体的时候需要使用StackEmpty函数来判断是否栈为空。

②"{{"：这种情况会导致出循环体的时候，栈不为空，所以直接返回true是错误的，出循环体的时候我们需要用if条件语句来判断*s是否为‘\0’，然后在使用StackEmpty函数即可。

代码如下：

bool isValid(char * s){
    Stack st;
    StackInit(&st);
    bool ret;
    while(*s != '\0')
    {
        if(*s == '[' || *s == '{' || *s == '(')
        {
            StackPush(&st, *s);
            s++;
        }
        else
        {
            if(StackEmpty(&st))
            {
                ret = false;
                break;
            }

            if(StackTop(&st) != '[' && *s == ']')
            {
                ret = false;
                break;
            }

            if(StackTop(&st) != '(' && *s == ')')
            {
                ret = false;
                break;
            }

            if(StackTop(&st) != '{' && *s == '}')
            {
                ret = false;
                break;
            }
            s++;
            StackPop(&st);
        }

    }
    if(*s == '\0')
        ret = StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}

---

2.用队列实现栈

---

同样需要c语言自己造一个轮子来实现队列。

这里提供的思路是用两个队列实现栈的功能，其中应用双队列的目的是为了解决出栈的问题，将非空队列的值导入空队列直至非空队列只剩队尾的时候，执行QueuePop（出队列）即可，如下：

代码如下：

typedef struct {
    Queue _q1;
    Queue _q2;

} MyStack;

/** Initialize your data structure here. */

MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->_q1);
    QueueInit(&pst->_q2);
    return pst;
}

/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->_q1))
    {
        QueuePush(&obj->_q1, x);
    }
    else
    {
        QueuePush(&obj->_q2, x);
    }
}

/** Removes the element on top of the stack and returns that element. */
int myStackPop(MyStack* obj) {
	//注意生命周期的问题，所以定义成指针类型
    Queue *nonEmpty = &obj->_q1;
    Queue *empty = &obj->_q2;
    if(QueueEmpty(&obj->_q1))
    {
        empty = &obj->_q1;
        nonEmpty = &obj->_q2;
    }
    while(QueueSize(nonEmpty)>1)
    {
        QueuePush(empty,QueueFront(nonEmpty));
        QueuePop(nonEmpty);
    }
    int top = QueueFront(nonEmpty);
    QueuePop(nonEmpty);
    return top;
}

/** Get the top element. */
int myStackTop(MyStack* obj) {
    if(QueueEmpty(&obj->_q1))
    {
       return QueueBack(&obj->_q2);
    }
    else
    {
        return QueueBack(&obj->_q1);
    }
}

/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->_q1) && QueueEmpty(&obj->_q2);
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->_q1);
    QueueDestroy(&obj->_q2);
    free(obj);
}

---

3.用栈实现队列

这个题目的思路与“用队列实现栈”的方法一样，用两个栈实现队列，重点也是解决出队列QueuePop的问题，将数据栈倒入临时栈，再将临时栈的栈顶取出就等同于出队列，如下：

typedef struct {
    Stack _DataST;
    Stack _TempST;
} MyQueue;

/** Initialize your data structure here. */

MyQueue* myQueueCreate() {
    MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&pq->_DataST);
    StackInit(&pq->_TempST);
    return pq;
}

/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->_DataST, x);
}

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
    int front = myQueuePeek(obj);
    StackPop(&obj->_TempST);
    return front;
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->_TempST))
    {
        while(StackSize(&obj->_DataST))
        {
            StackPush(&obj->_TempST,StackTop(&obj->_DataST));
            StackPop(&obj->_DataST);
        }
    }
    int front = StackTop(&obj->_TempST);
    return front; 
}

/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->_DataST) && StackEmpty(&obj->_TempST);
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->_DataST);
    StackDestroy(&obj->_TempST);
    free(obj);
}

---

4.设计循环队列

这个题目比较有意思的点在于环形，一般这种队列可以用数组和循环链表进行实现，但是出于方便起见，本题用静态数组（容量不变）实现，一般我们设置的数组大小会比实际的环形多出一个元素，而且多出来的这一个数据并不存放数据，至于为什么，主要是为了区分判空与判满的条件，如下：

有了这个判断条件之后，这个题目也就迎刃而解了，代码如下：

typedef struct {
    int* _data;
    int _front;
    int _rear;
    int _k;
} MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

MyCircularQueue* myCircularQueueCreate(int k) {
     MyCircularQueue* pq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    pq->_data = (int*)malloc(sizeof(int)*(k+1));
    pq->_front = pq->_rear = 0;
    pq->_k = k;
    return pq;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->_data[obj->_rear] = value;
    obj->_rear++;
    //注意当尾下标为k+1的情况
    obj->_rear  %= (obj->_k + 1); 
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj->_front++;
    //同上
    obj->_front %= (obj->_k + 1);
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->_data[obj->_front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    int rear = obj->_rear - 1;
    //注意尾下标为0的情况
    if(rear == -1)
    {
        rear = obj->_k;
    }
    return obj->_data[rear];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->_front == obj->_rear;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->_front == (obj->_rear+1)%(obj->_k + 1); 
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->_data);
    free(obj);
}