力扣刷题：栈和队列OJ篇（上）

大家好，这里是小编的博客频道
小编的博客：就爱学编程

很高兴在CSDN这个大家庭与大家相识，希望能在这里与大家共同进步，共同收获更好的自己！！！

---

废话不多说，我们直接看题。

1.用队列实现栈

（1）题目描述

---

（2）解题思路

• 为了满足栈的特性，即最后入栈的元素最先出栈，在使用队列实现栈时，应满足队列前端的元素是最后入栈的元素。可以使用两个队列实现栈的操作，其中queue 1​ 用于存储栈内的元素，queue 2 作为入栈操作的辅助队列。
• 入栈操作时，首先将元素入队到queue 2，然后将 queue 1 的全部元素依次出队并入队到 queue 2 ，此时 queue 2 的前端的元素即为新入栈的元素，再将queue 1 和 queue 2互换，则 queue 1 的元素即为栈内的元素，queue 1的前端和后端分别对应栈顶和栈底。由于每次入栈操作都确保 queue 1 的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除 queue 1 的前端元素并返回即可，获得栈顶元素操作只需要获得queue 1 的前端元素并返回即可（不移除元素）。由于 queue 1 用于存储栈内的元素，判断栈是否为空时，只需要判断 queue 1 是否为空即可。

代码实现：

typedef int QDatatype;
typedef struct QuequeNode {QDatatype data;struct QuequeNode* next;
}QNode;
typedef struct Queue{QNode* head;			//单链表的头指针作为队头QNode* tail;			//单链表的尾指针作为队尾int size;				//存储队列元素数量
}Que;//初始化队列
void QInit(Que* ps) {assert(ps);ps->head = ps->tail = NULL;ps->size = 0;
}//销毁队列
void QDestroy(Que* ps) {assert(ps);QNode* cur = ps->head;while (cur) {QNode* next = cur->next;free(cur);cur = next;}ps->size = 0;ps->head = ps->tail = NULL;
}//插入数据（从队尾）------入队
void QPush(Que* ps, QDatatype x) {assert(ps);QNode* cur = (QNode*)malloc(sizeof(QNode));if (cur == NULL) {perror("malloc fail");return;}if (ps->head == NULL) {assert(ps->tail == NULL);ps->head = ps->tail = cur;}else {ps->tail->next = cur;		//先赋值ps->tail = cur;				//再更新尾指针}cur->next = NULL;cur->data = x;ps->size++;
}//判空
bool QEmpty(Que* ps) {assert(ps);return (ps->size == 0);
}//删除数据（从对头）------出队
void QPop(Que* ps) {assert(ps);assert(!QEmpty(ps));if (ps->head->next == NULL) {free(ps->head);ps->head = ps->tail = NULL;ps->size = 0;return;}QNode* next = ps->head->next;free(ps->head);ps->head = next;ps->size--;
}//得出队内元素数量
int QSize(Que* ps) {assert(ps);return (ps->size);
}//得到队头元素的数据
QDatatype QFront(Que* ps) {assert(ps && !QEmpty(ps));return (ps->head->data);
}//得到队尾元素的数据
QDatatype QBack(Que* ps) {assert(ps && !QEmpty(ps));return (ps->tail->data);
}typedef struct {Que q1;Que q2;
} MyStack;MyStack* myStackCreate() {MyStack* ptr = (MyStack*)malloc(sizeof(MyStack));if(ptr == NULL){perror("malloc fail");return NULL;}QInit(&ptr->q1);QInit(&ptr->q2);return ptr;
}void myStackPush(MyStack* obj, int x) {if(QEmpty(&obj->q1)){QPush(&obj->q2, x);}else{QPush(&obj->q1, x);}
}int myStackPop(MyStack* obj) {if(QEmpty(&obj->q1)){while(QSize(&obj->q2) > 1){QDatatype temp = QFront(&obj->q2);QPop(&obj->q2);QPush(&obj->q1, temp);}QDatatype top =  QBack(&obj->q2);QPop(&obj->q2);return top;}else{while(QSize(&obj->q1) > 1){QDatatype temp = QFront(&obj->q1);QPop(&obj->q1);QPush(&obj->q2, temp);}QDatatype top =  QBack(&obj->q1);QPop(&obj->q1);return top;}
}int myStackTop(MyStack* obj) {if(QEmpty(&obj->q1)){return QBack(&obj->q2);}return QBack(&obj->q1);
}bool myStackEmpty(MyStack* obj) {return QEmpty(&obj->q1) && QEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {QDestroy(&obj->q1);QDestroy(&obj->q2);free(obj);obj = NULL;
}

---

2.用两个栈实现队列

（1）题目描述

---

（2）解题思路

• 将一个栈当作输入栈，用于压入 push 传入的数据；另一个栈当作输出栈，用于 pop 和 peek 操作。
• 每次pop或peek时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

代码实现：

#define MAXCAPACITY 4typedef int Datastyle;typedef struct stack {Datastyle* a;               int top;int capacity;
}ST;//初始化栈
void STInit(ST* ps) {assert(ps);Datastyle* temp = (Datastyle*)malloc(MAXCAPACITY * sizeof(Datastyle));if (temp == NULL) {perror("malloc fail");exit(-1);}ps->a = temp;ps->capacity = MAXCAPACITY;ps->top = 0;
}//销毁栈
void  STDestory(ST* ps){assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}//插入数据（从栈顶）----（入栈，压栈）
void STPush(ST* ps, Datastyle x) {assert(ps);//判断是否满了if (ps->top == ps->capacity) {Datastyle* temp = (Datastyle*)realloc(ps->a, 2 * ps->capacity * sizeof(Datastyle));				//扩容为当前容量的两倍比较合理if (temp == NULL) {perror("realloc fail");return;}ps->capacity *= 2;ps->a = temp;}ps->a[ps->top++] = x;
}//判空
bool STEmpty(ST* ps) {return (ps->top == 0);
}//删除数据（从栈顶）----（出栈）
void STPop(ST* ps) {assert(ps && !STEmpty(ps));--ps->top;
}//访问栈顶元素
Datastyle STTop(ST* ps) {return ps->a[ps->top - 1];
}//得出栈的元素个数
int STSize(ST* ps) {assert(ps);return ps->top;
}typedef struct {ST stpush;                 //stpush专门用来存储数据，只有在stpop为空时进行出数据至st2ST stpop;                 //stpop专门用来出数据，只有当其为空时从stpush拿出数据进行存储
} MyQueue;MyQueue* myQueueCreate() {MyQueue* ptr = (MyQueue*) malloc(sizeof(MyQueue));if(ptr == NULL){perror("malloc fail");return NULL;}STInit(&ptr->stpush);STInit(&ptr->stpop);return ptr;
}void myQueuePush(MyQueue* obj, int x) {STPush(&obj->stpush, x);
}int myQueuePop(MyQueue* obj) {if(STEmpty(&obj->stpop)){while(!STEmpty(&obj->stpush)){Datastyle temp = STTop(&obj->stpush);STPop(&obj->stpush);STPush(&obj->stpop, temp);}}Datastyle top =  STTop(&obj->stpop);STPop(&obj->stpop);return top;
}int myQueuePeek(MyQueue* obj) {if(STEmpty(&obj->stpop)){while(!STEmpty(&obj->stpush)){Datastyle temp = STTop(&obj->stpush);STPop(&obj->stpush);STPush(&obj->stpop, temp);}}return STTop(&obj->stpop);
}bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->stpush) && STEmpty(&obj->stpop);
}void myQueueFree(MyQueue* obj) {STDestory(&obj->stpush);STDestory(&obj->stpop);free(obj);obj = NULL;
}

---

快乐的时光总是短暂，咱们下篇博文再见啦！！！如果小编的文章会对你有帮助的话不要忘了，记得给小编点赞、收藏支持一下，在此非常感谢！！！