数据结构OJ题——栈和队列

1. 用栈实现队列（OJ链接）

题目描述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

假设入队的顺序是1，2，3，4，5，那么出队的顺序也需要是1，2，3，4，5
栈的性质是先进后出，但是我们有两个栈，如果把数据pop到另一个栈中，再出数据，那么会怎么样呢？

看下图。

此时我们从stack2中出数据会发现，出队的顺序变成了1，2，3，4，5
此时需要进数据的话，就需要进入到stack1，当stack2为空时，若需要pop数据，则将stack1的数据倒到stack2中再进行pop。

那么push和pop操作就可以理解为：有两个栈，stack1和stack2，push数据时永远push到stack1中，pop数据从stack2中pop，如果stack2为空，那么将stack1中的数据全部倒到stack2中，再进行pop。

peek操作为获取队头元素，由于经过一轮的倒入，再stack2中的栈顶数据就是队头了，直接返回该数据即可，如果stack2为空，则需要先从stack1中入数据到stack2中。

判空操作：两个栈都为空，那么队列就为空。

用栈实现队列，我们需要一个栈的数据结构，之前已经写过了，这里直接拷贝过来用即可。
完整代码如下

typedef int STDataType;typedef struct StackNode
{int capacity;      //最大容量int top;           //栈顶数据的下一个位置STDataType* arr;   //数组
}STNode;//初始化顺序栈
void StackInit(STNode* ps)
{ps->arr = NULL;ps->capacity = 0;ps->top = 0;
}
//销毁栈
void StackDestroy(STNode* ps)
{free(ps->arr);ps->arr = NULL;ps->capacity = ps->top = 0;
}
//入栈
void StackPush(STNode* ps, STDataType x)
{//没有空间或者空间满了，先扩容if (ps->capacity == ps->top){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->arr,sizeof(STNode) * newcapacity);if (tmp == NULL){perror("malloc()");return;}ps->arr = tmp;ps->capacity = newcapacity;}//插入数据ps->arr[ps->top++] = x;}
//出栈
void StackPop(STNode* ps)
{ps->top--;
}
//判断栈空
bool StackEmpty(STNode* ps)
{return ps->top == 0;
}
//获得栈顶元素
int FindTop(STNode* ps)
{return ps->arr[ps->top - 1];
}typedef struct 
{STNode stack1;//push数据的栈STNode stack2;//pop数据的栈
} MyQueue;MyQueue* myQueueCreate() 
{MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));StackInit(&obj->stack1);StackInit(&obj->stack2);return obj;
}void myQueuePush(MyQueue* obj, int x) 
{StackPush(&obj->stack1,x);
}int myQueuePop(MyQueue* obj) 
{//栈一不是空，栈二是空if(!StackEmpty(&obj->stack1)&&StackEmpty(&obj->stack2)){//将数据移到栈二while(!StackEmpty(&obj->stack1)){StackPush(&obj->stack2,FindTop(&obj->stack1));StackPop(&obj->stack1);}int ret=FindTop(&obj->stack2);StackPop(&obj->stack2);return ret;}//栈二有数据，直接popelse{int ret=FindTop(&obj->stack2);StackPop(&obj->stack2);return ret;}
}int myQueuePeek(MyQueue* obj) 
{//栈二没有数据if(StackEmpty(&obj->stack2)){//将栈一的数据移到栈二while(!StackEmpty(&obj->stack1)){StackPush(&obj->stack2,FindTop(&obj->stack1));StackPop(&obj->stack1);}}//返回栈顶数据return FindTop(&obj->stack2);
}bool myQueueEmpty(MyQueue* obj) 
{return StackEmpty(&obj->stack1)&&StackEmpty(&obj->stack2);
}void myQueueFree(MyQueue* obj) 
{StackDestroy(&obj->stack1);StackDestroy(&obj->stack2);free(obj);
}

代码虽然看着很长，但是其中三分之二都是之前写过的，这里只是拿来运用而已。下一题也是如此。

2. 用队列实现栈（OJ链接）

题目描述：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

假设入队数据1，2，3，4，5由于需要实现栈，那么出数据的顺序需要是5，4，3，2，1，效仿上一题，将数据倒入到另一个队列后，发现再出数据还是1，2，3，4，5，因此这个方法不适用了。

需要出的数据是5，所以可以考虑把1，2，3，4倒入到另一个队列，再把5出出去。把1，2，3倒回来，把4再出出去，循环就可以实现出数据的顺序为5，4，3，2，1了

过程如图所示

最终的数据序列就是5，4，3，2，1

push数据时，需要往非空的队列内push，需要后进先出。

pop数据时需要将非空队列的前n-1个数据入到空队列里（假设非空队列有n个数据），再pop最后一个数据。

top：栈顶数据就是非空队列的队尾

empty：两个队列都为空，则栈为空

完整代码如下

typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);void QueuePush(Queue* pq,QDataType x);
void QueuePop(Queue* pq);
int QueueSize(Queue* pq);QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);bool QueueEmpty(Queue* pq);//初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}
//销毁队列
void QueueDestroy(Queue* 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(Queue* pq, QDataType x)
{assert(pq);//创建新节点QNode* newNode = (QNode*)malloc(sizeof(QNode));if (newNode == NULL){return;}newNode->val = x;newNode->next = NULL;//队列为空if (pq->head == NULL){pq->head = pq->tail = newNode;}//队列不为空else{pq->tail->next = newNode;pq->tail = newNode;}pq->size++;
}
//队头出队
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));   //队列不能为空//只有一个结点if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* cur = pq->head->next;  //保留第二个结点free(pq->head);pq->head = cur;}pq->size--;
}
//队列大小
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
//队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->val;
}
//队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->val;
}
//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}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) 
{//找到空的队列Queue* Empty=&obj->q1;Queue* NotEmpty=&obj->q2;if(!QueueEmpty(&obj->q1)){Empty=&obj->q2;NotEmpty=&obj->q1;}//将非空队列前n-1个数据导入到空队列while(QueueSize(NotEmpty)>1){QueuePush(Empty,QueueFront(NotEmpty));QueuePop(NotEmpty);}//pop掉最后一个int popData=QueueFront(NotEmpty);QueuePop(NotEmpty);return popData;}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);
}

同样，三分之二的代码是之前写过的，这里只需要拷贝过来使用即可。
运行结果如下图

3. 设计循环队列（OJ链接）

题目描述：循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

假设k等于5，即队列的长度等于5，最多存五个数据。
这里采用数组来实现循环队列。

定义的结构体类型如下

typedef struct {int* a;      //数组int front;   //指向队头int tail;    //指向队尾下一个位置int k;       //队列元素个数
} MyCircularQueue;

开辟k个空间会有上述的歧义，所以选择多开一个空间，即开辟k+1个空间，那么队列为空时是front=tail

将上面两种情况综合，队列为满时判断条件是 ( tail + 1 ) % ( k + 1 ) = front;

出队和入队也需要注意下标的回绕，也就是求余操作，也可以使用判断语句。

完整代码如下

typedef struct {int* a;      //数组int front;   //指向队头int tail;    //指向队尾下一个位置int k;       //队列元素个数
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a=(int*)malloc(sizeof(int)*(k+1));obj->front=obj->tail=0;obj->k=k;return obj;
}//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front==obj->tail;
}
//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->tail+1)%(obj->k+1)==obj->front;
}
//入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//队列满了if(myCircularQueueIsFull(obj)){return false;}//入队obj->a[obj->tail++]=value;//下标回绕if(obj->tail==obj->k+1){obj->tail=0;}return true;
}
//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//队列为空if(myCircularQueueIsEmpty(obj)){return false;}//出队obj->front++;//下标回绕if(obj->front==obj->k+1){obj->front=0;}return true;
}
//队头元素
int myCircularQueueFront(MyCircularQueue* obj) {//空队列返回-1if(myCircularQueueIsEmpty(obj)){return -1;}return obj->a[obj->front];
}
//队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {//空队列返回-1if(myCircularQueueIsEmpty(obj)){return -1;}//返回最后一个值if(obj->tail==0){return obj->a[obj->k];}return obj->a[obj->tail-1];
}
//释放空间
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}