分享一首歌曲吧,希望在枯燥的刷题生活中带给你希望和勇气,加油!
题目:
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push
、top
、pop
和 empty
)。
实现 MyStack
类:
-
void push(int x)
将元素 x 压入栈顶。 -
int pop()
移除并返回栈顶元素。 -
int top()
返回栈顶元素。 -
boolean empty()
如果栈是空的,返回true
;否则,返回false
。
题解:
首先自己实现一个队列粘贴复制过去:
注意:这道题目队列的实现方法不同不会影响题目,只要是个队列,先进先出,那么不管你是双向还是结构不同,都不会影响题目的实现。文章来源:https://www.toymoban.com/news/detail-633838.html
#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;
}
剩下的就是题目接口:文章来源地址https://www.toymoban.com/news/detail-633838.html
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);
}
到了这里,关于(力扣)用两个队列实现栈---C语言的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!