一、栈的概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
二、栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小。
三、实现栈（数组实现）
typedef int STDataType; struct Stack { STDataType* p; int top; int capacity; }; void StackInit(Stack* ps) { ps->p = (STDataType*)malloc(sizeof(Stack)); ps->top = 0; ps->capacity = 4;
void StackPush(Stack* ps, STDataType data) { if (ps->capacity == ps->top) { //增容 Stack* tmp = realloc(ps->p, sizeof(Stack) * ps->capacity * 2); if (tmp == NULL) { perror("ERROR:"); exit(-1); } ps->p = tmp; tmp = NULL; ps->capacity *= 2; } ps->p[ps->top] = data; ps->top++; }
void StackPop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); ps->top--; }
1. STDataType StackTop(Stack* ps) 2. { 3. assert(ps); 4. assert(!StackEmpty(ps)); 5. return ps->p[ps->top - 1]; 6. }
- bool StackEmpty(Stack* ps)
- {
- return ps->top == 0;
- //空返回1；非空返会0；
- }
void StackDestroy(Stack* ps) { assert(ps); free(ps->p); ps->p = NULL; ps->top = 0; ps->capacity = 0 }
四、队列的概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out)
入队列：进行插入操作的一端称为 队尾
出队列：进行删除操作的一端称为 队头
五：队列的实现
typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Queue;
队列的初始化：void QueueInit(Queue* pq);
void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; }
队列的销毁：void QueueDestroy(Queue* pq);
void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* del = cur; cur = cur->next; free(del); } pq->head = pq->tail = NULL;
入队：void QueuePush(Queue* pq, QDataType x);
void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } else { newnode->data = x; newnode->next = NULL; } if (pq->tail == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } pq->size++; }
出队：void QueuePop(Queue* pq);
void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* del = pq->head; pq->head = pq->head->next; free(del); del = NULL; } pq->size--; }
获取队头元素：QDataType QueueFront(Queue* pq);
QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; }
获取队尾元素：QDataType QueueBack(Queue* pq);
QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; }
判断队列是否为空：bool QueueEmpty(Queue* pq);
bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL && pq->tail == NULL; }
队列的元素个数：int QueueSize(Queue* pq);
int QueueSize(Queue* pq) { assert(pq); return pq->size; }
初次写博客，望大家多多支持鼓励！！！
