重生之“我打数据结构，真的假的？”--3.栈和队列

1.栈和队列的基本概念

1.1 栈

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

1.2 初始化及功能实现

#include"stack.h"typedef int datatype;
typedef struct stack
{datatype* a;int top;int capacity;
}ST;void InitST(ST* sl)
{assert(sl);                  //sl不为NULLsl->a = NULL;sl->top = 0;sl->capacity = 0;
}//初始化void STpush(ST* sl, int data)
{assert(sl);if (sl->top == sl->capacity){int newcapacity = sl->capacity == 0 ? 2 : sl->capacity * 2;datatype* tmp = (datatype*)realloc(sl->a, newcapacity * sizeof(datatype));sl->a = tmp;sl->capacity = newcapacity;}sl->a[sl->top] = data;sl->top++;
}//插入
void STpop(ST* sl)
{assert(sl);                //！！！！！！判断指针是否为空，《《《《判断的是栈是否存在》》》》》》          assert(!STempty(sl));      //！！！！！！！！！与上文不同，《《《《判断的是栈是否为空》》》》》》sl->top--;
}//删除datatype STtop(ST* sl)
{assert(sl);assert(!STempty(sl));return sl->a[sl->top-1];
}//取栈顶void STdestroy(ST* sl)
{assert(sl);free(sl->a);sl->a = NULL;sl->top = sl->capacity = 0;
}bool STempty(ST* sl)
{assert(sl);return sl->top == 0;
}

1.3 括号匹配问题

. - 力扣（LeetCode）

思路：

1.设立一个栈，依次从s中取出元素，如果为左括号类型 则入栈

2.否则取栈顶元素（如果栈为空则直接返回false）如果匹配

则删除栈顶元素，如果不匹配，返回false

3.s访问完后，如果栈为空，则返回true，否则返回false

bool isValid(char* s) {typedef struct stack
{char * a;int top;int capacity;
}ST;bool STempty(ST* sl)
{assert(sl);return sl->top == 0;
}
void InitST(ST* sl)
{assert(sl);                  //sl不为NULLsl->a = NULL;sl->top = 0;sl->capacity = 0;
}void STpush(ST* sl, char data)
{assert(sl);if (sl->top == sl->capacity){int newcapacity = sl->capacity == 0 ? 2 : sl->capacity * 2;char* tmp = (char*)realloc(sl->a, newcapacity * sizeof(char));sl->a = tmp;sl->capacity = newcapacity;}sl->a[sl->top] = data;sl->top++;
}
void STpop(ST* sl)
{assert(sl);                //！！！！！！判断指针是否为空，《《《《判断的是栈是否存在》》》》》》          assert(!STempty(sl));      //！！！！！！！！！与上文不同，《《《《判断的是栈是否为空》》》》》》sl->top--;
}char STtop(ST* sl)
{assert(sl);assert(!STempty(sl));return sl->a[sl->top-1];
}void STdestroy(ST* sl)
{assert(sl);free(sl->a);sl->a = NULL;sl->top = sl->capacity = 0;
}int i=0;char j;char k;ST L;ST R;InitST(&L);InitST(&R);while(s[i]!='\0'){if(s[i]=='('||s[i]=='['||s[i]=='{'){STpush(&L, s[i]);i++;}else{if(STempty(&L))return false;if((STtop(&L)=='('&&s[i]==')')||(STtop(&L)=='{'&&s[i]=='}')||(STtop(&L)=='['&&s[i]==']')){STpop(&L);i++;}elsereturn false;}}if(STempty(&L))return true;elsereturn false;}

2.队列 

2.1 概念

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素

2.2 初始化及功能实现

typedef int datatype;
typedef struct Queuenode
{datatype data;struct Queuenode * next;
}Qnode;typedef struct QT
{Qnode* head;Qnode* tail;int size;
}QT;void QueueInit(QT* sl)
{assert(sl);sl->head = NULL;sl->tail = NULL;sl->size = 0;
}bool Queueempty(QT* sl)
{assert(sl);return sl->head ==NULL;
}void Queuepush(QT* sl, int x)
{assert(sl);Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));newnode->next = NULL;newnode->data = x;if (Queueempty(sl)){sl->head = newnode;sl->tail = newnode;}else{sl->tail->next = newnode;sl->tail = newnode;}sl->size++;
}void Queuepop(QT* sl)
{assert(sl);assert(!Queueempty(sl));Qnode* next = sl->head->next;free(sl->head);sl->head = next;sl->size--;
}int Queuetop(QT* sl)
{assert(sl);assert(!Queueempty(sl));return sl->head->data;
}void Queuedestroy(QT* sl)
{assert(sl);while (!Queueempty(sl))Queuepop(sl);sl->head = sl->tail = NULL;sl->size = 0;
}

2.3 循环队列 

. - 力扣（LeetCode）

typedef struct Queuenode
{int data;struct Queuenode * next;
}Qnode;typedef struct {
Qnode* head;
Qnode* tail;
int size;
int flag;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* sl=NULL;sl=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));sl->head = NULL;sl->tail = NULL;sl->size = 0;sl->flag = k;return sl;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->head ==NULL;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(obj->size>=obj->flag)return false;Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));newnode->next = NULL;newnode->data = value;if(myCircularQueueIsEmpty(obj)){obj->head = newnode;obj->tail = newnode;obj->tail->next=obj->head;obj->head->next=obj->tail;}else{ obj->tail->next = newnode;obj->tail = newnode;if(obj->head->next==obj->head)obj->head->next=obj->tail;obj->tail->next=obj->head;}
obj->size++;
return true;}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;else{if(obj->head!=obj->tail){Qnode* next = obj->head->next;obj->tail->next=next;free(obj->head);obj->head = next;obj->size--;}else{free(obj->head);obj->head = obj->tail = NULL;obj->size = 0;}}return true;
}int myCircularQueueFront(MyCircularQueue* obj) {int i=0;if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->head->data;
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->tail->data;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->size==obj->flag;
}void myCircularQueueFree(MyCircularQueue* obj) {while (!myCircularQueueIsEmpty(obj)){Qnode* next = obj->head->next;obj->tail->next=next;if(obj->head!=obj->tail){ free(obj->head);obj->head = next;obj->size--;}else{obj->head = obj->tail = NULL;obj->size = 0;break;}}}

3.用栈实现队列 

 . - 力扣（LeetCode）

 思路：

1.可以设立两个栈 p，q

（1）入队：将p中元素依次入栈q，再将函数传递的数据入栈q

（2）出队：将q中元素依次入栈p，再取q栈顶元素

typedef struct stack
{int * a;int top;int capacity;
}ST;typedef struct {
ST* p;
ST* q;
} MyQueue;MyQueue* myQueueCreate() 
{MyQueue*sl=NULL;sl=(MyQueue*)malloc(sizeof(MyQueue));sl->q=(ST*)malloc(sizeof(ST));sl->p=(ST*)malloc(sizeof(ST));sl->q->a=NULL;sl->q->top=0;sl->q->capacity=0;sl->p->a=NULL;sl->p->top=0;sl->p->capacity=0;return sl;
}bool STempty(ST* sl)
{assert(sl);return sl->top == 0;
}int STtop(ST* sl)
{assert(sl);assert(!STempty(sl));int i;i=sl->a[sl->top-1];return i;
}void myQueuePush(MyQueue* obj, int x) {while(!STempty(obj->q)){
if (obj->p->top == obj->q->capacity)
{int newcapacity = obj->q->capacity == 0 ? 2 : obj->p->capacity * 2;int * tmp = (int*)realloc(obj->p->a, newcapacity * sizeof(int));obj->p->a = tmp;obj->p->capacity = newcapacity;
}
obj->p->a[obj->p->top] =STtop(obj->q) ;
obj->p->top++;
obj->q->top--;}if (obj->p->top == obj->p->capacity)
{int newcapacity = obj->p->capacity == 0 ? 2 : obj->p->capacity * 2;int * tmp = (int*)realloc(obj->p->a, newcapacity * sizeof(int));obj->p->a = tmp;obj->p->capacity = newcapacity;
}
obj->p->a[obj->p->top] = x;
obj->p->top++;
}int myQueuePop(MyQueue* obj) {while(!STempty(obj->p)){if (obj->q->top == obj->q->capacity)
{int newcapacity = obj->q->capacity == 0 ? 2 : obj->q->capacity * 2;int * tmp = (int*)realloc(obj->q->a, newcapacity * sizeof(int));obj->q->a = tmp;obj->q->capacity = newcapacity;
}
obj->q->a[obj->q->top] =STtop(obj->p) ;
obj->q->top++;
obj->p->top--;}int i=STtop(obj->q);obj->q->top--;return i;
}int myQueuePeek(MyQueue* obj) {while(!STempty(obj->p)){if (obj->q->top == obj->q->capacity)
{int newcapacity = obj->q->capacity == 0 ? 2 : obj->q->capacity * 2;int * tmp = (int*)realloc(obj->q->a, newcapacity * sizeof(int));obj->q->a = tmp;obj->q->capacity = newcapacity;
}
obj->q->a[obj->q->top] =STtop(obj->p) ;
obj->q->top++;
obj->p->top--;}int i=STtop(obj->q);return i;
}bool myQueueEmpty(MyQueue* obj) {if(STempty(obj->p)&&STempty(obj->q))return true;elsereturn false;
}void myQueueFree(MyQueue* obj) {free(obj->p);free(obj->q);
}