目录
1.用队列实现栈
(1)题目描述
(2)解题思路
代码实现:
typedef int QDatatype;
typedef struct QuequeNode {
QDatatype data;
struct QuequeNode* next;
}QNode;
typedef struct Queue{
QNode* head; //单链表的头指针作为队头
QNode* tail; //单链表的尾指针作为队尾
int size; //存储队列元素数量
}Que;
//初始化队列
void QInit(Que* ps) {
assert(ps);
ps->head = ps->tail = NULL;
ps->size = 0;
}
//销毁队列
void QDestroy(Que* ps) {
assert(ps);
QNode* cur = ps->head;
while (cur) {
QNode* next = cur->next;
free(cur);
cur = next;
}
ps->size = 0;
ps->head = ps->tail = NULL;
}
//插入数据(从队尾)------入队
void QPush(Que* ps, QDatatype x) {
assert(ps);
QNode* cur = (QNode*)malloc(sizeof(QNode));
if (cur == NULL) {
perror("malloc fail");
return;
}
if (ps->head == NULL) {
assert(ps->tail == NULL);
ps->head = ps->tail = cur;
}
else {
ps->tail->next = cur; //先赋值
ps->tail = cur; //再更新尾指针
}
cur->next = NULL;
cur->data = x;
ps->size++;
}
//判空
bool QEmpty(Que* ps) {
assert(ps);
return (ps->size == 0);
}
//删除数据(从对头)------出队
void QPop(Que* ps) {
assert(ps);
assert(!QEmpty(ps));
if (ps->head->next == NULL) {
free(ps->head);
ps->head = ps->tail = NULL;
ps->size = 0;
return;
}
QNode* next = ps->head->next;
free(ps->head);
ps->head = next;
ps->size--;
}
//得出队内元素数量
int QSize(Que* ps) {
assert(ps);
return (ps->size);
}
//得到队头元素的数据
QDatatype QFront(Que* ps) {
assert(ps && !QEmpty(ps));
return (ps->head->data);
}
//得到队尾元素的数据
QDatatype QBack(Que* ps) {
assert(ps && !QEmpty(ps));
return (ps->tail->data);
}
typedef struct {
Que q1;
Que q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* ptr = (MyStack*)malloc(sizeof(MyStack));
if(ptr == NULL){
perror("malloc fail");
return NULL;
}
QInit(&ptr->q1);
QInit(&ptr->q2);
return ptr;
}
void myStackPush(MyStack* obj, int x) {
if(QEmpty(&obj->q1)){
QPush(&obj->q2, x);
}
else{
QPush(&obj->q1, x);
}
}
int myStackPop(MyStack* obj) {
if(QEmpty(&obj->q1)){
while(QSize(&obj->q2) > 1){
QDatatype temp = QFront(&obj->q2);
QPop(&obj->q2);
QPush(&obj->q1, temp);
}
QDatatype top = QBack(&obj->q2);
QPop(&obj->q2);
return top;
}
else{
while(QSize(&obj->q1) > 1){
QDatatype temp = QFront(&obj->q1);
QPop(&obj->q1);
QPush(&obj->q2, temp);
}
QDatatype top = QBack(&obj->q1);
QPop(&obj->q1);
return top;
}
}
int myStackTop(MyStack* obj) {
if(QEmpty(&obj->q1)){
return QBack(&obj->q2);
}
return QBack(&obj->q1);
}
bool myStackEmpty(MyStack* obj) {
return QEmpty(&obj->q1) && QEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
QDestroy(&obj->q1);
QDestroy(&obj->q2);
free(obj);
obj = NULL;
}
2.用两个栈实现队列
(1)题目描述
(2)解题思路
代码实现:
#define MAXCAPACITY 4
typedef int Datastyle;
typedef struct stack {
Datastyle* a;
int top;
int capacity;
}ST;
//初始化栈
void STInit(ST* ps) {
assert(ps);
Datastyle* temp = (Datastyle*)malloc(MAXCAPACITY * sizeof(Datastyle));
if (temp == NULL) {
perror("malloc fail");
exit(-1);
}
ps->a = temp;
ps->capacity = MAXCAPACITY;
ps->top = 0;
}
//销毁栈
void STDestory(ST* ps){
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
//插入数据(从栈顶)----(入栈,压栈)
void STPush(ST* ps, Datastyle x) {
assert(ps);
//判断是否满了
if (ps->top == ps->capacity) {
Datastyle* temp = (Datastyle*)realloc(ps->a, 2 * ps->capacity * sizeof(Datastyle)); //扩容为当前容量的两倍比较合理
if (temp == NULL) {
perror("realloc fail");
return;
}
ps->capacity *= 2;
ps->a = temp;
}
ps->a[ps->top++] = x;
}
//判空
bool STEmpty(ST* ps) {
return (ps->top == 0);
}
//删除数据(从栈顶)----(出栈)
void STPop(ST* ps) {
assert(ps && !STEmpty(ps));
--ps->top;
}
//访问栈顶元素
Datastyle STTop(ST* ps) {
return ps->a[ps->top - 1];
}
//得出栈的元素个数
int STSize(ST* ps) {
assert(ps);
return ps->top;
}
typedef struct {
ST stpush; //stpush专门用来存储数据,只有在stpop为空时进行出数据至st2
ST stpop; //stpop专门用来出数据,只有当其为空时从stpush拿出数据进行存储
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* ptr = (MyQueue*) malloc(sizeof(MyQueue));
if(ptr == NULL){
perror("malloc fail");
return NULL;
}
STInit(&ptr->stpush);
STInit(&ptr->stpop);
return ptr;
}
void myQueuePush(MyQueue* obj, int x) {
STPush(&obj->stpush, x);
}
int myQueuePop(MyQueue* obj) {
if(STEmpty(&obj->stpop)){
while(!STEmpty(&obj->stpush)){
Datastyle temp = STTop(&obj->stpush);
STPop(&obj->stpush);
STPush(&obj->stpop, temp);
}
}
Datastyle top = STTop(&obj->stpop);
STPop(&obj->stpop);
return top;
}
int myQueuePeek(MyQueue* obj) {
if(STEmpty(&obj->stpop)){
while(!STEmpty(&obj->stpush)){
Datastyle temp = STTop(&obj->stpush);
STPop(&obj->stpush);
STPush(&obj->stpop, temp);
}
}
return STTop(&obj->stpop);
}
bool myQueueEmpty(MyQueue* obj) {
return STEmpty(&obj->stpush) && STEmpty(&obj->stpop);
}
void myQueueFree(MyQueue* obj) {
STDestory(&obj->stpush);
STDestory(&obj->stpop);
free(obj);
obj = NULL;
}