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不为NULL
sl->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 括号匹配问题
思路：
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不为NULL
sl->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++;
}
else
return false;
}
}
if(STempty(&L))
return true;
else
return 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 循环队列
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;
else
return obj->head->data;
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
else
return 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.用栈实现队列
思路：
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;
else
return false;
}
void myQueueFree(MyQueue* obj) {
free(obj->p);
free(obj->q);
}