文章目录

• 一.对列实现栈
• 二.栈实现对列
• 三.循环对列

一.对列实现栈

题目描述：

关键思路:
要实现的栈有两个对列
当栈出数据时：先把存数据的栈里面的数据一个一个移到另一个栈，直到存数据的栈只有一个数据为止。然后再把最后一个元素出栈。
细节1:存数据的栈移到另一个栈这个过程，需要把栈里面存过的数据出栈。
细节2:只有一个数据的条件是头指针与尾指针相等
补充:
1.判断此栈为空需要判断两个对列都为空
2.释放栈时需要先释放里面的对列，再释放栈
3.出栈的时候需要判断两个对列都不为空的，入栈的时候则不需要考虑。

这是我们所需对列的代码，还得手搓，有需要的直接复制即可。

typedef int QDataType;
typedef struct QListNode
{QDataType val;struct QListNode* next;
}QListNode;
typedef struct Queue
{QListNode* head;QListNode* tail;
}Queue;
void QueueInit(Queue* q)
{assert(q);q->head = NULL;q->tail = NULL;
}
void QueuePush(Queue* q, QDataType data)
{assert(q);if (q->head == NULL){QListNode* NewNode = (QListNode*)malloc(sizeof(QListNode));NewNode->val = data;q->head = q->tail = NewNode;q->head->next = q->tail->next = NULL;}else{QListNode* NewNode = (QListNode*)malloc(sizeof(QListNode));q->tail->next = NewNode;NewNode->val = data;NewNode->next = NULL;q->tail = NewNode;}
}void QueueDestroy(Queue* q)
{assert(q);QListNode* cur = q->head;while (cur != NULL){QListNode* next = cur->next;free(cur);cur = next;}q->head = q->tail = NULL;
}
void QueuePop(Queue* q)
{assert(q);assert(q->head);if (q->head == q->tail){free(q->head);q->head = q->tail = NULL;}else{QListNode* next = q->head->next;free(q->head);q->head = next;}
}
QDataType QueueFront(Queue* q)
{assert(q);assert(q->head);return q->head->val;
}
QDataType QueueBack(Queue* q)
{assert(q);assert(q->tail);return q->tail->val;
}
int QueueSize(Queue* q)
{assert(q);assert(q->head);QListNode* cur = q->head;int count = 0;while (cur){QListNode* next = cur->next;count++;cur = next;}return count;
}
int QueueEmpty(Queue* q)
{assert(q);return q->head == NULL;
}

这是题目让我们写的代码

typedef struct
{Queue one;Queue two;
} MyStack;
MyStack* myStackCreate() 
{MyStack* stack =(MyStack *)malloc(sizeof(MyStack));if(stack == NULL){perror("malloc stack");exit(-1);}QueueInit(&stack->one);QueueInit(&stack->two);return stack;
}
void myStackPush(MyStack* obj, int x) 
{assert(obj);//假设一个对列为空Queue* Empty = &obj->one; Queue* NoEmpty = &obj->two;//如果一个对列不为空if(Empty->head != NULL){Empty = &obj->two;NoEmpty = &obj->one;}QueuePush(NoEmpty,x);
}int myStackPop(MyStack* obj) 
{assert(obj);//假设一个对列为空Queue* Empty = &obj->one; Queue* NoEmpty = &obj->two;//倘若两个对列都为空呢？assert(NoEmpty->head||Empty->head);//都为空才为空。//如果一个对列不为空if(Empty->head != NULL){Empty = &obj->two;NoEmpty = &obj->one;}//移剩下一个结点while(NoEmpty->head!=NoEmpty->tail){QueuePush(Empty,QueueFront(NoEmpty));QueuePop(NoEmpty);//释放的是不为空的对列}QDataType x = QueueFront(NoEmpty);QueuePop(NoEmpty);return x;   
}int myStackTop(MyStack* obj) 
{assert(obj);//假设一个对列为空Queue* Empty = &obj->one; Queue* NoEmpty = &obj->two;if(NoEmpty->head!=NULL){return QueueBack(NoEmpty);//栈返回的是对列的最后一个元素}else{return QueueBack(Empty);}
}bool myStackEmpty(MyStack* obj) 
{assert(obj);return QueueEmpty(&obj->one)&&QueueEmpty(&obj->two);
}void myStackFree(MyStack* obj) 
{QueueDestroy(&obj->one);QueueDestroy(&obj->two);free(obj);
}

二.栈实现对列

题目描述：

关键思路：

出栈思路：
这里的存数据与出数据的栈是固定的，当出数据的栈为空时，再从入数据的栈里面拿数据，否则不能拿数据，而入数据的栈则可以一直入。
实现小技巧:先实现myQueuePeek再实现myQueuePop会简单很多
释放栈的思路:
先释放对列里面的栈，再释放栈。
细节:函数要调用下面的函数，要不就声明一下，要不就把下面的函数放在此函数的上面。

这是我们所需栈的代码，还得手搓，有需要的直接复制即可。

typedef int STDataType;
typedef struct Stack
{STDataType* arr;int size;int capacity;
}Stack;
void StackInit(Stack* ps)
{ps->arr = NULL;ps->capacity = 0;ps->size = 0;
}void StackPush(Stack* ps, STDataType data)
{if (ps->capacity == 0 || ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->arr,sizeof(STDataType)*newcapacity);if (tmp == NULL){perror("StackPush:realloc");return;}else{ps->arr = tmp;ps->capacity = newcapacity;}}ps->arr[ps->size++] = data;
}
void StackPop(Stack* ps)
{assert(ps);assert(ps->size > 0);ps->arr[ps->size - 1];ps->size--;
}
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps->size > 0);return ps->arr[ps->size - 1];
}
int StackSize(Stack* ps)
{assert(ps);return ps->size;
}
int StackEmpty(Stack* ps)
{assert(ps);return ps->size == 0;
}
void StackDestroy(Stack* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->capacity = 0;ps->size = 0;
}

这是目标代码

typedef struct 
{Stack PopStack;Stack PushStack;
} MyQueue;MyQueue* myQueueCreate() 
{MyQueue *newQueue = (MyQueue *)malloc(sizeof(MyQueue));if(newQueue==NULL){perror("malloc fail");exit(-1);}StackInit(&newQueue->PopStack);StackInit(&newQueue->PushStack);return newQueue;
}void myQueuePush(MyQueue* obj, int x) 
{assert(obj);StackPush(&obj->PushStack,x);
}int myQueuePeek(MyQueue* obj) 
{Stack *Pop = &obj->PopStack;Stack *Push =&obj->PushStack;if(StackEmpty(Pop)){while(!StackEmpty(Push)){StackPush(Pop,StackTop(Push));StackPop(Push);}}return StackTop(Pop);
}
int myQueuePop(MyQueue* obj) 
{STDataType x = myQueuePeek(obj);StackPop(&obj->PopStack);return x;
}
bool myQueueEmpty(MyQueue* obj) {assert(obj);return StackEmpty(&obj->PopStack)&&StackEmpty(&obj->PushStack);
}
void myQueueFree(MyQueue* obj) 
{StackDestroy(&obj->PopStack);StackDestroy(&obj->PushStack);free(obj);
}

三.循环对列

题目描述：

顺序表思路:
设置k的长度，要多设置一个，所以实际开辟的长度为k+1
判断对列是否已满:
两种方法:
菜鸡法:
第一种情况:头减尾等于对列长度k
第二种情况:尾减头等于1
大佬的方法:
尾下标加1模上对列长度加一等于头下标
说明:%在这里实际就是达到了循环，并且处理了菜鸡的第一种情况。
返回队尾元素
先判断对列是否为空
然后有两种方法返回
菜鸡法:
第一种情况:尾下标为0返回对列长度k也就是最后一个元素的下标。
注意:我们可是多开了一个元素的哦！
第二种情况:返回尾下标减一
大佬法:
返回尾下标加对列长度模上对列长度加1
注意的细节:
1.为了让对列达到循环的效果每次我们都得模上对列的长度加1
2.释放对列的时候我们要先释放对列里面的顺序表再释放对列！

typedef int QDataType;
typedef struct 
{QDataType *arr;int head;int tail;int k;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) 
{MyCircularQueue *newQueue =(MyCircularQueue *)malloc(sizeof(MyCircularQueue));if(newQueue==NULL){perror("malloc fail");exit(-1);}QDataType* tmp = (QDataType*)malloc(sizeof(QDataType)*(k+1));if(tmp==NULL){perror("malloc fail");exit(-1);}newQueue->arr = tmp;newQueue->tail=newQueue->head=0;newQueue->k=k;return newQueue;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) 
{    //if((obj->tail+1)%(obj->k+1)==obj->head)//{//    return true;// }//如何分开算？可以拿笔验证一下。if(obj->head-obj->tail==1||obj->tail-obj->head==obj->k){return true;}return false;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{return obj->head-obj->tail==0;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{assert(obj);//对列是否已满if(myCircularQueueIsFull(obj)){return false;}obj->arr[obj->tail++]=value;obj->tail%=(obj->k+1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{assert(obj);if(myCircularQueueIsEmpty(obj)){return false;}obj->head++;obj->head%=(obj->k+1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) 
{assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}return obj->arr[obj->head];
}int myCircularQueueRear(MyCircularQueue* obj) 
{assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}if(obj->tail==0)//特殊情况{return obj->arr[obj->k];}else{return obj->arr[obj->tail-1];}//return obj->tail == 0 ? obj->arr[obj->k] : obj->arr[obj->tail-1];//return obj->arr[(obj->tail+obj->k)%(obj->k+1)];
}
void myCircularQueueFree(MyCircularQueue* obj) 
{assert(obj);free(obj->arr);obj->arr = NULL;free(obj);
}