一、什么是栈和队列
（1）栈：
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素————百度百科
由此可见栈是一种先进后出（First In Last Out）即FILO结构。
（2）队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头————百度百科
队列是一种先进先出（First In First Out）的结构即FIFO结构。
二、线性栈的操作实现
栈可分为线性栈和链式栈，不同的实现方法匹配于不同的场景。
（1）栈的结构定义：
typedef int STDataType; typedef struct Stack { STDataType* a;//线性栈需要数组 int top;//栈顶指针记录元素个数 int capacity;//栈的容量 }ST;
（2）栈的初始化：
ST* InitNewStack(STDataType n) { ST* p = (ST*)malloc(sizeof(ST));//初始化生成栈 p->a = (STDataType*)malloc(sizeof(STDataType) * n);//对栈的数组进行开辟 if (p->a == NULL)//开辟检查 { perror("malloc"); exit(-1); } p->top = -1;//将指针置为-1，也可以为0，只不过后续实现有稍微不同 p->capacity = n;//将容量设置好 return p;//返回新的栈 }
（3）入栈操作：
void StackPush(ST* st, STDataType x) { assert(st); if (st->top == st->capacity)//检查栈是否满了 { STDataType* tmp = (STDataType*)realloc(st->a, sizeof(st->capacity) * 2 * sizeof(STDataType));//栈满了进行扩容操作 if (tmp == NULL)//扩容检查 { perror("realloc"); exit(-1); } st->a = tmp; st->capacity *= 2;//将容量记录扩大 } st->a[++st->top] = x;//对元素进行入栈，栈顶元素+1 }
（4）出栈操作：
void StackPop(ST* st) { assert(st);//断言是否为空栈 if (st->top >= 0) st->top -= 1;//只要不为空栈，仅仅将栈顶指针-1即可 return; }
（5）栈判空：
bool StackEmpty(ST* st) { assert(st); return st->top == -1;//当top为-1表示空栈 }
（6）取栈顶元素：
STDataType StackFront(ST* st) { assert(st); return st->a[st->top];//直接返回栈顶元素即可 }
（7）打印栈：
void Print(ST* st)//进行打印 { assert(st); int len = sizeof(st->a) / sizeof(STDataType); int i = 0; for (i = 0; i <= st->top; i++) { printf("%3d", i); } printf("\n"); for (i = 0; i <= st->top; i++) { printf("---"); } printf("\n"); for (i = 0; i <= st->top; i++) { printf("%3d", st->a[i]); } printf("\n\n\n"); return; }
（8）销毁栈：
void StackClear(ST* st)//由内而外进行销毁，防止内存泄漏 { assert(st); free(st->a); st->a = NULL; free(st); st = NULL; return; }
（9）测试栈：
void Test() { ST* st = InitNewStack(MAX_OP); int i = 0; StackPush(st, 1); if (!StackEmpty(st)) { StackPush(st, 2); StackPush(st, 3); StackPush(st, 4); StackPush(st, 5); StackPush(st, 6); StackPush(st, 7); StackPush(st, 8); Print(st); } if (!StackEmpty(st)) { StackPop(st); StackPop(st); StackPop(st); Print(st); } printf("StackFront: %d\n", StackFront(st)); StackClear(st); return; }
结果打印为：
怎么样，栈的操作实现是不是挺简单的，也没有想象的那么难，下面我们看看链式栈的实现方式吧。
三、链式栈的操作实现
（1）栈的结构定义：
typedef int STDataType; typedef struct STNode {//栈的元素 struct STNode* next;//指针域 STDataType data;//数据域 }Node; typedef struct Stack {//栈顶指针 Node* top; }ST;
（2）栈的初始化：
Node* InitNewNode(STDataType x)//栈节点的初始化 { Node* p = (Node*)malloc(sizeof(Node));//开辟新节点 if (p == NULL)//节点检查 { perror("malloc"); exit(-1); } p->next = NULL;//指针域置空 p->data = x;//数据域赋值 return p;//返回新节点 } void InitNewST(ST* st) { assert(st); st->top = NULL;//将栈顶指针置空 return; }
（3）入栈操作：
void StackPush(ST* st, STDataType x) { assert(st); if (st->top == NULL)//栈顶指针为空时 { Node* node = InitNewNode(x); st->top = node; return; } Node* node = InitNewNode(x); node->next = st->top;//头插法入栈 st->top = node;//栈顶指针指向头节点 return; }
（4）出栈操作：
void StackPop(ST* st) { assert(st); if (st->top == NULL)//空栈直接返回 return; if (st->top->next)//栈的元素大于1个 { Node* tmp = st->top;//直接进行头删 st->top = tmp->next;//指针指向下一个节点 free(tmp); return; } free(st->top);//只有一个节点直接删除，并将top置空 st->top = NULL; return; }
（5）栈判空：
bool StackEmpty(ST* st) { assert(st); return st->top == NULL;//top不为空指针 }
（6）取栈顶元素：
Node* StackTop(ST* st) { assert(st); return st->top;//直接返回栈顶节点 }
（7）打印栈：
void output(ST* st) { assert(st); Node* p = st->top; int len = 0; while (p) { p = p->next; len += 1; } int i = 0; for (i = 0; i < len; i++) { printf("%3d", i); printf(" "); } printf("\n"); for (i = 0; i < len; i++) { printf("-----"); } printf("\n"); p = st->top; while (p) { printf("%3d", p->data); printf("->"); p = p->next; } printf("\n\n\n"); return; }
（8）销毁栈：
void StackDestroy(ST* st) { assert(st); while (st->top) { Node* tmp = st->top->next;//记录栈顶指针的下一个元素 free(st->top);//释放掉当前元素 st->top = tmp;//再把栈顶指针指向下一个元素 } return; }
（9）测试栈：
void Test() { ST st; InitNewST(&st); StackPush(&st, 5); StackPush(&st, 4); StackPush(&st, 3); StackPush(&st, 2); StackPush(&st, 1); output(&st); if (!StackEmpty(&st)) { StackPop(&st); StackPop(&st); output(&st); } Node* p = StackTop(&st); printf("The Stack Top Element is %d\n", p->data); StackDestroy(&st); return; }
测试结果：
四、队列的操作实现
这里队列就不实现线性队列了，线性队列可以参考上面的线性栈来写，这里主要实现一下链式队列
（1）队列的结构定义：
typedef int QDataType; typedef struct QueueNode {//链式队列节点 struct QueueNode* next; QDataType data; }QNode; typedef struct Queue {//队列 QNode* head;//队列头指针 QNode* tail;//队列尾指针 int size;//大小 }Que;
（2）队列的初始化：
void InitNewQueue(Que* q) { assert(q); q->head = q->tail = NULL;//头尾节点置空 q->size = 0;//初始化长度为0 return; }
（3）入队操作：
void QueuePush(Que* q, QDataType x) { assert(q); QNode* newnode = (QNode*)malloc(sizeof(QNode));//开辟新的链式队列节点 if (newnode == NULL)//检测是否开辟失败 { perror("malloc"); exit(-1); } newnode->data = x; newnode->next = NULL; if (q->tail == NULL)//尾指针为空即队列为空 { q->head = q->tail = newnode;//头尾指针指向同一个元素 } else//队列不为空 { q->tail->next = newnode;//入队 q->tail = newnode; } q->size++;//记录大小 return; }
（4）出队操作：
void QueuePop(Que* q) { assert(q); if (q->head->next == NULL)//只有一个节点 { free(q->head); q->head = q->tail = NULL;//将头尾节点置空 } else//大于一个节点数量 { QNode* next = q->head->next;//记录头指针下一个节点 free(q->head);//释放当前节点 q->head = next;//头指针移动 } q->size -= 1;//记录大小 return; }
（5）队列判空：
bool QueueEmpty(Que* q) { assert(q); return q->head == NULL; }
（6）取队首队尾元素：
QDataType QueueFront(Que* q) { assert(q); assert(!QueueEmpty(q));//不为空队列直接返回头指针数据域 return q->head->data; } QDataType QueueBack(Que* q) { assert(q); assert(!QueueEmpty(q));//不为空队列直接返回尾指针数据域 return q->tail->data; }
（7）队列大小：
QDataType QueueSize(Que* q) { assert(q); return q->size; }
（8）销毁队列：
void QueueDestroy(Que* q) { assert(q); while (q->head)//头指针不为空 { QNode* tmp = q->head->next;//记录下头指针下一个节点 free(q->head);//释放当前节点 q->head = tmp; } q->head = q->tail = NULL;//头尾指针置空 q->size = 0;//数量清零 return; }
（9）测试队列：
void Test() { Que q; InitNewQueue(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); QueuePush(&q, 5); QueuePush(&q, 6); printf("QueueSize : %d\n", QueueSize(&q)); while (!QueueEmpty(&q)) { printf("%d ", QueueFront(&q)); QueuePop(&q); } printf("\n"); QueueDestroy(&q); return; }
输出结果为：
如果你看到这里，觉得这篇文章对你有帮助的话，还望能三连支持一下~~
