欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 房产 > 家装 > [数据结构]用队列实现栈

[数据结构]用队列实现栈

2025/7/10 7:07:50 来源:https://blog.csdn.net/m0_74978334/article/details/145889206  浏览:    关键词:[数据结构]用队列实现栈

问题:

思路:

代码实现:

(注:下面代码涉及到队列的完整代码,如果有不懂的可以看小编之前发的文章《[数据结构]队列详解》)

typedef int QDataType;// 链式结构:表示队列
typedef struct QListNode
{struct QListNode* next;QDataType data;
}QNode;
// 队列的结构
typedef struct Queue
{QNode * head;QNode* tail;int size;
}Queue;// 初始化队列
void QueueInit(Queue* pq);
// 队尾入队列
void QueuePush(Queue* pq, QDataType x);
// 队头出队列
void QueuePop(Queue* pq);
// 获取队列头部元素
QDataType QueueFront(Queue* pq);
// 获取队列队尾元素
QDataType QueueBack(Queue* pq);
// 获取队列中有效元素个数
int QueueSize(Queue* pq);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0
bool QueueEmpty(Queue* pq);
// 销毁队列
void QueueDestroy(Queue* pq);// 初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}// 销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur != NULL){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}
// 队尾入队列
void QueuePush(Queue* pq, QDataType x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;//不是带哨兵位的头结点,需要判断第一个是否为空if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;//将新节点链接到队列的最后一个节点。pq->tail = newnode;//更新尾指针,使其指向新节点。}pq->size++;
}
// 队头出队列
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head!=NULL);if (pq->head != NULL){if (pq->head->next == NULL)//表示只有一个节点了{free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}}pq->size--;
}// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{return pq->size;
}// 检测队列是否为空,如果为空返回非零结果,如果非空返回0
bool QueueEmpty(Queue* pq)
{return pq->size == 0;
}
// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack *pts =(MyStack *)malloc(sizeof(MyStack));if(pts==NULL){perror("malloc fail");}QueueInit(&pts->q1);QueueInit(&pts->q2);return pts;
}void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}int myStackPop(MyStack* obj) {Queue* emptyQ=&obj->q1;Queue* noemptyQ=&obj->q2;//假设q1为空q2不为空if(!QueueEmpty(&obj->q1)){emptyQ=&obj->q2;noemptyQ=&obj->q1;}//导数据while(QueueSize(noemptyQ)>1){QueuePush(emptyQ,QueueFront(noemptyQ));//把非空的数据导入到空列表里面去QueuePop(noemptyQ);}int top=QueueFront(noemptyQ);QueuePop(noemptyQ);//删除非空队列里面的那个数据(出栈)return top;
}int myStackTop(MyStack* obj) {if(QueueEmpty(&obj->q1)){return QueueBack(&obj->q2);}else{return QueueBack(&obj->q1);}
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);}void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词