3. 代码实现

typedef int QDataType;
typedef struct QueueNode
{

QDataType data;
struct QueueNode* next;
}QNode;

typedef struct Queue
{

QNode* tail;
int size;
}Que;

void QueueInit(Que* pq);
void QueuePush(Que* pq,QDataType x);
void QueuePop(Que* pq);
QDataType QueueFront(Que* pq);
QDataType QueueBack(Que* pq);
QDataType QueueSize(Que* pq);
bool QueueEmpty(Que* pq);
void QueueDestroy(Que* pq);

void QueueInit(Que* pq)
{

assert(pq);
pq->size = 0;
}

void QueuePush(Que* pq, QDataType x)
{

assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{

perror("malloc failed");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)
{

}
else
{

pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}

void QueuePop(Que* pq)
{

assert(pq);
//队列为空
assert(!QueueEmpty(pq));
//只有一个结点
{

}
else
{

}
pq->size--;
}

QDataType QueueFront(Que* pq)
{

assert(pq);
assert(!QueueEmpty(pq));
}

QDataType QueueBack(Que* pq)
{

assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}

QDataType QueueSize(Que* pq)
{

assert(pq);
return pq->size;
}

bool QueueEmpty(Que* pq)
{

assert(pq);
}

void QueueDestroy(Que* pq)
{

assert(pq);
while (cur)
{

QNode* next = cur->next;
free(cur);
cur = next;
}
pq->size = 0;
}

typedef struct {

Que q1;
Que q2;
} MyStack;

MyStack* myStackCreate() {

MyStack *pst=(MyStack*)malloc(sizeof(MyStack));
QueueInit(&pst->q1);
QueueInit(&pst->q2);
return pst;
}

void myStackPush(MyStack* obj, int x) {

if(!QueueEmpty(&obj->q1))
{

QueuePush(&obj->q1,x);
}
else
{

QueuePush(&obj->q2,x);
}
}

int myStackPop(MyStack* obj) {

Que* empty=&obj->q1;
Que* nonEmpty=&obj->q2;
if(!QueueEmpty(&obj->q1))
{

nonEmpty=&obj->q1;
empty=&obj->q2;
}
//前size-1个导入空队列
while(QueueSize(nonEmpty)>1)
{

QueuePush(empty,QueueFront(nonEmpty));
QueuePop(nonEmpty);
}
int top=QueueFront(nonEmpty);
QueuePop(nonEmpty);
}

int myStackTop(MyStack* obj) {

if(!QueueEmpty(&obj->q1))
{

return QueueBack(&obj->q1);
}
else
{

return QueueBack(&obj->q2);
}
}

bool myStackEmpty(MyStack* obj) {

return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {

QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}

/**
* Your MyStack struct will be instantiated and called as such:
* MyStack* obj = myStackCreate();
* myStackPush(obj, x);

* int param_2 = myStackPop(obj);

* int param_3 = myStackTop(obj);

* bool param_4 = myStackEmpty(obj);

* myStackFree(obj);
*/


|
1天前
|

【数据结构】栈和队列--＞理解和实现（赋源码)
【数据结构】栈和队列--＞理解和实现（赋源码)
12 5
|
21天前
|

【数据结构OJ题】设计循环队列

22 1
|
15天前
|

20 2
|
21天前
【数据结构OJ题】用栈实现队列

24 0
|
2月前
|

【数据结构与算法 经典例题】使用栈实现队列（图文详解）
【数据结构与算法 经典例题】使用栈实现队列（图文详解）
43 0
|
21天前
|

【数据结构】栈和队列

18 1
|
1月前
|

37 2
|
2月前
|

【数据结构】操作受限的线性表，栈的具体实现
【数据结构】操作受限的线性表，栈的具体实现
35 5
|
2月前
|

【数据结构与算法 经典例题】使用队列实现栈（图文详解）
【数据结构与算法 经典例题】使用队列实现栈（图文详解）
34 1
|
2月前
|

【C/数据结构和算法】：栈和队列
【C/数据结构和算法】：栈和队列
36 1