目录

0.写在前面

1.leetcode.20 有效的括号

2.leetcode.225 用队列实现栈

3.用栈实现队列

4.设计循环队列

0.写在前面

这些题目所用语言为C语言，由于C语言未提供栈和队列的数据结构，所以需要我们手动实现栈和队列。此外熟练掌握栈和队列的性质对解题尤为重要。如果忘记了栈和队列的使用方法可在此直接跳转到栈和队列详解篇。

＜栈＞的概念&结构&实现【C语言版】http://t.csdn.cn/lqe2X＜队列＞的概念&结构&实现【C语言版】http://t.csdn.cn/iXiZI

1.leetcode.20 有效的括号

OJ链接：有效的括号（点此跳转）

解题思路：遍历字符串，如果碰到 ‘ ( ‘ 或 ‘ [ ‘ 或 ‘ { ‘ 就入栈；如果碰到字符是 ‘ ) ‘ ，栈顶的元素又是 ‘ ( ‘，就将栈顶的元素出栈。其他两种情况与之类似。

解题实战：

typedef char STDataType;typedef struct Stack{STDataType* a;  //动态开辟数组int capacity; //记录栈的容量大小int top; //记录栈顶的位置}Stack;//栈的初始化void StackInit(Stack* ps);//释放动态开辟的内存void StackDestroy(Stack* ps);//压栈void StackPush(Stack* ps, STDataType data);//出栈void StackPop(Stack* ps);//读取栈顶的元素STDataType StackTop(Stack* ps);//判断栈是否为空bool StackEmpty(Stack* ps);//栈存储的数据个数int StackSize(Stack* ps);void StackInit(Stack* ps){assert(ps);//初始化时，可附初值，也可置空ps->a = NULL;ps->capacity = 0;ps->top = 0;}void StackDestroy(Stack* ps){assert(ps);//若并未对ps->a申请内存，则无需释放if (ps->capacity == 0)return;//释放free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;}void StackPush(Stack* ps,STDataType data){assert(ps);//若容量大小等于数据个数，则说明栈已满，需扩容if (ps->capacity == ps->top){//若为第一次扩容，则大小为4，否则每次扩大2倍int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}//压栈ps->a[ps->top] = data;ps->top++;}void StackPop(Stack* ps){assert(ps);assert(!StackEmpty(ps));//出栈ps->top--;}STDataType StackTop(Stack* ps){assert(ps);assert(!StackEmpty(ps));//返回栈顶的数据return ps->a[ps->top - 1];}bool StackEmpty(Stack* ps){assert(ps);//返回topreturn ps->top == 0;}int StackSize(Stack* ps){assert(ps);return ps->top;}bool isValid(char* s) {    Stack ST;    StackInit(&ST);    int pos=0;    //遍历字符串，遇到'\0'结束    while(*(s+pos) != '\0')    {        if(*(s+pos) == '(' || *(s+pos) == '[' || *(s+pos) == '{')        {            StackPush(&ST,*(s+pos));        }        else        {            if(StackEmpty(&ST))                return false;            if((ST.top != 0) &&               (*(s+pos) == ')' && StackTop(&ST) == '(')||               (*(s+pos) == ']' && StackTop(&ST) == '[')||               (*(s+pos) == '}' && StackTop(&ST) == '{'))            {                StackPop(&ST);            }            else            {                return false;            }        }         pos++;    }    if( StackEmpty(&ST) )    {        return true;    }    else    {        return false;    }}

2.leetcode.225 用队列实现栈

OJ链接：用队列实现栈

解题思路：首先我们要清楚栈和队列的性质：

栈：先进后出。只在尾部删数据。

队列：先进先出。只在头部删数据。

也就是说，添加数据时，两个是一样的，区别在于删数据时。栈要pop一个数据时，其实pop的是队尾的数据，而不巧的是，队列不能在队尾pop数据。所以此时，我们用两个队列来完成。

栈的结构定义用两个队列来实现。

typedef struct {    Queue q1;    Queue q2;    int size;} MyStack;

使用两个队列的目的是，其中一个队列用来存储数据，另外一个空的队列在pop的时候用来接收非空的队列的数据。非空队列将数据全部拷贝到空队列，只留下一个队尾的数据，此时，队列只剩一个元素，它既在队尾也在队头，所以就可以pop了。

解题实战：

typedef int QDataType;typedef struct QueueNode{QDataType data; //存储的数据struct QueueNode* next; //记录下一个结点的位置}QNode;typedef struct Queue{QNode* head; //记录队头的位置QNode* tail; //记录队尾的位置int size; //记录队列的长度}Queue;//队列的初始化void QueueInit(Queue* pq);//释放malloc出的内存void QueueDestroy(Queue* pq);//入队void QueuePush(Queue* pq, QDataType x);//出队void QueuePop(Queue* pq);//获取队头的数据QDataType QueueFront(Queue* pq);//获取队尾的数据QDataType QueueBack(Queue* pq);//判断队列是否为空bool QueueEmpty(Queue* pq);//队列数据的个数int QueueSize(Queue* pq);void QueueInit(Queue* pq){assert(pq);pq->head = NULL;pq->tail = NULL;pq->size = 0;}void QueueDestroy(Queue* pq){assert(pq);//用cur找尾QNode* cur = pq->head;while (cur){QNode* del = cur;cur = cur->next;free(del);}pq->size = 0;pq->head = pq->tail = NULL;}void QueuePush(Queue* pq,QDataType data){assert(pq);QNode* newNode = (QNode*)malloc(sizeof(QNode));if (newNode == NULL){perror("malloc fail");exit(-1);}//初始化结点newNode->data = data;newNode->next = NULL;if (pq->tail == NULL){//队列为空时入队pq->head = newNode;pq->tail = newNode;}else{//队列不为空时入队pq->tail->next = newNode;pq->tail = newNode;}pq->size++;}void QueuePop(Queue* pq){assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){//只有一个结点时free(pq->head);pq->head = pq->tail = NULL;}else{//一般情况QNode* del = pq->head;pq->head = pq->head->next;free(del);}pq->size--;}QDataType QueueFront(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->head->data;}QDataType QueueBack(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;}bool QueueEmpty(Queue* pq){assert(pq);//return pq->size==0;return pq->head == NULL && pq->tail == NULL;}int QueueSize(Queue* pq){assert(pq);return pq->size;}typedef struct {    Queue q1;    Queue q2;    int size;} MyStack;MyStack* myStackCreate() {    MyStack* ps=(MyStack*)malloc(sizeof(MyStack));    QueueInit(&ps->q1);    QueueInit(&ps->q2);    ps->size=0;    return ps;}void myStackPush(MyStack* obj, int x) {    //找一个不为空的队列来push数据    Queue* noneQueue=(&obj->q1)->size == 0?&obj->q2:&obj->q1;    QueuePush(noneQueue,x);    obj->size++;}int myStackPop(MyStack* obj) {    //找空队列    if ((obj->q2).size == 0)    {        QDataType top;        //复制数据        while ((&obj->q1)->size > 1)        {            top = QueueFront(&obj->q1);            QueuePop(&obj->q1);            QueuePush(&obj->q2,top);        }        top=QueueFront(&obj->q1);        QueuePop(&obj->q1);        obj->size--;        return top;    }    else    {        QDataType top;        //复制数据        while ((&obj->q2)->size > 1)        {            top = QueueFront(&obj->q2);            QueuePop(&obj->q2);            QueuePush(&obj->q1,top);        }        top = QueueFront(&obj->q2);        QueuePop(&obj->q2);        obj->size--;        return top;    } }                                        int myStackTop(MyStack* obj) {        if ((&obj->q1)->size != 0)        return (&obj->q1)->tail->data;    else        return (&obj->q2)->tail->data;}bool myStackEmpty(MyStack* obj) {    return !obj->size;}void myStackFree(MyStack* obj) {    QueueDestroy(&obj->q1);    QueueDestroy(&obj->q2);    free(obj);    obj=NULL;}

3.leetcode.232 用栈实现队列

OJ链接：用栈实现队列

解题思路：同上一题的思路，本题也是用两个栈实现队列。其中s1用来push，s2用来pop和peek。与上一题不同的是，这次pop时，不用一直将s1的数据导入到s2中。而是当s2为空时再导入。

解题实战：

typedef int STDataType;typedef struct Stack{STDataType* a;  //动态开辟数组int capacity; //记录栈的容量大小int top; //记录栈顶的位置}Stack;//栈的初始化void StackInit(Stack* ps);//释放动态开辟的内存void StackDestroy(Stack* ps);//压栈void StackPush(Stack* ps, STDataType data);//出栈void StackPop(Stack* ps);//读取栈顶的元素STDataType StackTop(Stack* ps);//判断栈是否为空bool StackEmpty(Stack* ps);//栈存储的数据个数int StackSize(Stack* ps);void StackInit(Stack* ps){assert(ps);//初始化时，可附初值，也可置空ps->a = NULL;ps->capacity = 0;ps->top = 0;}void StackDestroy(Stack* ps){assert(ps);//若并未对ps->a申请内存，则无需释放if (ps->capacity == 0)return;//释放free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;}void StackPush(Stack* ps,STDataType data){assert(ps);//若容量大小等于数据个数，则说明栈已满，需扩容if (ps->capacity == ps->top){//若为第一次扩容，则大小为4，否则每次扩大2倍int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}//压栈ps->a[ps->top] = data;ps->top++;}void StackPop(Stack* ps){assert(ps);assert(!StackEmpty(ps));//出栈ps->top--;}STDataType StackTop(Stack* ps){assert(ps);assert(!StackEmpty(ps));//返回栈顶的数据return ps->a[ps->top - 1];}bool StackEmpty(Stack* ps){assert(ps);//返回topreturn ps->top == 0;}int StackSize(Stack* ps){assert(ps);return ps->top;}typedef struct {    Stack s1; //用来push数据    Stack s2; //用来pop和peek} MyQueue;MyQueue* myQueueCreate() {    MyQueue* myqueue = (MyQueue*)malloc(sizeof(MyQueue));    StackInit(&myqueue->s1);    StackInit(&myqueue->s2);    return myqueue;}void myQueuePush(MyQueue* obj, int x) {    StackPush(&obj->s1, x);}int myQueuePeek(MyQueue* obj) {    //s2不为空时，不用再将s1的数据导入到s2    if(StackEmpty(&obj->s2))    {        //将s1的数据倒着push到s2中        while (!StackEmpty(&obj->s1))        {            STDataType top = StackTop(&obj->s1);            StackPop(&obj->s1);            StackPush(&obj->s2, top);        }    }    //此时s2的数据是逆置的，所以栈顶的数据也就是队头的数据    return StackTop(&obj->s2);}int myQueuePop(MyQueue* obj) {    STDataType top= myQueuePeek(obj);    //此时s2的数据是逆置的，pop s2栈顶的数据，也就是pop队头的数据    StackPop(&obj->s2);    return top;}bool myQueueEmpty(MyQueue* obj) {    return StackEmpty(&obj->s1) && StackEmpty(&obj->s2);}void myQueueFree(MyQueue* obj) {    StackDestroy(&obj->s1);    StackDestroy(&obj->s2);    free(obj);    obj = NULL;

4.leetcode.622 设计循环队列

OJ链接：设计循环队列

解题思路：循环队列与普通的队列就两点差别。

1.增加一个capacity来记录队列的容量

2.队尾与队头相连（称之为循环）

解题实战：

typedef int QDataType;typedef struct QueueNode{QDataType data; //存储的数据struct QueueNode* next; //记录下一个结点的位置}QNode;typedef struct {    QNode* head;    QNode* tail;    int size;    int capacity;} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj);bool myCircularQueueIsFull(MyCircularQueue* obj);MyCircularQueue* myCircularQueueCreate(int k) {    MyCircularQueue* tmp=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));    tmp->head=NULL;    tmp->tail=NULL;    tmp->size=0;    tmp->capacity=k;    return tmp;}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {        if(myCircularQueueIsFull(obj))        return false;    QNode* newNode = (QNode*)malloc(sizeof(QNode));if (newNode == NULL){perror("malloc fail");exit(-1);}newNode->next = NULL;newNode->data = value;if (obj->size == 0){    obj->head = obj->tail = newNode;obj->size++;}else{obj->tail->next = newNode;obj->tail = newNode;        newNode->next=obj->head;obj->size++;}    return true;}bool myCircularQueueDeQueue(MyCircularQueue* obj) {        if(myCircularQueueIsEmpty(obj))        return false;    QNode* cur=obj->head;    obj->head=obj->head->next;    obj->tail->next=obj->head;    free(cur);    obj->size--;    return true;}int myCircularQueueFront(MyCircularQueue* obj) {    if(myCircularQueueIsEmpty(obj))        return -1;    return obj->head->data;}int myCircularQueueRear(MyCircularQueue* obj) {    if(myCircularQueueIsEmpty(obj))        return -1;    return obj->tail->data;}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {    return !obj->size;}bool myCircularQueueIsFull(MyCircularQueue* obj) {    return obj->size==obj->capacity;}void myCircularQueueFree(MyCircularQueue* obj) {    if(myCircularQueueIsEmpty(obj))    {        free(obj);        return;    }    while(obj->head!=obj->tail)    {        QNode* cur=obj->head;        obj->head=obj->head->next;        free(cur);    }    free(obj->head);    free(obj);    obj=NULL;}