分享一首歌曲吧，希望在枯燥的刷题生活中带给你希望和勇气，加油！
题目：
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
● void push(int x) 将元素 x 压入栈顶。
● int pop() 移除并返回栈顶元素。
● int top() 返回栈顶元素。
● boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
题解：
首先自己实现一个队列粘贴复制过去：
注意：这道题目队列的实现方法不同不会影响题目，只要是个队列，先进先出，那么不管你是双向还是结构不同，都不会影响题目的实现。
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int DataType; typedef struct Queue { DataType data; struct Queue *next; }Queue; typedef struct Q { Queue* head; Queue* tail; int size; }Q; void Init(Q *qq); void Destroy(Q* qq); void QueuePush(Q* qq, DataType x); void QueuePop(Q* qq); DataType GetQueueFrontNum(Q* qq); DataType GetQueueBackNum(Q* qq); bool Empty(Q* qq); int Size(Q* qq); void Init(Q* qq) { assert(qq); qq->head = NULL; qq->tail = NULL; qq->size = 0; } void QueuePush(Q* qq, DataType x) { assert(qq); Queue* temp = (Queue*)malloc(sizeof(Queue)); if (temp == NULL) { perror("malloc fail"); exit(-1); } temp->data = x; temp->next = NULL; if (qq->tail == NULL) qq->head = qq->tail = temp; else { qq->tail->next = temp; qq->tail = temp; } qq->size++; } void QueuePop(Q* qq) { assert(qq); assert(!Empty(qq)); if (qq->head == qq->tail) { free(qq->head); qq->head = qq->tail = NULL; } else { Queue* next = qq->head->next; free(qq->head); qq->head = next; } qq->size--; } DataType GetQueueFrontNum(Q* qq) { assert(qq); assert(!Empty(qq)); return qq->head->data; } DataType GetQueueBackNum(Q* qq) { assert(qq); assert(!Empty(qq)); return qq->tail->data; } bool Empty(Q* qq) { assert(qq); return qq->size == 0; } void Destroy(Q* qq) { assert(qq); Queue *cur = qq->head; while(cur) { Queue *next = cur->next; free(cur); cur = next; } qq->head = qq->tail = NULL; qq->size = 0; } int Size(Q* qq) { assert(qq); return qq->size; }
剩下的就是题目接口：
typedef struct { Q q1; Q q2; } MyStack;
MyStack* myStackCreate() { MyStack *st = (MyStack*)malloc(sizeof(MyStack)); Init(&st->q1); Init(&st->q2); return st; }
void myStackPush(MyStack* obj, int x) { if(!Empty(&obj->q1)) { QueuePush(&obj->q1,x); } else { QueuePush(&obj->q2,x); } }
int myStackPop(MyStack* obj) { Q *empty = &obj->q1; Q *obempty = &obj->q2; if(!Empty(&obj->q1)) { empty = &obj->q2; obempty = &obj->q1; } int sz = Size(obempty) - 1; for(int i=0; i<sz; i++) { QueuePush(empty,GetQueueFrontNum(obempty)); QueuePop(obempty); } int num = GetQueueFrontNum(obempty); QueuePop(obempty); return num; }
int myStackTop(MyStack* obj) { if(!Empty(&obj->q1)) { return GetQueueBackNum(&obj->q1); } else { return GetQueueBackNum(&obj->q2); } }
bool myStackEmpty(MyStack* obj) { return (&obj->q1)->size == 0 && (&obj->q2)->size == 0; }
void myStackFree(MyStack* obj) { Destroy(&obj->q1); Destroy(&obj->q2); free(obj); }
