栈和队列
1. 栈
栈：⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作 的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。 压栈：栈的插⼊操作叫做进栈/压栈/⼊栈，⼊数据在栈顶。 出栈：栈的删除操作叫做出栈。出数据也在栈顶。
底层结构选型 栈的实现⼀般可以使⽤数组或者链表实现，相对⽽⾔数组的结构实现更优⼀些。因为数组在尾上插⼊ 数据的代价⽐较⼩。
栈的实现
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int STDataType;typedef struct Stack
{STDataType* PST;int top;int capasity;
}Stack;typedef struct MyQueue {Stack pushst;Stack popst;
} MyQueue;
//栈的实现
void StackInit(Stack* ST);
void StackDestroy(Stack* ST);
void StackPush(Stack* ST, STDataType x);
void StackPop(Stack* ST);
void StackPrint(Stack* ST);
int StackIsEmpty(Stack* ST);
STDataType StackTop(Stack* ST);#include"Stack.h"
//栈的实现
void StackInit(Stack* ST)
{assert(ST);ST->capasity = 4;ST->top = 0;ST->PST =(STDataType*)malloc(sizeof(STDataType)*4);
}
int StackIsEmpty(Stack* ST)
{assert(ST);if (ST->top == 0) {return 1;}else {return 0;}
}
void StackDestroy(Stack* ST)
{assert(ST);free(ST->PST);ST->capasity = 0;ST->top = 0;ST->PST = NULL;
}
void StackPush(Stack* ST, STDataType x)
{assert(ST);if (ST->top == ST->capasity) {STDataType* temp = (STDataType*)realloc(ST->PST, sizeof(STDataType) * 2 * ST->capasity);if (temp == NULL) {printf("realloc failed\n");exit(1);}ST->PST = temp;ST->capasity = 2 * ST->capasity;}ST->PST[ST->top] = x;ST->top++;
}
void StackPop(Stack* ST)
{assert(ST);if (ST->top) {ST->top--;}
}
void StackPrint(Stack* ST)
{assert(ST);for (int i = 0; i < ST->top; i++){printf("%d ", ST->PST[i]);}printf("top:%d capacity:%d", ST->top,ST->capasity);printf("\n");
}STDataType StackTop(Stack* ST)
{assert(ST);assert(ST->top);return ST->PST[ST->top-1];
} 最小栈(栈实战应用)
包含min函数的栈牛客题霸牛客网
//解题思路：1 再搞一个栈2来存储当前栈1中最小的元素，栈2的栈顶元素就是当前栈1中的最小元素，当栈1最小元素出栈时，栈2也要跟着出栈
2 不要额外栈，把栈存储的元素类型改为pair类型<栈元素，当前元素到栈底的最小元素>
class Solution {
public:void push(int value) {if(s1.empty()){s1.push({value,value});}else {if(value<=s1.top().second){s1.push({value,value});}else {s1.push({value,s1.top().second});}}}void pop() {s1.pop();}int top() {return s1.top().first;}int min() {return s1.top().second;}stack<pair<int,int>> s1;
};2. 队列
概念：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先 出FIFO(First In First Out) ⼊队列：进⾏插⼊操作的⼀端称为队尾 出队列：进⾏删除操作的⼀端称为队头
队列的实现
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int QNDataType;
typedef struct QueueNode {struct QueueNode* next;QNDataType data;}QN;typedef struct Queue {QN* head;QN* tail;
}Queue;void QueueInit(Queue* Qe);
void QueuePrint(Queue* Qe);
void QueuePush(Queue* Qe, QNDataType x);//队尾入
void QueuePop(Queue* Qe);//队头出
QNDataType QueueFront(Queue* Qe);//取队头数据
QNDataType QueueBack(Queue* Qe);//取队尾数据
int QueueSize(Queue* Qe);//取队列大小
int QueueIsEmpty(Queue* Qe);//判断队列是否为空
void QueueDestroy(Queue* Qe);#include"Queue.h"void QueueInit(Queue* Qe)
{Qe->head = NULL;Qe->tail = NULL;
}
void QueueDestroy(Queue* Qe)
{assert(Qe);QN* cur = Qe->head;while (cur != NULL) {QN* next = cur->next;free(cur);cur = next;}Qe->tail = Qe->head = NULL;}
int QueueIsEmpty(Queue* Qe)//判断队列是否为空
{assert(Qe);return Qe->head == NULL;}
void QueuePrint(Queue* Qe)
{assert(Qe);QN* cur = Qe->head;while (cur!= NULL) {printf("%d ", cur->data);cur = cur->next;}printf("\n");
}
void QueuePush(Queue* Qe, QNDataType x)
{assert(Qe);QN* temp = (QN*)malloc(sizeof(QN));if (temp == NULL) {printf("malloc failed\n");exit(-1); }temp->data = x;temp->next = NULL;if (Qe->tail == NULL) {//第一次入数据Qe->head = temp;Qe->tail = temp;}else {//第二次Qe->tail->next = temp;Qe->tail = temp;}
}
void QueuePop(Queue* Qe)
{assert(Qe);assert(Qe->head);if (Qe->head->next == NULL) {//只有一个节点的时候出数据free(Qe->head);Qe->head = Qe->tail = NULL;}else {//多节点出数据QN* next = Qe->head->next;free(Qe->head);Qe->head = next;}
}QNDataType QueueFront(Queue* Qe)//取队头数据
{assert(Qe);assert(Qe->head);//判断队头为空return Qe->head->data;
}QNDataType QueueBack(Queue* Qe)//取队尾数据
{assert(Qe);assert(Qe->head);//判断队头为空return Qe->tail->data;
}int QueueSize(Queue* Qe)//取队列大小
{assert(Qe);QN* cur = Qe->head;int size = 0;while (cur!=NULL) {size++;cur = cur->next;}return size;}
