力扣刷题:栈和队列OJ篇(上)-LMLPHP


1.用队列实现栈

(1)题目描述

力扣刷题:栈和队列OJ篇(上)-LMLPHP

力扣刷题:栈和队列OJ篇(上)-LMLPHP


(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)题目描述

力扣刷题:栈和队列OJ篇(上)-LMLPHP
力扣刷题:栈和队列OJ篇(上)-LMLPHP


(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;
}

快乐的时光总是短暂,咱们下篇博文再见啦!!!如果小编的文章会对你有帮助的话不要忘了,记得给小编点赞、收藏支持一下,在此非常感谢!!!

01-01 08:37