目录
我们提供的服务有：成都网站设计、成都网站建设、微信公众号开发、网站优化、网站认证、海城ssl等。为上1000家企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务，是有科学管理、有技术的海城网站制作公司1.用队列实现栈
增删
求栈顶元素
判断栈为空
2.用栈实现队列
增删
返回队列开头的数据
判断队列为空
尾言
源码
队列实现栈
栈实现队列
刚讲完栈和队列，LeetCode上有两题栈与队列的互相实现，简单地讲讲思路和实现吧。
1.用队列实现栈
原题地址：225.用队列实现栈
题目要求我们用两个队列来实现一个栈，我们知道队列的性质是先进先出，而栈是后进先出，假设随便给我们要的这个栈之中添加几个数，便能画出这样的图
增删
那这样接下来若要出栈，输出的便是 5 ，但是队列出队的话只能输出 1 。所以我们就要用到另一个队列，把队列1最后一个数前面的数据导入到队列2之后再输出队列1的唯一数。这样就完成了出栈的模拟。
之后把队列1第一个数据删除，一定保证一个队列为空 ，即第二次出栈还是要把非空的队列的数据导入空队列里去。
若是要入栈操作的话就是直接再非空队列队尾插入数据就可以了，最后面的值不会被导入到另一队列里。所以下次出栈就会将其输出。
求栈顶元素
找栈顶元素其实与出栈的唯一不同就是，出栈要删除栈顶元素，而求栈顶元素不一样，其要求要有返回值。偷懒的话可以先写求栈顶元素，之后出栈只要复用函数就可以完成了。
判断栈为空
前面讲过，必定有一个队列为空，因此不能只检查一个队列而是两个队列都要检查，即两个队列都为空则证明栈为空。
2.用栈实现队列
原题地址：232.用栈实现队列
其实只要熟悉了队列和栈的基本性质，其实这两题也并不会很难，思路正确了剩下的就只需要注意编写程序时的小细节就可以了。
增删
仔细分析题目，要求用两个栈实现一个队列，既然题目都这样要求了只用一个栈明显是不可能的，上一题的经验告诉我，要把数据导入到另一个栈里。
把数据导到另一个栈后我们惊奇的发现，数据恰好就成了我们想要的样子。这段数据就可以直接输出了。
这下我们就可以让一个栈专门承载输入数据，另一个栈专门输出数据，输出栈为空时再从输入栈把数据导入到输出栈里面。
返回队列开头的数据
也是跟删除是一个道理，不过只是返回值并不删除数据。即输出栈没有值就导入输入栈的值进去就可以了。
判断队列为空
两个栈如果都为空，队列就为空，只有其中一个栈为空是不算的。
尾言
好了，这样今天我们两道题的思路与实现到这里就讲完了，说实在的用C语言写确实是麻烦了一点，但是之前写过栈和队列的话直接把代码复制过去，之后用自己之前写的函数写就可以了。有问题的话一定私信或者评论区指出，一定第一时间回复！！！
源码
队列实现栈
typedef int Qdatatype;
typedef struct Qnode
{
Qdatatype data;
struct Queue* next;
}Qnode;
typedef struct Queue
{
Qnode* head;
Qnode* tail;
int size;
}Queue;
void Queueinit(Queue* p)
{
p->head = NULL;
p->tail = NULL;
p->size = 0;
}
bool QueueEmpty(Queue* p)
{
assert(p);
return p->head == NULL || p->tail == NULL;
}
void Queuepush(Queue* p, Qdatatype x)
{
assert(p);
Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
if (newnode == NULL)
{
perror(malloc);
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (p->head == NULL)
{
p->head = p->tail = newnode;
p->size++;
}
else
{
p->tail->next = newnode;
p->tail = newnode;
p->size++;
}
}
void Queuepop(Queue* p)
{
assert(p);
assert(!QueueEmpty(p));
Qnode* next = p->head->next;
free(p->head);
p->head = next;
p->size--;
}
Qdatatype Queuefront(Queue* p)
{
assert(p);
return p->head->data;
}
void QueueDestroy(Queue* p)
{
assert(p);
Qnode* cur = p->head;
while (cur)
{
Qnode* next = cur->next;
free(cur);
cur = next;
}
p->head = p->tail = NULL;
p->size = 0;
}
Qdatatype Queueback(Queue* p)
{
assert(p);
assert(!QueueEmpty(p));
return p->tail->data;
}
int Queuesize(Queue* p)
{
assert(p);
return p->size;
}
typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* stack = (MyStack*)malloc(sizeof(MyStack)); //开辟栈的空间，动态开辟才不是局部变量
Queueinit(&stack->q1); //两个队列的初始化
Queueinit(&stack->q2);
return stack;
}
void myStackPush(MyStack* obj, int x) {
assert(obj);
if (!QueueEmpty(&obj->q1)) //在非空队列里插入数据，两个都为空则默认插入在第一个里面
{
return Queuepush(&obj->q1, x);
}
else
{
return Queuepush(&obj->q2, x);
}
}
int myStackPop(MyStack* obj) {
assert(obj);
Queue* emptyqueue = &obj->q1; //一定有一个空队列
Queue* queue = &obj->q2; //一个是有数据的队列
if (QueueEmpty(&obj->q2)) //判断为空的队列
{
emptyqueue = &obj->q2;
queue = &obj->q1;
}
while (Queuesize(queue) >1)
{
Queuepush(emptyqueue, Queuefront(queue)); //导入后删除原队列里的数据
Queuepop(queue);
}
int ret = Queuefront(queue);
Queuepop(queue);
return ret;
}
int myStackTop(MyStack* obj) {
assert(obj);
if (!QueueEmpty(&obj->q1))
{
return Queueback(&obj->q1);
}
else
{
return Queueback(&obj->q2);
}
}
bool myStackEmpty(MyStack* obj) {
assert(obj);
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
栈实现队列
typedef int STdatatype;
typedef struct Stack
{
STdatatype* data;
int top;
int capacity;
}Stack;
void checkcapacity(Stack* p)
{
STdatatype* newp;
if (p->top == p->capacity)
{
newp = (STdatatype*)realloc(p->data, sizeof(Stack) * p->capacity * 2);
if (newp == NULL)
{
perror(realloc);
exit(-1);
}
p->data = newp;
p->capacity *= 2;
}
if (p == NULL)
{
perror(realloc);
exit(-1);
}
}
void StackInit(Stack* p)
{
STdatatype* np = (STdatatype*)malloc(sizeof(STdatatype) * 4);
if (np)
{
p->data = np;
}
p->top = 0;
p->capacity = 4;
}
void StackPush(Stack* p, STdatatype x)
{
assert(p);
checkcapacity(p);
(p->data)[p->top] = x;
p->top++;
}
void Stackprint(Stack* p)
{
int i = p->top - 1;
while (i >= 0)
{
printf("%d ", (p->data)[i--]);
}
printf("\n");
}
void StackPop(Stack* p)
{
assert(p);
assert(p->top);
p->top--;
}
STdatatype StackTop(Stack* p)
{
assert(p);
int top = p->top - 1;
return (p->data)[top];
}
int StackEmpty(Stack* p)
{
assert(p);
if (p->top != 0)
{
return 0;
}
return 1;
}
void StackDestroy(Stack* p)
{
assert(p);
assert(p->data);
free(p->data);
p->data = NULL;
p->top = 0;
p->capacity = 0;
}
typedef struct //两个队列一个输出一个输入，输出栈里没数据了之后就从输入里面倒数据过去
{
Stack S; //输入
Stack nullS; //输出
} MyQueue;
bool myQueueEmpty(MyQueue* obj);
int myQueuePeek(MyQueue* obj);
MyQueue* myQueueCreate() //创建队列
{
MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue)); //开辟队列空间
StackInit(&queue->S); //对两个栈初始化
StackInit(&queue->nullS);
return queue; //返回开辟的队列
}
void myQueuePush(MyQueue* obj, int x) {
assert(obj);
StackPush(&obj->S, x); //直接在插入的队列里插入数据
}
int myQueuePop(MyQueue* obj) {
assert(obj);
assert(!myQueueEmpty(obj)); //判断队列不为空
int ret = myQueuePeek(obj); //取最上面的值返回
StackPop(&obj->nullS); //pop在peek的基础上增加数据的删除
return ret;
}
int myQueuePeek(MyQueue* obj) { //拿最前面的数据
assert(obj);
assert(!myQueueEmpty(obj)); //队列不为空
if (StackEmpty(&obj->nullS)) //输出栈为空则倒入数据
{
while (!StackEmpty(&obj->S)) //直到输入栈为空，必定一个栈为空
{
StackPush(&obj->nullS, StackTop(&obj->S)); //取输入栈最上面导入到输出栈的最下面
StackPop(&obj->S); //清除输入栈的数据
}
}
return StackTop(&obj->nullS); //返回最上面的值
}
bool myQueueEmpty(MyQueue* obj) {
assert(obj);
return StackEmpty(&obj->nullS) && StackEmpty(&obj->S); //两个栈都为空则队列为空
}
void myQueueFree(MyQueue* obj) {
assert(obj);
StackDestroy(&obj->nullS); //销毁两个栈
StackDestroy(&obj->S);
free(obj); //销毁队列
}
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享名称：【LeetCode】用队列实现栈和用栈实现队列（C语言）-创新互联
转载来于：
http://cdkjz.cn/article/dicoph.html
