【数据结构初阶】栈与队列笔试题

前言

在我们学习了栈和队列之后，今天来通过几道练习题来巩固一下我们的知识。

题目一 用栈实现队列

题目链接：232. 用栈实现队列 - 力扣（Leetcode）

这道题难度不是很大，重要的是我们对结构认识的考察，由于这篇文章我们是通过C语言解决的，所以我们必须先去构造一个栈，并且可以进行栈的各种操作，最终实现队列的实现。

typedef int datetype;typedef struct Stack
{datetype* a;int capacity;int top;
}stack;
//初始化
void stackInit(stack* p);
//销毁
void stackDestroy(stack* p);
//入栈
void stackPush(stack* p, datetype x);
//出栈
void stackPop(stack* p);
//取栈顶数据
datetype stackTop(stack* p);
//数据个数
int stackSize(stack* p);
//判断是否为空
bool stackEmpty(stack* p);
bool isValid(char* s);
void stackInit(stack* p)
{assert(p);p->a = NULL;p->capacity = 0;p->top = 0;
}
void stackPush(stack* p,datetype x)
{assert(p);if (p->capacity == p->top){int newCapacity = p->capacity == 0 ? 4 : 2 * p->capacity;datetype* tmp = (datetype*)realloc(p->a, newCapacity * sizeof(datetype));if (tmp == NULL){perror("realloc");exit(-1);}p->a = tmp;p->capacity=newCapacity;}p->a[p->top] = x;p->top++;
}void stackPop(stack* p)
{assert(p);assert(!stackEmpty(p));p->top--;
}void stackDestroy(stack* p)
{assert(p);if (p->capacity == 0)return;free(p->a);p->a = NULL;p->capacity = 0;p->top = 0;
}datetype stackTop(stack* p)
{assert(p);assert(!stackEmpty(p));return p->a[p->top-1];
}bool stackEmpty(stack* p)
{assert(p);return p->top==0;
}
int stackSize(stack* p)
{assert(p);return p->top;
}
//定义进行出数据和入数据的栈
typedef struct {stack pushST;stack popST;
} MyQueue;//创建队列，使用两个栈来实现
MyQueue* myQueueCreate() {MyQueue* tmp=(MyQueue*)malloc(sizeof(MyQueue));stackInit(&tmp->pushST);stackInit(&tmp->popST);return tmp;
}
//直接将数据入pushST
void myQueuePush(MyQueue* obj, int x) {stackPush(&obj->pushST,x);
}
//如过popST内不为空，直接输出数据，如果为空,将pushST数据都入到popST内
int myQueuePop(MyQueue* obj) {if(stackEmpty(&obj->popST)){while(!stackEmpty(&obj->pushST)){stackPush(&obj->popST,stackTop(&obj->pushST));stackPop(&obj->pushST);}}int front=stackTop(&obj->popST);stackPop(&obj->popST);return front;
}int myQueuePeek(MyQueue* obj) {if(stackEmpty(&obj->popST)){while(!stackEmpty(&obj->pushST)){stackPush(&obj->popST,stackTop(&obj->pushST));stackPop(&obj->pushST);}}return stackTop(&obj->popST);
}bool myQueueEmpty(MyQueue* obj) {return stackEmpty(&obj->pushST)&&stackEmpty(&obj->popST);
}void myQueueFree(MyQueue* obj) {stackDestroy(&obj->pushST);stackDestroy(&obj->popST);free(obj);obj=NULL;
}

这道题我们使用两个栈，一个栈负责出数据，一个栈负责入数据，当入数据时，直接push即可，当出数据时，我们使用两个栈配合，使用栈先入先出的特点，将pushST的内容入到popST时，数据就已经变成了逆序，所以在popST栈内，直接出就可以实现队列的先入后出的功能。

题目二 用队列实现栈

题目链接：225. 用队列实现栈 - 力扣（Leetcode）

这道题与上道题类似，都是对结构的考察，使用队列先入先出的特点，通过两个队列之前出数据入数据后，可以实现栈的功能，当一个队列出队进入另外一个队列，只剩一个数据时，直接将这个数据出队列，两个队列互相配合，最终将所有数出队，实现栈的功能。

typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QueueNode;typedef struct Queue
{QueueNode* head;QueueNode* tail;// size_t _size;
}Queue;//void QueueInit(QueueNode** pphead, QueueNode** pptail);
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;
}void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* cur = pq->head;while (cur != NULL){QueueNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));newnode->data = x;newnode->next = NULL;if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}
}void QueuePop(Queue* pq)
{assert(pq);//if (pq->head == NULL)//    return;assert(!QueueEmpty(pq));QueueNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL){pq->tail = NULL;}
}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;
}int QueueSize(Queue* pq)
{assert(pq);int n = 0;QueueNode* cur = pq->head;while (cur){++n;cur = cur->next;}return n;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL;
}typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* ret =(MyStack*)malloc(sizeof(MyStack));QueueInit(&ret->q1);QueueInit(&ret->q2);return ret;
}//哪个队列不为空，就在哪个队列入数据
void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}
//找到为空和不为空的队列，将不为空的队列出为只剩一个数据，直接出这个数据
int myStackPop(MyStack* obj) {Queue* empty = &obj->q1;Queue* nonempty = &obj->q2;if(!QueueEmpty(&obj->q1)){empty = &obj->q2;nonempty = &obj->q1;}while(QueueSize(nonempty)>1){QueuePush(empty,QueueFront(nonempty));QueuePop(nonempty);}int ret=QueueFront(nonempty);QueuePop(nonempty);return ret;
}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);
}

题目三 设计循环队列

题目链接：622. 设计循环队列 - 力扣（Leetcode）

我们之前实现队列是使用链表来实现的，当然也可以使用顺序表来实现，考虑到这道题循环队列的特殊结构，我们使用顺序表和链表两种方式来解决这个问题。

方法一：使用链表解决

首先定义每个结点的结构，再定义一个结构来存head，tail，数据个数size，最大容量capacity,当数据个数等于最大容量时，说明队列已满，当数据个数size为0时，说明队列为空。

typedef struct qNode
{int data;struct qNode* next;
}qNode;typedef struct {qNode* head;qNode* tail;int size;int capacity;
} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* cq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));cq->head=cq->tail=NULL;cq->capacity=k;cq->size=0;return cq;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}qNode* newNode=(qNode*)malloc(sizeof(qNode));newNode->data=value;newNode->next=NULL;if(obj->size==0){obj->head=obj->tail=newNode;}else{obj->tail->next=newNode;obj->tail=newNode;}obj->size++;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}qNode* next=obj->head->next;free(obj->head);obj->head=next;obj->size--;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->head->data;
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->tail->data;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return !obj->size;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->size==obj->capacity;
}
void myCircularQueueFree(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){free(obj);return;}qNode* cur=obj->head;while(cur!=obj->tail){qNode* next = cur->next;free(cur);cur = next;}free(obj);obj=NULL;
}

方法二：使用顺序表解决

使用顺序表，当head==tail时，说明队列为空，当head==tail+1时，说明队列为满。

typedef struct {int* a;int head;int tail;int capacity;
} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* cq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));cq->a = (int*)malloc(sizeof(int)*(k+1));cq->head=cq->tail=0;cq->capacity=k;return cq;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->head==obj->tail;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->tail+1)%(obj->capacity+1)==obj->head;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}obj->a[obj->tail++]=value;obj->tail = obj->tail % (obj->capacity+1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}obj->head++;obj->head=obj->head%(obj->capacity+1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->a[obj->head];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->a[obj->tail];
}
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}

总结

我们今天讲解了栈与队列的笔试题，希望可以得到大家的支持。