栈和队列

一、对于模仿栈应用何种模型

1.程序表：尾插尾删很快，缓存利用率高，然而要扩容

2.单链表：应用链表头作为栈顶来插入删除数据也很快

3.带头双向循环链表：也能够，工夫也是O(1)

二、栈的模仿实现

//"stack.h"typedef int type;typedef struct stack{    type* a;    int top;    int capacity;}st;//stack.c#include"stack.h"void st_init(st* sta){    assert(sta);    sta->a = NULL;    sta->top = 0;//数组下标的意思，是数据下一个下标，外面没有值;top = -1,则是top指向最初一个元素    sta->capacity = 0;}void st_push(st* sta, type x){    assert(sta);    if (sta->top == sta->capacity)    {        //满了        int newcapa = sta->capacity == 0 ? 4 : 2 * sta->capacity;        type* t = realloc(sta->a, sizeof(type) * newcapa);//扩容；如果a== NULL，它的行为就和malloc一样        if (t == NULL)        {            printf("realloc fail\n");            exit(-1);        }        sta->a = t;        sta->capacity = newcapa;    }    sta->a[sta->top] = x;    ++sta->top;}void st_destroy(st* sta){    assert(sta);    free(sta->a);    sta->a = NULL;    sta->top = 0;    sta->capacity = 0;}void st_pop(st* sta){    assert(sta);    assert(sta->top > 0);    sta->top--;}type st_top(st* sta){    assert(sta);    assert(sta->top > 0);    return sta->a[sta->top - 1];}bool st_empty(st* sta){    assert(sta);    return sta->top == 0;}int st_size(st* sta){    assert(sta);    return sta->top; }

三、根底oj

1.无效的括号

https://leetcode.cn/problems/valid-parentheses/

给定一个只包含 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否无效。

无效字符串需满足：左括号必须用雷同类型的右括号闭合。左括号必须以正确的程序闭合。每个右括号都有一个对应的雷同类型的左括号。

思路：做括号入栈；有括号就和出栈的括号匹配

bool isValid(string s) {    if(s.size()%2 != 0 )return false;    stack<char>st;    for(auto x:s)    {        if(x == '(' || x=='[' ||x=='{')            st.push(x);        else        {            if(st.empty())return false;            if(st.top() == '(' && x==')')            {                st.pop();                continue;            }                            else if(st.top() == '[' && x==']')            {                st.pop();                continue;            }            else if(st.top() == '{' && x=='}')            {                st.pop();                continue;            }            else                 return false;        }    }  if(st.empty())       return true;  return false; }

2.栈的压入、弹出序列

https://www.nowcoder.com/exam/company?tag=581)

输出两个整数序列，第一个序列示意栈的压入程序，请判断第二个序列是否可能为该栈的弹出程序。假如压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入程序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

bool IsPopOrder(vector<int> pushV,vector<int> popV) {    stack<int>st;    int j = 0;    for(auto x:pushV)    {        st.push(x);        while(!st.empty() && st.top() == popV[j])        {            st.pop();            ++j;        }    }    if(st.empty())        return true;    return false;}

3.用队列实现栈

https://leetcode.cn/problems/implement-stack-using-queues/

请你仅应用两个队列实现一个后入先出（LIFO）的栈，并反对一般栈的全副四种操作（push、top、pop 和 empty）

typedef int type;struct queuenode{    struct queue* next;    type data;};typedef struct queue{    struct queuenode* head;    struct queuenode* tail;}queue;void queue_init(queue* q){    assert(q);    q->head = NULL;    q->tail = NULL;}void queue_destroy(queue* q){    assert(q);    struct queuenode* cur = q->head;    while (cur != NULL)    {        struct queuenode* next = cur->next;        free(cur);        cur = next;    }    q->head = q->tail = NULL;}void queue_push(queue* q, type x){    assert(q);    struct queuenode* newnode = (struct queuenode*)malloc(sizeof(struct queuenode));    newnode->data = x;    newnode->next = NULL;        if (q->head == NULL)    {        q->head = q->tail = newnode;    }    else    {        q->tail->next = newnode;        q->tail = newnode;    }}void queue_pop(queue* q){    assert(q);    assert(q->head);    if (q->head == q->tail)    {        free(q->head);        q->head = q->tail = NULL;    }    else    {        struct queuenode* next = q->head->next;        free(q->head);        q->head = next;    }}bool queue_empty(queue* q){    assert(q);    return q->head == NULL;}struct queuenode* buy_node(type x){    struct queuenode* newnode = (struct queuenode*)malloc(sizeof(struct queuenode));    newnode->data = x;    newnode->next = NULL;    return newnode;}type queue_back(queue* q){    assert(q);    assert(q->tail);    return q->tail->data;}type queue_front(queue* q){    assert(q);    assert(q->head);    return q->head->data;}int queue_size(queue* q){    if (q->head == NULL)return 0;    if (q->head == q->tail)return 1;    struct queuenode* t = q->head;    int count = 0;    while (t != NULL)    {        ++count;        t = t->next;    }    return count;}typedef struct {    queue q1;    queue q2;} MyStack;MyStack* myStackCreate() {    MyStack *st = (MyStack*)malloc(sizeof(MyStack));    queue_init(&st->q1);    queue_init(&st->q2);    return st;}void myStackPush(MyStack* obj, int x) {    if(!queue_empty(&obj->q1))    {        queue_push(&obj->q1, x);    }    else    {        queue_push(&obj->q2, x);    }}int myStackPop(MyStack* obj) {    queue* aempty = &obj->q1;    queue* noempty = &obj->q2;    if(!queue_empty(&obj->q1))    {        aempty = &obj->q2;        noempty = &obj->q1;    }    while(queue_size(noempty)>1)    {        queue_push(aempty,queue_front(noempty));        queue_pop(noempty);    }    int top = queue_front(noempty);    queue_pop(noempty);    return top;}int myStackTop(MyStack* obj) {    if(!queue_empty(&obj->q1))    {        return queue_back(&obj->q1);    }    else      {        return queue_back(&obj->q2);    }}bool myStackEmpty(MyStack* obj) {    return queue_empty(&obj->q1)&&queue_empty(&obj->q2);}void myStackFree(MyStack* obj) {    queue_destroy(&obj->q1);    queue_destroy(&obj->q2);    free(obj);}

4.用栈实现队列

https://leetcode.cn/problems/implement-queue-using-stacks/

请你仅应用两个栈实现先入先出队列。队列该当反对个别队列反对的所有操作（push、pop、peek、empty）

typedef int type;typedef struct stack{    type* a;    int top;    int capacity;}st; typedef struct {    st pushst;    st popst;} MyQueue;void st_init(st* sta){    assert(sta);    sta->a = NULL;    sta->top = 0;//数组下标的意思，是数据下一个下标，外面没有值;top = -1,则是top指向最初一个元素    sta->capacity = 0;}void st_push(st* sta, type x){    assert(sta);    if (sta->top == sta->capacity)    {        //满了        int newcapa = sta->capacity == 0 ? 4 : 2 * sta->capacity;        type* t = realloc(sta->a, sizeof(type) * newcapa);//扩容；如果a== NULL，它的行为就和malloc一样        if (t == NULL)        {            printf("realloc fail\n");            exit(-1);        }        sta->a = t;        sta->capacity = newcapa;    }    sta->a[sta->top] = x;    ++sta->top;}void st_destroy(st* sta){    assert(sta);    free(sta->a);    sta->a = NULL;    sta->top = 0;    sta->capacity = 0;}void st_pop(st* sta){    assert(sta);    assert(sta->top > 0);    sta->top--;}type st_top(st* sta){    assert(sta);    assert(sta->top > 0);    return sta->a[sta->top - 1];}bool st_empty(st* sta){    assert(sta);    return sta->top == 0;}int st_size(st* sta){    assert(sta);    return sta->top; }MyQueue* myQueueCreate() {    MyQueue * q = (MyQueue*)malloc(sizeof(MyQueue));    st_init(&q->popst);    st_init(&q->pushst);    return q;}void myQueuePush(MyQueue* obj, int x) {    st_push(&obj->pushst, x);}int myQueuePop(MyQueue* obj) {    if(st_empty(&obj->popst))    {        while(!st_empty(&obj->pushst))        {            st_push(&obj->popst, st_top(&obj->pushst));            st_pop(&obj->pushst);        }    }    type x = st_top(&obj->popst);    st_pop(&obj->popst);    return x;}int myQueuePeek(MyQueue* obj) {    if(st_empty(&obj->popst))    {        while(!st_empty(&obj->pushst))        {            st_push(&obj->popst,st_top(&obj->pushst));            st_pop(&obj->pushst);        }    }    return st_top(&obj->popst);}bool myQueueEmpty(MyQueue* obj) {    return st_empty(&obj->pushst) && st_empty(&obj->popst);}void myQueueFree(MyQueue* obj) {    st_destroy(&obj->popst);    st_destroy(&obj->pushst);    free(obj);}

5.设计循环队列

https://leetcode.cn/problems/design-circular-queue/

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作体现基于 FIFO（先进先出）准则并且队尾被连贯在队首之后以造成一个循环。它也被称为“环形缓冲器”。

循环队列的一个益处是咱们能够利用这个队列之前用过的空间。在一个一般队列里，一旦一个队列满了，咱们就不能插入下一个元素，即便在队列后面仍有空间。然而应用循环队列，咱们能应用这些空间去存储新的值。

思路：无论是链表还是数组模仿，都须要空一个格子，来代表曾经满了的状况。head和tail在同一地位时，代表队列为空。tail的下一个地位是head代表队列曾经满了。要存x个数据，就须要x+1的空间。

#include<stdbool.h>typedef struct {    int*a;    int head;    int tail;    int k;} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {    MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));    q->a = (int *)malloc(sizeof(int)* (k + 1));    q->head = q->tail = 0;    q->k = k;    return q;}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {    return obj->head == obj->tail;}bool myCircularQueueIsFull(MyCircularQueue* obj) {    return (obj->tail + 1)%(obj->k +1) == obj->head;}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//在队列中加数据    if(myCircularQueueIsFull(obj))        return false;    obj->a[obj->tail] = value;    obj->tail = (obj->tail + 1)%(obj->k + 1);    return true;}bool myCircularQueueDeQueue(MyCircularQueue* obj) {    if(myCircularQueueIsEmpty(obj))        return false;    obj->head = (obj->head + 1)%(obj->k + 1);    return true;}int myCircularQueueFront(MyCircularQueue* obj) {    if(myCircularQueueIsEmpty(obj))        return -1;    return obj->a[obj->head];}int myCircularQueueRear(MyCircularQueue* obj) {    if(myCircularQueueIsEmpty(obj))        return -1;    return obj->a[(obj->tail + obj-> k)%(obj->k + 1)];//留神这里，(tail - 1 + k + 1)%(k + 1)，因为tail-1会小于0，所以须要加上数组长度} void myCircularQueueFree(MyCircularQueue* obj) {    free(obj->a);    free(obj);}

四、模仿队列应用的模型

如果应用数组的话，须要在数组头插入删除数据，效率低。所以这里应用单链表实现，并且保护它的尾指针。将队列的头指针和尾指针放入构造体，这样的话批改它们的时候就不须要传二级指针了，而只须要构造体的一级指针。

五、模仿实现队列

//queue.htypedef int type;struct queuenode{    struct queue* next;    type data;};//将指针放在一个构造体中，这样批改他们时就不须要二级指针，而是只须要构造体的一级指针就能够了typedef struct queue{    struct queuenode* head;    struct queuenode* tail;}queue;//queue.c#define _CRT_SECURE_NO_WARNINGS 1 #include"queue.h"void queue_init(queue* q){    assert(q);    q->head = NULL;    q->tail = NULL;}void queue_destroy(queue* q){    assert(q);    struct queuenode* cur = q->head;    while (cur != NULL)    {        struct queuenode* next = cur->next;        free(cur);        cur = next;    }    q->head = q->tail = NULL;}void queue_push(queue* q, type x){    assert(q);    struct queuenode* newnode = (struct queuenode*)malloc(sizeof(struct queuenode));    newnode->data = x;    newnode->next = NULL;        if (q->head == NULL)    {        q->head = q->tail = newnode;    }    else    {        q->tail->next = newnode;        q->tail = newnode;    }}void queue_pop(queue* q){    assert(q);    assert(q->head);    if (q->head == q->tail)    {        free(q->head);        q->head = q->tail = NULL;    }    else    {        struct queuenode* next = q->head->next;        free(q->head);        q->head = next;    }}bool queue_empty(queue* q){    assert(q);    return q->head == NULL;}struct queuenode* buy_node(type x){    struct queuenode* newnode = (struct queuenode*)malloc(sizeof(struct queuenode));    newnode->data = x;    newnode->next = NULL;    return newnode;}type queue_back(queue* q){    assert(q);    assert(q->tail);    return q->tail->data;}type queue_front(queue* q){    assert(q);    assert(q->head);    return q->head->data;}int queue_size(queue* q){    if (q->head == NULL)return 0;    if (q->head == q->tail)return 1;    struct queuenode* t = q->head;    int count = 0;    while (t != NULL)    {        ++count;        t = t->next;    }    return count;}