数据结构——栈，队列，及其结构特点应用。

创始人

2024-03-22 03:21:46

✅<1>主页：我的代码爱吃辣
📃<2>知识讲解：数据结构——栈，队列。
🔥<3>创作者：我的代码爱吃辣
☂️<4>开发环境：Visual Studio 2022
🏡<5>系统环境：windows 10
💬<6>前言：今天来学习一下，数据结构中的栈和队列的实现和应用。

🦃一.栈

🐔（1）什么是栈

🐣（2）栈的实现：

🌱（3）.栈的应用

🌾二.队列

🌲（1）什么是队列

🌵 (2)队列的实现

🍄（3）队列的应用：

🦃一.栈

🐔（1）什么是栈

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈，出数据也在栈顶。

🐣（2）栈的实现：

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。因为栈即插入和删除（入栈和出战栈）都是在线性表的尾部进行操作，数组的尾部的插如和删除的时间复杂度都是 O(1) ,而如果是链式结构，去实现栈结构，针对尾插和尾删的时间复杂度都是 O(n) ,而双向循环带头的链表，虽然可以解决这个问题，但是.......

我们将栈的实现分为以下各个部分：

1.栈的定义 (StactInit)

typedef int STDateType;  //数据类型
typedef struct Stact
{STDateType* date; //数组int capacity;   //栈的容量int top;      //栈内数据的个数
}ST;ST* StactInit()
{ST* Stact = (ST*)malloc(sizeof(ST));  //创建栈的结构//栈的结构初始化Stact->capacity = 4; Stact->top = 0;Stact->date = (STDateType*)malloc(sizeof(STDateType)*Stact->capacity);//返回栈return Stact;
}

2.栈的销毁 (StactDestroy)

void StactDestory(ST* Stact)
{assert(Stact);//先释放数组申请的空间free(Stact->date);Stact->date = NULL;Stact->capacity = 0;Stact->top = 0;//在释放栈的结构体空间free(Stact);
}

3.栈的StactPushBank操作 (入栈)

void StactPushBank(ST* Stact, STDateType x)
{//断言Stact,当进行Push时，栈结构必须存在(Stact!=NULL)，//如果不存也就是栈是空(Stact==NULL),那Push的操作就是非法的assert(Stact);//每次对栈的底层是数组，所以每次都要检查是否需要扩容if (Stact->capacity == Stact->top){STDateType* tmp = (STDateType*)realloc(Stact->date, Stact->capacity * 2);if (tmp==NULL){perror("realloc");exit(-1);}Stact->date = tmp;Stact->capacity *= 2;}//将x入栈，数组的栈内数据的个数加一Stact->date[Stact->top++] = x;
}

4.栈的StactPopBank操作 (出栈)

void StactPopBank(ST* Stact)
{assert(Stact);//当栈已经空了，还去出栈就是非法了assert(!StactEmpty(Stact));  Stact->top--;
}

5.栈的 StactTop (得到栈顶元素)

STDateType StactTop(ST* Stact)
{assert(Stact);//当栈已经空了，无法获取栈顶元素assert(!StactEmpty(Stact));return Stact->date[Stact->top - 1];
}

6.栈的StactSize (元素个数)

int StactSize(ST* Stact)
{assert(Stact);return Stact->top;
}

7.栈的判空 (StactEmpty)

bool StactEmpty(ST* stact)
{assert(stact);//当栈内数据个数为0时，栈为空return stact->top == 0;
}

测试：

void Print(ST* Stact)
{assert(Stact);for (int i = 0; i < Stact->top; i++){printf("%d ", Stact->date[i]);}printf("\n");
}
int main()
{ST* Stact= StactInit();StactPushBank(Stact, 100); StactPushBank(Stact, 200); StactPushBank(Stact, 300); StactPushBank(Stact, 400); Print(Stact);printf("StactSize:%d\n",StactSize(Stact));//Pop一次StactPopBank(Stact);Print(Stact);printf("StactSize:%d\n", StactSize(Stact));StactDestory(Stact);return 0;
}

🌱（3）.栈的应用

（1）例题

若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,1

答案：C

分析：选项A，1进1出，2进3进4进，4出3出2出，所以出栈顺序1，4，3，2，选项A正确。

选项B，1进2进，2出，3进3出，4进，4出1出，所以出栈顺序2，3，4，1，选项B正确。

选项C，1进2进3进，3出，此时想要出2，就必须先出栈1，所以选项C错误。

选项D，1进2进3进，3出，4进，4出2出1出，所以出栈顺序3，4，2，1，选项D正确。

（2）例题

LeetCode ———— 20. 有效的括号

题目描述：

思路分析：

遇到左括号就进栈，遇到右括号就出栈，将出栈的左括号与右括号进行匹配，如果匹配成功就继续，如果匹配失败就返回false。

//栈结构
typedef char STDateType;
typedef struct Stact
{STDateType* date;int capacity;int top;
}ST;ST* StactInit();void StactPushBank(ST* Stact, STDateType x);int StactSize(ST* Stact);void StactDestory(ST* Stact);void StactPopBank(ST* Stact);STDateType StactTop(ST* Stact);bool StactEmpty(ST* stact);ST* StactInit()
{ST* Stact = (ST*)malloc(sizeof(ST));Stact->capacity = 4;Stact->top = 0;Stact->date = (STDateType*)malloc(sizeof(STDateType) * Stact->capacity);return Stact;
}void StactPushBank(ST* Stact, STDateType x)
{assert(Stact);if (Stact->capacity == Stact->top){STDateType* tmp = (STDateType*)realloc(Stact->date, Stact->capacity * 2);if (tmp == NULL){perror("realloc");exit(-1);}Stact->date = tmp;Stact->capacity *= 2;}Stact->date[Stact->top++] = x;
}bool StactEmpty(ST* stact)
{assert(stact);return stact->top == 0;
}STDateType StactTop(ST* Stact)
{assert(Stact);assert(!StactEmpty(Stact));return Stact->date[Stact->top - 1];
}void StactPopBank(ST* Stact)
{assert(Stact);assert(!StactEmpty(Stact));Stact->top--;
}void StactDestory(ST* Stact)
{assert(Stact);free(Stact->date);Stact->date = NULL;Stact->capacity = 0;Stact->top = 0;free(Stact);
}int StactSize(ST* Stact)
{assert(Stact);return Stact->top;
}bool isValid(char* s) {//创建栈ST* stact = StactInit();while (*s){//遇到左括号进栈if (*s == '(' || *s == '{' || *s == '['){StactPushBank(stact, *s);s++;}else{	//遇到右括号出栈，如果出栈的括号时，//栈中已经空，此时括号匹配已经失败if (StactEmpty(stact)){StactDestory(stact);return false;}//如果栈不为空，出栈的左括号，与遇到的右括号匹配//如果匹配成功就，继续向后走，匹配失败就返回falsechar ch = StactTop(stact);StactPopBank(stact);if ((ch == '(' && *s == ')') ||(ch == '[' && *s == ']') ||ch == '{' && *s == '}'){s++;}else{StactDestory(stact);return false;}}}//当括号匹配匹配完时，如果栈中还有括号，//也就意味着匹配失败。if (!StactEmpty(stact)){StactDestory(stact);return false;}StactDestory(stact);return true;
}

🌾二.队列

🌲（1）什么是队列

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为队头。

🌵 (2)队列的实现

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

1.队列的定义——QueueInit

由于队列是，队尾入数据，队头出数据，为了方便数据的入队，我们除了队头指针，还会设计一个队尾指针。

typedef int QUDateType;
typedef struct QueueNode
{QUDateType date;struct QueueNode* next;
}QueueNode;typedef struct Queue
{QueueNode* head;QueueNode* tail;int size;
}Queue;void QueueInit(Queue* pque)
{assert(pque);pque->head = NULL;pque->tail = NULL;pque->size = 0;
}
int main()
{Queue Q;QueueInit(&Q);return 0;
}

2.入队操作——QueuePush

void QueuePush(Queue* pque,QUDateType x)
{//断言队列结构，当进行入队操作时，队列结构一定不能为空assert(pque);//申请空间QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc");exit(-1);}//赋值newnode->date = x;newnode->next = NULL;//如果队列为空，此时入队的就是第一个数据，也将是队列的头尾数据if (pque->head == NULL){pque->head = pque->tail = newnode;}//如果队列不为空，就将数据连接到队尾巴后面else{pque->tail->next = newnode;pque->tail = newnode;}//队列中数据个数加一pque->size++;
}

3.队列销毁——QueueDestroy

void QueueDestroy(Queue* pque)
{assert(pque);QueueNode* cur = pque->head;while (cur){QueueNode* nextnode = cur->next;free(cur);cur = nextnode;}pque->head = pque->tail = NULL;
}

4.得到对头数据——QueueFront

QUDateType QueueFront(Queue*pque)
{assert(pque);assert(!QueueEmpty(pque));return pque->head->date;
}

5.队列判空——QueueEmpty

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

6.删除对头数据——QueuePop

void QueuePop(Queue* pque)
{assert(pque);   //队列结构不能为空assert(!QueueEmpty(pque));   //删除数据时队列不能为空 //队列中只有一个数据的时候if (pque->head->next == NULL){free(pque->head);pque->tail = pque->head = NULL;}//队列中数据个数大于1else{QueueNode* popnode = pque->head;pque->head = pque->head->next;free(popnode);}//数据个数减一pque->size--;
}

7.得到队尾数据——QueueBack

QUDateType QueueBack(Queue* pque)
{assert(pque);assert(!QueueEmpty(pque));return pque->tail->date;
}

8.得到队列中数据个数——QueueSize


int QueueSize(Queue* pque)
{assert(pque);return pque->size;
}

测试：

int main()
{Queue Q;QueueInit(&Q);//插如100 .200 300 ，400 ，QueuePush(&Q, 100);QueuePush(&Q, 200);QueuePush(&Q, 300);QueuePush(&Q, 400);//输出队头数据printf("%d ", QueueFront(&Q));//输出队尾数据printf("%d ", QueueBack(&Q));//输出队列数据个数printf("%d \n", QueueSize(&Q));//输出队列中的数据while (!QueueEmpty(&Q)){printf("%d ", Q.head->date);QueuePop(&Q);}//队列销毁QueueDestroy(&Q);return 0;
}

🍄（3）队列的应用：

LeetCode——225. 用队列实现栈

题目描述：

思路：

每次入队数据都需要从不为空的队列进，这样可以保证

Push：进栈，对应到两个队列的操作就是，入不为空的队列。

Top：得到栈顶数据，对应到两个队列的操作就是，得到两个队列中不为空的队列的队尾数据。

Pop：删除栈顶数据，对应的两个队列的操作就是，删除不为空队列的队尾数据元素，但是由于队列结构的原因，要想删除队尾数据，就要先删除队尾前面的数据，所以我们可以先将队尾前面的数据放到另外一个空队列，再将队尾数据删除。

Empty：判断栈是否为空，对应的两个队列的操作就是，只有两个队列都已经没有数据时，栈才为空。

代码：

//队列结构
typedef int QUDateType;
typedef struct QueueNode
{QUDateType date;struct QueueNode* next;
}QueueNode;typedef struct Queue
{QueueNode* head;QueueNode* tail;int size;
}Queue;void QueueInit(Queue* pque)
{assert(pque);pque->head = NULL;pque->tail = NULL;pque->size = 0;
}
//进队列
void QueuePush(Queue* pque,QUDateType x)
{assert(pque);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->date = x;newnode->next = NULL;if (pque->head == NULL){pque->head = pque->tail = newnode;}else{pque->tail->next = newnode;pque->tail = newnode;}pque->size++;
}
//队列为空
bool QueueEmpty(Queue* pque)
{assert(pque);return pque->head == NULL && pque->tail == NULL;
}
//得到对头数据
QUDateType QueueFront(Queue*pque)
{assert(pque);assert(!QueueEmpty(pque));return pque->head->date;
}
//得到队尾数据
QUDateType QueueBack(Queue* pque)
{assert(pque);assert(!QueueEmpty(pque));return pque->tail->date;
}
//队列数据个数
int QueueSize(Queue* pque)
{assert(pque);return pque->size;
}
//删除队头数据
void QueuePop(Queue* pque)
{assert(pque);assert(!QueueEmpty(pque));//队列中只有一个数据的时候if (pque->head->next == NULL){free(pque->head);pque->tail = pque->head = NULL;}else{QueueNode* popnode = pque->head;pque->head = pque->head->next;free(popnode);}pque->size--;
}
//队列销毁
void QueueDestroy(Queue* pque)
{assert(pque);QueueNode* cur = pque->head;while (cur){QueueNode* nextnode = cur->next;free(cur);cur = nextnode;}pque->head = pque->tail = NULL;
}
//封装两个队列
typedef struct {Queue q1;Queue q2;
} MyStack;//创建栈
MyStack* myStackCreate() {MyStack*Q=(MyStack*)malloc(sizeof(MyStack));QueueInit(&Q->q1);QueueInit(&Q->q2);return Q;
}//将元素 x 压入栈顶。
void myStackPush(MyStack* obj, int x) {//找到空队列与非空队列QueueNode*empty=&obj->q1;QueueNode*noempty=&obj->q2;if(!QueueEmpty(&obj->q1)){empty=&obj->q2;noempty=&obj->q1;}//将数据入空队列QueuePush(noempty,x);
}
//删除栈顶数据
int myStackPop(MyStack* obj) {assert(obj);//找到空队列与非空队列QueueNode*empty=&obj->q1;QueueNode*noempty=&obj->q2;if(!QueueEmpty(&obj->q1)){empty=&obj->q2;noempty=&obj->q1;}//将非空队列只留一个数据，其他的全部出队到空队列while(QueueSize(noempty)>1){QueuePush(empty,QueueFront(noempty));QueuePop(noempty);}//返回非空队列的最后一个数据int ret=QueueFront(noempty);QueuePop(noempty);return ret;
}
//返回栈顶数据
int myStackTop(MyStack* obj) {assert(obj);QueueNode*empty=&obj->q1;QueueNode*noempty=&obj->q2;if(!QueueEmpty(&obj->q1)){empty=&obj->q2;noempty=&obj->q1;}return QueueBack(noempty);
}
//栈判空
bool myStackEmpty(MyStack* obj) {assert(obj);return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
//销毁栈
void myStackFree(MyStack* obj) {assert(obj);QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}

测试：

2.LeetCode——622. 设计循环队列

题目描述：

思路:在设计循环队列的时候，我们可以使用数组，或者链表都是可以的，这里我们就使用数组来实现循环队列。

1.MyCircularQueue（结构）

typedef struct {int *date;//最后一个数据的下一个坐标int tail;//头指针int head;循环队列的容量int k;
} MyCircularQueue;

2.MyCircularQueue(k)(创建)

在设计循环队列的时候，我们设计队列的容量时多开一个容量，目的是为了更好的分清队空和队满，队空和队满的时候，头尾坐标都会指在同一位置上。

MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*Q=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));Q->date=(int *)malloc(sizeof(int)*(k+1));Q->tail=0;Q->head=0;Q->k=k;return Q;
}

3.myCircularQueueEnQueue（入队）

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//先判断队列是否已经满了if(myCircularQueueIsFull(obj)){return false;}//断言判断队列结构assert(obj);//在队尾出数据obj->date[obj->tail++]=value;//当数据尾部已经在数组的最后了，此时在进入数据后，//数据尾巴下标时刻保持在数据尾部的后一个下标的，//就要回到数组的头部位置。if(obj->tail==(obj->k)+1){obj->tail=0;}return true;
}

4.Front(获取对头数据)


int myCircularQueueFront(MyCircularQueue* obj) {assert(obj);//队列不为空，才可以获得数据if(myCircularQueueIsEmpty(obj)){return -1;}return obj->date[obj->head];
}

5.deQueue(删除对头数据)

bool myCircularQueueDeQueue(MyCircularQueue* obj) {assert(obj);//队列不能为空if(myCircularQueueIsEmpty(obj)){return false;}//如果head不在数组的尾部，直接head++obj->head++;//如果head，在数组的最后一个位置，此时head++以后需要循环到数组第一个位置if(obj->head==obj->k+1){obj->head=0;}return true;
}

6.Rear(获得队尾数据)


int myCircularQueueRear(MyCircularQueue* obj) {assert(obj);//首先队列不能为空if(myCircularQueueIsEmpty(obj)){return -1;}//当数据尾在数组开头处，最后一个数据在数组的尾部//此时k就是数组的最后一个数据的下标if(obj->tail-1<0){return obj->date[obj->k];}//如果数据尾部在数组中间或者是在数组尾部，数据尾部就是date[tail-1].return obj->date[obj->tail-1];
}

7.isEmpty(判断队列是否为空)

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {assert(obj);//头尾相等就是空。return obj->tail==obj->head;
}

8.isFull(判断队列是否满)

bool myCircularQueueIsFull(MyCircularQueue* obj) {assert(obj);//当tail在数组的最后一个位置时，head在数组第一个位置。//tail不在数据的最后。return (obj->tail+1)%(obj->k+1)==obj->head;
}

9. 销毁队列


void myCircularQueueFree(MyCircularQueue* obj) {assert(obj);free(obj->date);free(obj);
}

代码：

typedef struct {int *date;int tail;int head;int k;
} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*Q=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));Q->date=(int *)malloc(sizeof(int)*(k+1));Q->tail=0;Q->head=0;Q->k=k;return Q;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}assert(obj);obj->date[obj->tail++]=value;if(obj->tail==(obj->k)+1){obj->tail=0;}return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {assert(obj);if(myCircularQueueIsEmpty(obj)){return false;}obj->head++;if(obj->head==obj->k+1){obj->head=0;}return true;
}int myCircularQueueFront(MyCircularQueue* obj) {assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}return obj->date[obj->head];
}int myCircularQueueRear(MyCircularQueue* obj) {assert(obj);if(myCircularQueueIsEmpty(obj)){return -1;}if(obj->tail-1<0){return obj->date[obj->k];}return obj->date[obj->tail-1];
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {assert(obj);return obj->tail==obj->head;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {assert(obj);return (obj->tail+1)%(obj->k+1)==obj->head;
}void myCircularQueueFree(MyCircularQueue* obj) {assert(obj);free(obj->date);free(obj);
}

测试：