Lesson4–栈和队列
【本节目标】
1.栈
2.队列
3.栈和队列面试题
一. 栈
1.1栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的的一端进行插入和删除操作的一端称为栈顶，另一端称为栈底
遵循：“先进后出的原则”
压栈：栈的插入数据叫做进栈/压栈，入数据在栈顶
出栈：栈的删除叫做出栈。出数据也在栈顶
1.2 栈的实现
栈的实现一般可以使用数组或者链表来实现，但是相对而言数组的结构实现更优一点。因为数组再尾部插入数据的代价比较小
//Stack.h
#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
//这里也分静态栈和动态栈，但是这里我们以动态栈为主要typedef int STDataType;typedef struct stack
{int* a; //这里我们的栈是用数组实现的int top; //栈底int capacity;//栈中的真实数据
}ST;//给结构体重新命名void STInit(ST*ps);//向栈插入数据void STDestory(ST* ps);//重置void STPush(ST* ps,STDataType x);//插入数据void STPop(ST* ps);//删除数据int STsize(ST* ps);//栈中数据个数bool STEmpty(ST* ps); //栈中数据是不是为空STDataType STTop(ST* ps);//栈顶数据//Stack.c
#define _CRT_SECURE_NO_WARNINGS
#include"Stack.h"
void STInit(ST* ps)//向栈插入数据
{//这里我们先栈中插入元素，需要保证栈不是NULL;assert(ps);ps->a = (STDataType *)malloc(sizeof(STDataType) * 4);//开辟四个整形的空间if (ps->a==NULL){perror("malloc fail");}ps->capacity = 4;ps->top = 0;//top 是指向栈顶元素的下一个位置//ps->top = -1 top 是栈顶元素位置
}
void STDestory(ST* ps)//重置(销毁栈)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}void STPush(ST* ps, STDataType x)//插入数据
{assert(ps);//我们在头插的时候需要考虑扩容的问题 if (ps->top == ps->capacity){STDataType* tmp = (STDataType *)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");//exit(-1);return ;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;}
void STPop(ST* ps)//删除数据
{assert(ps);assert(!STEmpty(ps));//不等于空就删，等于空就停止//if (ps->top == NULL)//{// return 0;//}//else//{// ps->top--;//这里我们就遵从了栈的后进先出//}ps->top--;//这里我们就遵从了栈的后进先出}
int STsize(ST* ps)//栈中数据个数
{assert(ps);return ps->top;
}
bool STEmpty(ST* ps) //栈中数据是不是为空
{assert(ps);return ps->top == 0;}
STDataType STTop(ST* ps)//返回栈顶数据
{assert(ps);assert(!(STEmpty(ps)));//为空就不能访问了return ps->a[ps->top - 1];}
//text.c
#define _CRT_SECURE_NO_WARNINGS
#include"Stack.h"void test1()
{ST st;//创建栈STInit(&st);//初始化栈STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);STPush(&st, 5); //插入数据//while (ps.top!=0)while (!STEmpty(&st))//不为空的时候我们才来访问{printf("%d ", STTop(&st)); //访问栈区中的元素STPop(&st); //删除头元素}STDestory(&st); //删除栈}void test2(){ST st;//创建栈STInit(&st);//初始化栈STPush(&st, 1);printf("%d\n", STTop(&st)); //访问栈区中的元素STPop(&st); //删除头元素STPush(&st, 2);printf("%d\n", STTop(&st)); //访问栈区中的元素STPop(&st); //删除头元素STPush(&st, 3);printf("%d\n", STTop(&st)); //访问栈区中的元素STPush(&st, 4);printf("%d\n", STTop(&st)); //访问栈区中的元素STPop(&st); //删除头元素STPush(&st, 5); //插入数据printf("%d\n", STTop(&st)); //访问栈区中的元素}int main()
{test1();// 顺序插入，倒叙删除//test2();//插入一个删除一个,或者插入两个删除return 0;
}
二、队列
//queue.h
#pragma once
//这里我们来实现队列的
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
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);//初始化
void QueueDestory(Queue* pq);//重制
void QueuePush(Queue* pq,QDatatype x);//插入
void Queuepop(Queue* pq);//删除
int QueueSize(Queue* pq);//队列中的个数
bool QueueEmpty(Queue* pq);//判断队列是否为空
QDatatype QueueFront(Queue* pq);//头数值
QDatatype QueueBack(Queue* pq);//尾数值//queue.c
#define _CRT_SECURE_NO_WARNINGS
#include"queue.h"
void QueueInit(Queue* pq)//初始化
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}
void QueueDestory(Queue* pq)//重制
{assert(pq);QNode* cur = pq->head;//保存一下头指针while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->size = NULL;pq->size = 0;
}
void QueuePush(Queue* pq ,QDatatype x)//插入
{//插入一个结点我们就需要来mallocQNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return ;}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){//起始结点为NULLassert(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--;}
int QueueSize(Queue* pq)//队列中的个数
{assert(pq);return pq->size;
}
bool QueueEmpty(Queue* pq)//判断队列是否为空
{assert(pq);return pq->size == 0;
}
QDatatype QueueFront(Queue* pq)//头数值
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}
QDatatype QueueBack(Queue* pq)//尾数值
{assert(pq);//这里我们就可以很好的利用了我们创建尾结点的作用return pq->tail->data;
}//text.c
#define _CRT_SECURE_NO_WARNINGS
#include"queue.h"int main()
{Queue q;//创建一个点QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);QueuePush(&q, 5);QueuePush(&q, 6);printf("%d\n", QueueFront(&q));//拿出头printf("%d\n", QueueBack(&q));//拿出尾printf("%d\n", QueueSize(&q));//拿出队列中的个数while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));//拿出头Queuepop(&q); //删除}printf("\n");printf("%d\n", QueueSize(&q));return 0;
}
//以上就是对列的实现