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;
}
//栈二有数据，直接pop
else
{
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) {
//空队列返回-1
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->a[obj->front];
}
//队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
//空队列返回-1
if(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);
}
关于栈和队列的题目，就写到这里了。