大家好,这里是针对栈和队列做的一些总结归类,主要是介绍了栈和队列的相关操作,特意整理出来一篇博客供我们一起复习和学习,如果文章中有理解不当的地方,还希望朋友们在评论区指出,我们相互学习,共同进步!

一：栈

1.1 栈的概念及结构

栈：是一种基于先进后出(FILO)的数据结构，是一种只能在一端进行插入和删除操作的特殊性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据。
压栈：栈的插入操作叫做进栈\压栈\入栈，入数据在栈顶。
出栈：栈的删除操作叫出栈，出数据也在栈顶。

1.2 栈的实现

头文件Stack.h:

typedef int STDataType;typedef struct Stack
{STDataType* a;int top;		// 栈顶的位置int capacity;	// 容量
}ST;void StackInit(ST* ps);//栈初始化
void StackDestory(ST* ps);//销毁栈
void StackPush(ST* ps, STDataType x);//压栈
STDataType StackTop(ST* ps);//出栈
void StackPop(ST* ps);
bool StackEmpty(ST* ps);//判断栈区是否为空
int StackSize(ST* ps);//计算栈的元素

1:栈初始化

void StackInit(ST* ps){assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}

2：销毁栈

void StackDestory(ST* ps){assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}

3：压栈

void StackPush(ST* ps, STDataType x){assert(ps);if (ps->capacity == ps->top){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;ps->a =(STDataType *)realloc(ps->a, newCapacity * sizeof(STDataType));if (!(ps->a)){printf("realloc fail\n");exit(-1);}else{ps->capacity = newCapacity;}}ps->a[ps->top] = x;(ps->top)++;
}

4：出栈

STDataType StackTop(ST* ps){assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}void StackPop(ST* ps){assert(ps);assert(ps->top > 0);(ps->top)--;
}

5：判断栈是否为空

bool StackEmpty(ST* ps){assert(ps);if (ps->top == 0){return true;}else{return false;}
}

6：计算栈内个数

int StackSize(ST* ps){assert(ps);return ps->top;
}

1.3 典型案例

括号匹配问题：LeetCode链接

二：队列

2.1 队列的概念及结构

队列是一种基于先进先出(FIFO)的数据结构,是一种只能在一端进行插入，在另一端进行删除操作的特殊线性结构，它按照先进先出的原则存储数据，先进入的数据，在读取的时候先被读出来。

2.2 队列的实现

队列也可以用数组和链表的结构实现，使用链表的结构会更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

typedef int QDataType;typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;//size_t size;
}Queue;
//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestory(Queue* pq);
//入队列
void QueuePush(Queue* pq, QDataType x);
//出队列
void QueuePop(Queue* pq);
//是否空队列
bool QueueEmpty(Queue* pq);
//队列大小
size_t QueueSize(Queue* pq);
//队头元素
QDataType QueueFront(Queue* pq);
//队尾元素
QDataType QueueBack(Queue* pq);

1：初始化队列

void QueueInit(Queue* pq){assert(pq);pq->head = NULL;pq->tail = NULL;
}

2：销毁队列

void QueueDestory(Queue* pq){assert(pq);QNode * cur = pq->head;while (cur){QNode * Next = cur->next;free(cur);cur = NULL;cur = Next;}pq->head = pq->tail = NULL;
}

3：入队列

void QueuePush(Queue* pq, QDataType x){assert(pq);QNode * newnode = (QNode *)malloc(sizeof(QNode));if (!newnode){printf("malloc fail\n");exit(-1);}else{if (pq->tail == NULL){assert(pq->head == NULL);pq->head = pq->tail = newnode;newnode->data = x;newnode->next = NULL;}else{pq->tail->next = newnode;newnode->data = x;newnode->next = NULL;pq->tail = newnode;}}
}

4：出队列

void QueuePop(Queue* pq){assert(pq);assert(pq->head && pq->tail);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;}
}

5：是否空队列

bool QueueEmpty(Queue* pq){assert(pq);return pq->head == NULL && pq->tail == NULL;
}

6：队列大小

size_t QueueSize(Queue* pq){assert(pq);int count = 0;QNode* cur = pq->head;while (cur){count++;cur = cur->next;}return count;
}

7：队头元素

QDataType QueueFront(Queue* pq){assert(pq);assert(pq->head);return pq->head->data;
}

8：队尾元素

QDataType QueueBack(Queue* pq){assert(pq);assert(pq->tail);return pq->tail->data;
}

深深的感谢您能够看到这里，祝您生活愉快，事业学习进步！！！