【数据结构】队列和栈练习

1.用队列实现栈 

225. 用队列实现栈 - 力扣（LeetCode）

typedef int QDatatype;
typedef struct QueueNode
{
	struct QueueNode *next;
	QDatatype data;
}QNode;
 
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	QDatatype size;
}Que;

typedef struct 
{
    Que q1;
    Que q2;
} MyStack;



void QueueInit(Que* pq);
void QueueDestroy(Que* pq);
 
void QueuePush(Que* pq, QDatatype x);
void QueuePop(Que* pq);
int QueueSize(Que* pq);
bool QueueEmpty(Que* pq);
 
QDatatype QueueFront(Que* pq);//队头数据
QDatatype QueueBack(Que* pq);//队尾数据


void QueueInit(Que* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
 
void QueueDestroy(Que* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
 
void QueuePush(Que* 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)
	{
		assert(pq->tail == NULL);
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}
 
void QueuePop(Que* pq)
{
	assert(pq);
	assert(pq->head != NULL);
 
	QNode* oldhead = pq->head;
	pq->head = pq->head->next;
	free(oldhead);
 
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
 
	pq->size--;
}
 
int QueueSize(Que* pq)
{
	assert(pq);
	return pq->size;
}
 
bool QueueEmpty(Que* pq)
{
	assert(pq);
	return pq->size == 0;
}
 
QDatatype QueueFront(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}
 
QDatatype QueueBack(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}



MyStack* myStackCreate() 
{
    MyStack*pst=(MyStack*)malloc(sizeof(MyStack));
    if(pst==NULL)
    {
        perror("malloc fail");
        return NULL;
    }

    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) 
{
    assert(obj != NULL);
    Que* emptyQ = NULL;
    Que* noneemptyQ = NULL;

    // 确定哪个队列是非空的
    if (!QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2)) 
    {
        noneemptyQ = &obj->q1;
        emptyQ = &obj->q2;
    } 
    else if (QueueEmpty(&obj->q1) && !QueueEmpty(&obj->q2)) 
    {
        noneemptyQ = &obj->q2;
        emptyQ = &obj->q1;
    } 
    else 
    {
        // 两个队列都为空，栈为空
        return -1; 
    }

    // 将非空队列的元素（除最后一个外）移到空队列
    while (QueueSize(noneemptyQ) > 1) 
    {
        QueuePush(emptyQ, QueueFront(noneemptyQ));
        QueuePop(noneemptyQ);
    }

    // 最后一个元素是栈顶
    int top = QueueFront(noneemptyQ);
    QueuePop(noneemptyQ);
    return top;
}

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

2.用栈实现队列 

232. 用栈实现队列 - 力扣（LeetCode）

typedef int STDataType;
 
typedef struct Stack
{
	int* a;
	int top;
	int capacity;
}ST;

typedef struct
{
    ST Popst;
    ST Pushst;
} MyQueue;
 
void STInit(ST* ps);
void STDestroy(ST* ps);
 
void STPush(ST* ps,STDataType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
 
STDataType STTop(ST* ps);

 
void STInit(ST* ps)
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->capacity = 4;
	ps->top = 0;//top是栈顶元素的下一位置
 
}
 
void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
 
void STPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		STDataType*tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity*2);
		if (tmp == NULL)
		{
			perror("malloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
 
	ps->a[ps->top] = x;
	ps->top++;
}
 
void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
 
	ps->top--;
}
 
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
 
STDataType STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
 
	return ps->a[ps->top - 1];
}



MyQueue* myQueueCreate() 
{
    MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
    if(obj==NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    STInit(&obj->Pushst);
    STInit(&obj->Popst);
    return obj;
}

void myQueuePush(MyQueue* obj, int x) 
{
    STPush(&obj->Pushst,x);
}

int myQueuePeek(MyQueue* obj) 
{
    if(STEmpty(&obj->Popst))
    {
        while(!STEmpty(&obj->Pushst))
        {
            STPush(&obj->Popst,STTop(&obj->Pushst));
            STPop(&obj->Pushst);
        }
    }

    return STTop(&obj->Popst);
}

int myQueuePop(MyQueue* obj) 
{
    int front=myQueuePeek(obj);
    STPop(&obj->Popst);

    return front;
}


bool myQueueEmpty(MyQueue* obj) 
{
    return(STEmpty(&obj->Pushst)&&STEmpty(&obj->Popst));
}

void myQueueFree(MyQueue* obj) 
{
    STDestroy(&obj->Pushst);
    STDestroy(&obj->Popst);
    free(obj);
}

3.设计循环队列

622. 设计循环队列 - 力扣（LeetCode）

typedef struct {
    int*a;
    int k;
    int front;
    int rear;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->front=obj->rear=0;
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    obj->k=k;
    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->rear;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear+1)%(obj->k+1)==obj->front;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;
    obj->a[obj->rear++]=value;
    obj->rear%=(obj->k+1);
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return false;
    ++obj->front;
    obj->front%=(obj->k+1);
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[(obj->rear-1+obj->k+1)%(obj->k+1)];
}


void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}