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