typedef i nt QueueDataType;
typedef struct QueueNode {
QueueDataType data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue {
struct QueueNode* head;
struct QueueNode* tail;
}Queue;
void QueueInit(Queue* q)
{
q->head = NULL;
q->tail = NULL;
}
void Destory(Queue* q)
{
QueueNode* p;
while (q->head!= NULL) {
p = q->head;
q->head = p->next;
free(p);
}
}
void QueuePush(Queue* q, QueueDataType x)
{
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode != NULL)
{
newnode->data = x;
newnode->next = NULL;
}
else {
exit(-1);
}
if (q->head == NULL)
{
q->head = q->tail = newnode;
}
else {
q->tail->next = newnode;
q->tail = newnode;
}
}
void QueuePop(Queue* q)
{
if (q->head!=NULL) {
QueueNode* p;
p = q->head;
q->head = q->head->next;
free(p);
}
}
void QueuePrintf(Queue* q)
{
QueueNode* p = q->head;
while (p!= NULL)
{
printf("%d ", p->data);
p = p->next;
}
}
bool QueueEmpty(Queue* q)
{
if (q->head == NULL) {
return true;
}
else {
return false;
}
}
QueueDataType QueueFront(Queue* q)
{
if (q->head!=NULL) {
return q->head->data;
}
}
QueueDataType QueueBack(Queue* q)
{
if (q->tail != NULL) {
return q->tail->data;
}
}
int QueueSize(Queue* q)
{
int num = 0;
QueueNode* p = (QueueNode*)malloc(sizeof(QueueNode));
p = q->head;
while (p!=NULL) {
num++;
p = p->next;
}
return num;
}
typedef struct {
struct Queue* Q1;
struct Queue* Q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
QueueInit(obj->Q1);
QueueInit(obj->Q2);
return obj;
}
void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty(obj->Q1)){
QueuePush(obj->Q1, x);
}else{
QueuePush(obj->Q2, x);
}
}
int myStackPop(MyStack* obj) {
Queue* nonemptyQ;
if(!QueueEmpty(obj->Q2)){
while(QueueSize(obj->Q2)>1){
QueuePush(obj->Q1, QueueFront(obj->Q2));
QueuePop(obj->Q2);
}
nonemptyQ=obj->Q2;
}
else{
while(QueueSize(obj->Q1)>1){
QueuePush(obj->Q2, QueueFront(obj->Q1));
QueuePop(obj->Q1);
}
nonemptyQ=obj->Q1;
}
int top=nonemptyQ->head->data;
QueuePop(nonemptyQ);
return top;
}
int myStackTop(MyStack* obj) {
if(!QueueEmpty(obj->Q1)){
return QueueBack(obj->Q1);
}else{
return QueueBack(obj->Q2);
}
}
bool myStackEmpty(MyStack* obj) {
if(QueueEmpty(obj->Q1)&&QueueEmpty(obj->Q2)){
return true;
}else{
return false;
}
}
void myStackFree(MyStack* obj) {
Destory(obj->Q1);
Destory(obj->Q2);
}
/**
- 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);
- /