栈
栈的基本概念
1.栈的定义
栈(Stack)是只允许在一端进行插入或删除操作的线性表。
栈顶(Top)。允许插入和删除的一端。入数据，出数据都在栈顶。
栈底(Bottom)。固定的，不允许插入和删除的一端。
空栈。不含任何元素的空表。
栈的操作特性可以明显概括为后进先出。
栈的插入操作，叫做进栈，也叫压栈，入栈。栈的删除操作，叫做出栈，有点叫做弹栈。
栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小。
栈的结构体可以描述为
typedef int stackData;
typedef struct stack
{stackData* val;int size;int cakacity;
}stack;栈的基本算法
*初始化
void SKinit(stack* head) {head->val = (stackData*)malloc(sizeof(stackData) * 4);assert(head->val);head->size = 4;//栈存储空间的大小head->top = 0;//top是栈顶元素的下一个位置
}*判空
bool SKEmpty(stack* pHead) {return pHead->top == 0;
}*获取栈顶元素
stackData StackTop(stack* ps) {assert(ps);return ps->val[ps->top - 1];
}进栈和出栈
*进栈
void SKpush(stack* pHead, stackData x) {assert(pHead);stack* head = pHead;if (head->top == head->size) {//判断是否需要扩容stackData* p1 = (stackData*)realloc(head->val,sizeof(stackData) * head->size * 2);assert(p1);head->val = p1;head->size *= 2;}head->val[head->top] = x;head->top++;}*出栈
stackData SKPop(stack* pHead) {assert(pHead);stack* head = pHead;stackData date = head->val[head->top - 1];head->top--;return date;
}*获取栈中有效元素个数
int SKsize(stack* pHead)
{return pHead->top;
}
*销毁栈
void SKdestory(stack* pHead)
{while (pHead->top) {SKPop(pHead);}
}
队列
队列的基本概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)。
队头（Front）：允许删除的一端，又称队首。
队尾（Rear）：允许插入的一端。
空队列：不包含任何元素的空表。
入队列：进行插入操作的一端称为队尾。
出队列：进行删除操作的一端称为队头。
队列实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
队列的结构体可以描述为
typedef char QDatatype;typedef struct QueueNode
{struct QueueNode* next;QDatatype data;
}QNode;typedef struct Queue
{QNode* head; //头节点QNode* tail; //尾节点int size;
}Queue;
*初始化
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}*队尾入队列
void QueuePush(Queue* pq, QDatatype x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}*队头出队列
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head != NULL);if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}*获取队列队头元素
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;
}*判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}*获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
*销毁队列
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;
}循环队列
我们把队列的这种头尾相接的顺序存储结构称为循环队列。用来解决队列的假溢出问题。环形队列可以使用数组实现，也可以使用循环链表实现。
以数组为数据存储模型比链表实现方便的多。所以本篇以数组为例。
front：只需要保存队头元素在数组中的下标即可。
rear：保存队尾元素的下一个下标，这样可以保证队列位空时rear和front的下标相同，队列满时front是rear的下一位。
为了区分队空还是队满的情况，有三种处理方式：
（1）牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是种较为普遍的做法，约定以“队头指针在队尾指针的下一位置作为队满的标志”。
队满条件： (Q->rear + 1)%Maxsize == Q->front
队空条件仍： Q->front == Q->rear
队列中元素的个数： (Q->rear - Q ->front + Maxsize)% Maxsize
（2）类型中增设表示元素个数的数据成员。这样，队空的条件为 Q->size == O ；队满的条件为 Q->size == Maxsize 。这两种情况都有 Q->front == Q->rear
（3）类型中增设tag 数据成员，以区分是队满还是队空。tag 等于0时，若因删除导致 Q->front == Q->rear ，则为队空；tag 等于 1 时，若因插入导致 Q ->front == Q->rear ，则为队满。
这里我们重点讨论第一种方法
实现
typedef int ElemType;
#define MAXSIZE 50
/*循环队列的顺序存储结构*/
typedef struct{ElemType data[MAXSIZE];int front; //头指针int rear; //尾指针,若队列不空，指向队列尾元素的下一个位置
}SqQueue;
*初始化
/*初始化一个空队列Q*/
void InitQueue(SqQueue *Q){Q->front = 0;Q->rear = 0;return;
}
*判空
bool isEmpty(SqQueue Q)
{if(Q.rear == Q.front)return true;return false;}
*求长度
int QueueLength(SqQueue Q)
{return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}
*入队列
/*若队列未满，则插入元素e为Q新的队尾元素*/
bool InQueue(SqQueue *Q, ElemType e){if((Q->rear + 1) % MAXSIZE == Q->front){return false; //队满}Q->data[Q->rear] = e; //将元素e赋值给队尾Q->rear = (Q->rear + 1) % MAXSIZE; //rear指针向后移一位置，若到最后则转到数组头部return true;
}
*出队列
/*若队列不空，则删除Q中队头元素，用e返回其值*/
bool OutQueue(SqQueue *Q, ElemType *e)
{if(isEmpty(Q)){return false; //队列空的判断}*e = Q->data[Q->front]; //将队头元素赋值给eQ->front = (Q->front + 1) % MAXSIZE; //front指针向后移一位置，若到最后则转到数组头部return true;
}
栈和队列间相互转换
栈模拟实现队列
可以利用两栈后入先出的特性，先用栈1把入队列的值存起来，在存起来后，就把栈1的值出栈到栈2中进行保存，这样就完成栈中底部的值变为顶部的值了。
代码示例
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int stackData;
typedef struct stack
{stackData* val;int size;int top;
}stack;//栈的结构体typedef struct {stack* stack1;//接收数据stack* stack2;//出数据
} MyQueue;//栈模拟的队列//栈函数的实现
void SKinit(stack** head) {*head = (stack*)malloc(sizeof(stack));assert(*head);(*head)->val = (stackData*)malloc(sizeof(stackData) * 4);assert((*head)->val);(*head)->size = 4;(*head)->top = 0;
}
//入栈
void SKpush(stack* pHead, stackData x) {assert(pHead);stack* head = pHead;if (head->top == head->size) {stackData* p1 = (stackData*)realloc(head->val,sizeof(stackData) * head->size * 2);assert(p1);head->val = p1;head->size *= 2;}head->val[head->top] = x;head->top++;}
//出栈
stackData SKPop(stack* pHead) {assert(pHead);stack* head = pHead;stackData date = head->val[head->top - 1];head->top--;return date;
}
//销毁
void SKdestory(stack* pHead) {while (pHead->top) {SKPop(pHead);}
}
//大小
int SKsize(stack* pHead) {return pHead->top;
}
//判断为空
int SKEmpty(stack* pHead) {return pHead->top == 0;
}
stackData StackTop(stack* ps) {assert(ps);return ps->val[ps->top - 1];
}//队列函数的实现// 创建一个队列
MyQueue* myQueueCreate() {MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); // 为队列分配内存SKinit(&obj->stack1); // 初始化栈1，用于接收数据SKinit(&obj->stack2); // 初始化栈2，用于出数据return obj; // 返回队列对象
}// 入队操作，将元素x压入栈1
void myQueuePush(MyQueue* obj, int x) {SKpush(obj->stack1, x); // 直接将元素压入栈1
}// 出队操作，从栈2中弹出元素
int myQueuePop(MyQueue* obj) {// 如果栈2为空，将栈1中的元素移动到栈2if (obj->stack2->top == 0) {// 从栈1依次弹出元素并压入栈2while (!SKEmpty(obj->stack1)) {stackData n = SKPop(obj->stack1);SKpush(obj->stack2, n);}}// 从栈2中弹出元素return SKPop(obj->stack2);
}// 查看队列头部元素
int myQueuePeek(MyQueue* obj) {// 如果栈2为空，将栈1中的元素移动到栈2if (obj->stack2->top == 0) {while (!SKEmpty(obj->stack1)) {stackData n = SKPop(obj->stack1);SKpush(obj->stack2, n);}}// 返回栈2的栈顶元素return StackTop(obj->stack2);
}// 判断队列是否为空
bool myQueueEmpty(MyQueue* obj) {return (obj->stack2->top == 0) && (obj->stack1->top == 0); // 栈1和栈2都为空时，队列为空
}// 销毁队列，释放所有资源
void myQueueFree(MyQueue* obj) {// 一直出队直到队列为空while (!myQueueEmpty(obj)) {myQueuePop(obj);}// 释放栈1和栈2的内存free(obj->stack1->val);free(obj->stack2->val);free(obj->stack1);free(obj->stack2);// 释放队列对象free(obj);
}
队列模拟实现栈
可以利用两个队列进行互相入队，把队列中的最后一个元素进行返回，这样就完成栈的先入先出的原则了。
代码示例
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>// 定义栈中存储的数据类型
typedef int stackData;// 栈的结构体定义
typedef struct stack {stackData* val; // 动态数组，用来存储栈的元素int size; // 栈的容量int top; // 栈顶元素的索引
} stack;// 初始化栈函数
void SKinit(stack** head) {*head = (stack*)malloc(sizeof(stack));assert(*head); // 确保内存分配成功(*head)->val = (stackData*)malloc(sizeof(stackData) * 4);assert((*head)->val); // 确保内存分配成功(*head)->size = 4;(*head)->top = 0;
}// 入栈操作
void SKpush(stack* pHead, stackData x) {assert(pHead); // 确保栈指针有效stack* head = pHead;// 如果栈满，进行扩容if (head->top == head->size) {// 重新分配内存，栈容量加倍stackData* p1 = (stackData*)realloc(head->val, sizeof(stackData) * head->size * 2);assert(p1); head->val = p1; head->size *= 2; }head->val[head->top] = x;head->top++;
}// 出栈操作
stackData SKPop(stack* pHead) {assert(pHead); // 确保栈指针有效stack* head = pHead;stackData date = head->val[head->top - 1];head->top--;return date;
}// 销毁栈，释放栈中所有数据
void SKdestory(stack* pHead) {while (pHead->top) {SKPop(pHead); // 依次出栈，直到栈为空}
}// 获取栈的大小（栈中的元素个数）
int SKsize(stack* pHead) {return pHead->top; // 栈顶指针即为栈的大小
}// 判断栈是否为空
int SKEmpty(stack* pHead) {return pHead->top == 0; // 如果栈顶指针为0，则栈为空
}// 获取栈顶元素
stackData StackTop(stack* ps) {assert(ps); // 确保栈指针有效return ps->val[ps->top - 1]; // 返回栈顶元素
}// 队列结构体定义
typedef struct {stack* stack1; // 用于接收数据（入队）stack* stack2; // 用于出数据（出队）
} MyQueue;// 创建队列
MyQueue* myQueueCreate() {// 为队列分配内存MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));// 初始化两个栈SKinit(&obj->stack1); // 用于接收数据SKinit(&obj->stack2); // 用于出数据return obj; // 返回队列对象
}// 入队操作，将元素x压入栈1
void myQueuePush(MyQueue* obj, int x) {SKpush(obj->stack1, x); // 将数据压入栈1
}// 出队操作，从栈2弹出元素
int myQueuePop(MyQueue* obj) {// 如果栈2为空，将栈1中的元素转移到栈2if (obj->stack2->top == 0) {// 将栈1中的元素依次弹出并压入栈2while (!SKEmpty(obj->stack1)) {stackData n = SKPop(obj->stack1);SKpush(obj->stack2, n);}}// 从栈2中弹出元素并返回return SKPop(obj->stack2);
}// 查看队列头部元素
int myQueuePeek(MyQueue* obj) {// 如果栈2为空，将栈1中的元素转移到栈2if (obj->stack2->top == 0) {while (!SKEmpty(obj->stack1)) {stackData n = SKPop(obj->stack1);SKpush(obj->stack2, n);}}// 返回栈2的栈顶元素return StackTop(obj->stack2);
}// 判断队列是否为空
bool myQueueEmpty(MyQueue* obj) {return (obj->stack2->top == 0) && (obj->stack1->top == 0); // 栈1和栈2都为空时，队列为空
}// 销毁队列，释放所有资源
void myQueueFree(MyQueue* obj) {// 一直出队直到队列为空while (!myQueueEmpty(obj)) {myQueuePop(obj);}// 释放栈1和栈2的内存free(obj->stack1->val);free(obj->stack2->val);free(obj->stack1);free(obj->stack2);// 释放队列对象free(obj);
}
