栈与队列的3个oj题

栈与队列

• 225.用队列实现栈
• 解题思路
• 代码
• 232.用栈实现队列
• 解题思路
• 代码
• 622.设计循环队列
• 解题思路
• 代码

---

225.用队列实现栈

解题思路

队列的性质是先进的先出，栈的性质是先进是后出。
我们设计的这两个队列，当添加数据的时候，插入有数据不为空的一个队列。当删除数据的，把数据移动到为空的队列中去，只留下队尾的数据，该数据就是要删除的数据。

代码

下面这是创建队列

typedef int QueueTypeDate;

typedef struct QListNode
{
	struct QListNode* next;
	QueueTypeDate val;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

void QueueInit(Queue* q)
{
	assert(q);
	q->head = q->tail = NULL;
}

bool QueueEmpty(Queue* q)
{
	assert(q);

	return q->head == NULL;
}

void QueuePush(Queue* q, QueueTypeDate x)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	newnode->next = NULL;
	newnode->val = x;

	if (QueueEmpty(q))
		q->head = q->tail = newnode;
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
}
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	if (q->head == q->tail)
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	else
	{
		QNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}
	
}
QueueTypeDate QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));

	return q->head->val;
}
QueueTypeDate QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));

	return q->tail->val;
}
int QueueSize(Queue* q)
{
	assert(q);
	QNode* cur = q->head;
	int size = 0;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}
void QueueDestroy(Queue* q)
{
	assert(q);
	while (q->head)
	{
		QueuePop(q);
	}
}

队列实现栈

typedef struct {
    Queue Q1;
    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->Q2,x);
    else
    QueuePush(&obj->Q1,x);
}

int myStackPop(MyStack* obj) {
    int x;
    if(QueueEmpty(&obj->Q1))
    {
        while((&obj->Q2)->head!=(&obj->Q2)->tail)
        {
            x=QueueFront(&obj->Q2);
            QueuePop(&obj->Q2);
            QueuePush(&obj->Q1,x);
        }   
        x=QueueFront(&obj->Q2);
        QueuePop(&obj->Q2);    
    }
    else
    {
        while((&obj->Q1)->head!=(&obj->Q1)->tail)
        {
            x=QueueFront(&obj->Q1);
            QueuePop(&obj->Q1);
            QueuePush(&obj->Q2,x);
        }   
        x=QueueFront(&obj->Q1);
        QueuePop(&obj->Q1);       
    }
    return x;
}

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

232.用栈实现队列

解题思路

一个栈来表示入队（简称入栈），另一个栈来表示出队（简称出栈）。当出队是，如果出栈为空，入栈里面的全部数据进入出栈中。
当查看队头的元素的时候，就是要察看出栈栈顶的数据。要注意出栈数据为空的情况。

代码

栈的实现——》数据结构——栈

typedef struct {
    Stack outstack;
    Stack instack;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    InitStack(&obj->outstack);
    InitStack(&obj->instack);
    return obj;
}

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

int myQueuePop(MyQueue* obj) {
    if(!StackSize(&obj->outstack))
    {
        while(StackSize(&obj->instack))
        {
            StackPush(&obj->outstack,StackTop(&obj->instack));
            StackPop(&obj->instack);
        }
    }
    int x=StackTop(&obj->outstack);
    StackPop(&obj->outstack);
    return x;
}

int myQueuePeek(MyQueue* obj) {
    if(!StackSize(&obj->outstack))
    {
        while(StackSize(&obj->instack))
        {
            StackPush(&obj->outstack,StackTop(&obj->instack));
            StackPop(&obj->instack);
        }
    }
    return StackTop(&obj->outstack);
}

bool myQueueEmpty(MyQueue* obj) {
    return !(StackSize(&obj->instack)||StackSize(&obj->outstack));
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->outstack);
    StackDestroy(&obj->instack);
    free(obj);

}

622.设计循环队列

解题思路

我们创建的循环队列为静态。队列长度为N，那么我们里面只用来储存N-1个数据。
队列里面的成员包括，数据，队列起始下标（头标），队列末尾下标（尾标）,队列可以有效储存数据的长度。
我们这样设计循环队列：当头标和尾标相等时，队列为空；当尾标下一个坐标等于头标时，为满。

我们设计的队列本质是连续储存的数组。
当增加数据的时候，尾向后移动；当删除数据的时候，头向后走。
不为空的时候。头或尾到最后的边界的时候，要回到头的地方。
插入的时候注意满的情况，删除的时候注意为空的时候。

代码

typedef struct {
    int* arr;
    int head;
    int tail;
    int capacity;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->arr=(int*)malloc(sizeof(int)*(k+1));
    obj->head=obj->tail=0;
    obj->capacity=k;
    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->head==obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    int curtail=obj->tail+1;
    if(curtail==obj->capacity+1)
    curtail=0;
    return curtail==obj->head;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    return false;
    obj->arr[obj->tail]=value;
    obj->tail++;
    if(obj->tail==obj->capacity+1)
    obj->tail=0;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return false;
    obj->head++;
    if(obj->head==obj->capacity+1)
    obj->head=0;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return -1;
    return obj->arr[obj->head];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return -1;
    int curtail=obj->tail-1;
    if(curtail==-1)
    return obj->arr[obj->capacity];
    else
    return obj->arr[curtail];
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->arr);
    obj->arr=NULL;
    free(obj);

}