目录

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;elsereturn (&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的数据导入到s2if(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;
}