栈是只能在表的一端进行插入和删除运算的线性表，通常称插入、删除这一端为栈顶(TOP)，另一端为栈底(BOTTOM)。 当表中没有元素时称为栈空。 栈顶元素总是后被插入(入栈)的元素，从而也是最先被移除(出栈)的元素；栈底元素总是最先被插入的元素，从而也是最后才能被移除的元素。所以栈是个 后进先出(LIFO) 的数据结构
栈的基本运算有三种：入栈、出栈与读栈顶，时间复杂度都是O(1)
#include <stdio.h> #include <stdlib.h> #include <time.h> #define MaxSize 20 typedef struct _Stack { char * top; // 栈首指针 char * end; // 栈尾指针 }Stack , *pStack; // ====================顺序栈的功能封装===================================== void InitStack (pStack *p); // 初始化指针 void PushStack (pStack , char ch); // 压栈 void PopStack (pStack p , char *ch);//出栈 int LenStack (pStack p ); // 栈的长度 void TraStack (pStack p); // 遍历栈区 void DestroyStack (pStack p); // 释放栈区 int main () { pStack one = (pStack) malloc (sizeof(Stack)); InitStack (one); DestroyStack (one); return 0; } void InitStack (pStack *p ) { (*p)->top = (char *)malloc(sizeof(char)*MaxSize); (*p)->end = (*p)->top; } void PushStack (pStack p , char ch) { *(p->end) = ch; p->end++; } void PopStack (pStack p , char *ch) { p->end--; (*ch)=*(p->end); } int LenStack (pStack p ) { int i=0 ; char * pl=p->top; while (pl!=p->end) { pl++; i++; } return i; } void TraStack (pStack p) { char * str; str = p->top; while (str != p->end) { printf ("%c -> " , *str); str++; } printf ("End\n"); } void DestroyStack (pStack p) { free (p->top); }队列是只允许在一端删除，在另一端插入的顺序表，允许删除的一端叫做队头，用对头指针 frontfront 指向对头元素的下一个元素。 允许插入的一端叫做队尾，用队尾指针 rearrear 指向队列中的队尾元素。 因此，从排头指针 frontfront 指向的下一个位置直到队尾指针 rearrear 指向的位置之间所有的元素均为队列中的元素。
传统形式的队列机制使用链表更加合适，使得内存得到合理的利用和释放。
#ifndef queue_Header_h #define queue_Header_h #include <stdio.h> #include <stdlib.h> #include <stdbool.h> //队列的结点结构 typedef struct Node{ int data; struct Node *next; } Node, *Queue; //队列的结构，嵌套 typedef struct{ Queue front; Queue rear; } LinkQueue; //初始化 //开始必然是空队列，队尾指针和队头指针都指向头结点 void initQueue(LinkQueue *queue) { //初始化头结点 queue->front = queue->rear = (Queue)malloc(sizeof(Node)); if (NULL == queue->front) { exit(0); } queue->front->next = NULL; } //判空 bool isEmpty(LinkQueue queue) { return queue.rear == queue.front ? true : false; } //入队,只在一端入队，另一端出队，同样入队不需要判满 void insertQueue(LinkQueue *queue, int temp) { Queue q = (Queue)malloc(sizeof(Node)); if (NULL == q) { exit(0); } //插入数据 q->data = temp; q->next = NULL; //rear 总是指向队尾元素 queue->rear->next = q; queue->rear = q; } //出队，需要判空 void deleteQueue(LinkQueue *queue) { Queue q = NULL; if (!isEmpty(*queue)) { q = queue->front->next; queue->front->next = q->next; //这句很关键，不能丢 if (queue->rear == q) { queue->rear = queue->front; } free(q); } } //遍历 void traversal(LinkQueue queue) { int i = 1; Queue q = queue.front->next; while (q != NULL) { printf("队列第%d个元素是：%d\n", i, q->data); q = q->next; i++; } } //销毁 void destoryQueue(LinkQueue *queue) { while (queue->front != NULL) { queue->rear = queue->front->next; free(queue->front); queue->front = queue->rear; } puts("销毁成功！"); } #endif普通的队列只能使用链表的形式来实现，如果是使用数组来实现，过程中由于在单方向自曾问题将导致最终栈溢出。
如果想要通过数组来实现队列，则可以考虑循环队列的方式。
但是循环队列需要区分空队列还是满队列。
这是空循环队列的样子：
这是满循环队列的样子:
解决办法：
另设一个布尔变量以区别队列的空和满；少用一个元素的空间，约定入队前测试尾指针在循环下加 1 后是否等于头指针，若相等则认为队满；（最常用）使用一个计数器记录队列中元素的总数。 #ifndef ___queue_Header_h #define ___queue_Header_h #include <stdio.h> #include <stdlib.h> #define MAX_SIZE 5 typedef struct{ int *base; int rear;//如果队列不空，指向队尾元素的下一个位置 int front;//初始的时候指向表头 } CirularQueue; //初始化 void initQueue(CirularQueue *queue) { queue->base = (int *)malloc(MAX_SIZE*sizeof(int)); if (NULL == queue->base) { exit(0); } queue->front = queue->rear = 0; } //求长度 int getLength(CirularQueue queue) { //这样把所以的情况都考虑到了 return (queue.rear - queue.front + MAX_SIZE) % MAX_SIZE; } //入队，先判满 void insertQueue(CirularQueue *queue, int e) { if ((queue->rear + 1) % MAX_SIZE == queue->front) { puts("循环队列是满的！"); } else { queue->base[queue->rear] = e; queue->rear = (queue->rear + 1) % MAX_SIZE; } } //出队 void deleteQueue(CirularQueue *queue) { if (queue->front == queue->rear) { puts("队列是空的！"); } else { queue->front = (queue->front + 1) % MAX_SIZE; } } //遍历 void traversal(CirularQueue queue) { int q = queue.front; for (int i = 0; i < getLength(queue); i++) { printf("循环队列的第%d个元素为%d\n", i + 1, queue.base[q]); q++; } } #endif