数据结构--栈和队列

栈的概念和结构

栈是一种常见的数据结构，它遵循后进先出LIFO（Last In First Out）的原则。进行数据插入和操作的一端称为栈顶，另一端称为栈底。

压栈：栈的插入操作被称为压栈/进栈/入栈，入数据在栈顶。
出栈：栈的删除操作。出数据也在栈顶；

栈的实现

栈可以用数组或者是链表来实现；这里将使用数组来实现，因为数组在插入删除时消耗代价较小；对于链表，由于Top放在尾，删除时还需要由头指针循环遍历找到尾结点前一个；

栈的数据结构

typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;

a为存储数据的数组，top表示栈顶，capacity表示当前数组的存储容量；

栈的初始化和销毁

void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}void STDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;}

assert（ps）验证的是传过来的地址，地址为NULL那就无法进行操作；
free完ps->a记得置空；

出栈和入栈

void STPush(ST* ps, STDataType x)
{assert(ps);//满扩容if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("Stack fail");exit(-1);}ps->a =tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;
}void STPop(ST* ps)
{assert(ps);assert(ps->top > 0);ps->top--;}

这里的Top是放在最后一位元素之后的；
当出栈时，不用管那个位置的内容和空间是否被删除，当下次入栈到这个位置，内容会被顶替；而如果用free掉这一块空间，会造成只释放部分空间的错误；

获取栈顶、大小，判空

STDataType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}int STSize(ST* ps)
{assert(ps);return ps->top;
}bool STEmpty(ST* ps)
{assert(ps);return ps->top==0;
}

对于数据结构来说，即使是简单的操作也要用函数进行封装；这样做的原因能够找出一些错误的操作，能够方便别人的操作；
例如你在主函数创建的栈为空，然后给到别人使用，别人不知道栈为空，别人没有用函数判断栈的大小，出来的栈的大小无法辨别是对的还是错误的；而创建函数就能够避免一些极端问题；

接下来我们简单的验证一下：

void Test1()
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);while (!STEmpty(&st)){printf("%d ", STTop(&st));STPop(&st);}printf("\n");STDestory(&st);
}int main()
{Test1();return 0;
}

队列的概念和结构

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

队列的实现

队列的实现可以用数组和链表来实现；这里将使用链表来实现；因为如果使用数组的结构，在数组头进行删除出数据，效率比较低；

队列的数据结构

typedef int QDataType;
typedef struct QueneNode
{struct QueneNode* next;QDataType data;
}QNode;typedef struct Quene
{QNode* head;QNode* tail;int size;
}Quene;

这里先用一个结构体将一个结点的类型进行封装；然后再用一个结构体进行队列的封装；因为这里我们将会使用队头和队尾，如果使用这两个进行传参，将会用到二级指针，比较麻烦，所以就使用一个结构体进行封装，用结构体进行传参，用到队头和队尾只需调用结构体的成员；

队列的初始化和销毁

void QueneInit(Quene* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}
void QueneDestory(Quene* pq)
{assert(pq);QNode* cur = pq ->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}

初始化将head和tail都置空；size统计多少个结点；
销毁用循环遍历逐渐将结点释放；最后将指针置空；

队列的插入

void QuenePush(Quene* pq, QDataType x)
{assert(pq);//扩容QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;//第一个插入if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}

首先是每插入一次就扩容一个结点；接着是判断是否为第一个结点的插入，如果是需要将head和tail都等于新节点；最后将size加加；

队列的删除

void QuenePop(Quene* pq)
{assert(pq);//判断是否没有数据assert(!QueneEmpty(pq));QNode* next = pq->head->next;//只有一个数据if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = next;}else{free(pq->head);pq->head = next;}pq->size--;}

我们需要判断有没有结点可以删除；然后记住头结点的下一个结点，删除头结点后将头结点指针等于下一个结点；如果只有一个结点可以删除，那么还要将tail置空；

获取队头和队尾的数据

QDataType QueneFront(Quene* pq)
{assert(pq);assert(!QueneEmpty(pq));return pq->head->data;
}
QDataType QueneBack(Quene* pq)
{assert(pq);assert(!QueneEmpty(pq));return pq->tail->data;
}

获取队列长度和判空

int QueneSize(Quene* pq)
{assert(pq);return pq->size;
}
bool QueneEmpty(Quene* pq)
{assert(pq);return pq->head == NULL;
}

最后做一下简单的验证

void Test1()
{Quene q;QueneInit(&q);QuenePush(&q, 1);QuenePush(&q, 2);QuenePush(&q, 3);QuenePop(&q);while (QueneSize(&q)>0){printf("%d ", QueneBack(&q));QuenePop(&q);}QueneDestory(&q);}int main()
{Test1();return 0;
}

栈和队列的一些题目

1.有效的括号

思路：这道题可以采用栈这种结构来解决问题，满足后进先出的原理；
我们可以这么做，分为左括号和右括号；遇到左括号就放入栈中，一旦遇到右括号，我们可以将栈顶取出，进行判断；这是我们的大体思路；
这道题我们还需要考虑一些极端情况：
第一种：字符串中只有右括号或者说一开始就是右括号，那么这种就相当于栈为空；当遇到右括号时，需要先进行判断；
第二种：字符串只有左括号，那么表明栈中的元素没有进行匹配出栈，栈不为空；
所以把特殊情况弄好后，就可以进行操作了，我们可以把我们写的栈结构复制到程序中，然后创建一个栈来进行操作；最后记得释放空间，避免内存泄漏；

代码：

#define  _CRT_SECURE_NO_WARNINGS 1typedef char STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}void STDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;}
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("Stack fail");exit(-1);}ps->a =tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;
}void STPop(ST* ps)
{assert(ps);assert(ps->top > 0);ps->top--;}STDataType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}int STSize(ST* ps)
{assert(ps);return ps->top;
}bool STEmpty(ST* ps)
{assert(ps);return ps->top==0;
}bool isValid(char * s){ST st;//栈初始化STInit(&st);while(*s){//左括号就入栈if(*s=='('||*s=='['||*s=='{'){STPush(&st,*s);}//右括号就出栈，判断else{栈空，表明没有左括号if(STEmpty(&st)){STDestory(&st);return false;}char val=STTop(&st);STPop(&st);//不符合if((*s==')'&&val!='(')||(*s==']'&&val!='[')||(*s=='}'&&val!='{')){return false;}}s++;}if(!STEmpty(&st)){return false;}STDestory(&st);return true;
}

2.用队列实现栈

思路：我们可以在纸上模拟一下入栈和出栈的操作；


由于入栈的时候和队列的性质一样，都在尾插入，所以不需要执行什么操作；出栈时，总需要进行转移，才能删除最后一个元素；那么可以先判断那个队列空与不为空，然后将不为空的进行转移到空的队列；那么就可以完成出栈；同时，由于这样的操作，入栈时如果有一个队列不为空需要将元素插入不为空的后面，方便出栈的操作；

代码：

#include<assert.h>
#include<stdbool.h>typedef int QDataType;
typedef struct QueneNode
{struct QueneNode* next;QDataType data;
}QNode;typedef struct Quene
{QNode* head;QNode* tail;int size;
}Quene;void QueneInit(Quene* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}
void QueneDestory(Quene* pq)
{assert(pq);QNode* cur = pq ->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}
void QuenePush(Quene* pq, QDataType x)
{assert(pq);//扩容QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;//第一个插入if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}
bool QueneEmpty(Quene* pq)
{assert(pq);return pq->head==NULL;
}
int QueneSize(Quene* pq)
{assert(pq);return pq->size;
}
void QuenePop(Quene* pq)
{assert(pq);//判断是否没有数据assert(!QueneEmpty(pq));//只有一个数据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--;
}
QDataType QueneFront(Quene* pq)
{assert(pq);assert(!QueneEmpty(pq));return pq->head->data;
}
QDataType QueneBack(Quene* pq)
{assert(pq);assert(!QueneEmpty(pq));return pq->tail->data;
}typedef struct {Quene q1;Quene q2;
} MyStack;
//创建一个自己的栈//用一个结构体进行包装
MyStack* myStackCreate() {MyStack* obj=malloc(sizeof(MyStack));QueneInit(&obj->q1);QueneInit(&obj->q2);return obj;
}//插入判断哪个队列不为空
void myStackPush(MyStack* obj, int x) {if(!QueneEmpty(&obj->q2)){QuenePush(&obj->q2,x);}else{QuenePush(&obj->q1,x);}
}//将队列分为空队列和不空队列
int myStackPop(MyStack* obj) {Quene* empty=&obj->q1;Quene* nonempty=&obj->q2;if(!QueneEmpty(&obj->q1)){empty=&obj->q2;nonempty=&obj->q1;}//数据转移while(QueneSize(nonempty)>1){QuenePush(empty,QueneFront(nonempty));QuenePop(nonempty);}//删除数据，并返回int Top=QueneFront(nonempty);QuenePop(nonempty);return Top;
}int myStackTop(MyStack* obj) {if(!QueneEmpty(&obj->q2)){return QueneBack(&obj->q2);}else{return QueneBack(&obj->q1);}
}bool myStackEmpty(MyStack* obj) {return QueneEmpty(&obj->q1)&&QueneEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {QueneDestory(&obj->q1);QueneDestory(&obj->q2);free(obj);
}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj = myStackCreate();* myStackPush(obj, x);* int param_2 = myStackPop(obj);* int param_3 = myStackTop(obj);* bool param_4 = myStackEmpty(obj);* myStackFree(obj);
*/

3.用栈实现队列

思路：一样的我们先在纸上模拟



如果再继续删除，那么可以删除到栈2为空，然后就将栈1的内容全部转移到栈2；如果栈2没空，再插入栈1会发现没有任何影响；
所以我们总结得出：将栈1表示为插入的栈，栈2表示为删除的栈，如果要删除栈2为空就将栈1的内容转移到栈2；

代码：

typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}void STDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;}
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("Stack fail");exit(-1);}ps->a =tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;
}void STPop(ST* ps)
{assert(ps);assert(ps->top > 0);ps->top--;}STDataType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}int STSize(ST* ps)
{assert(ps);return ps->top;
}bool STEmpty(ST* ps)
{assert(ps);return ps->top==0;
}//栈分为插入栈和输出栈
typedef struct {ST instack;ST outstack;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj=malloc(sizeof(MyQueue));STInit(&obj->instack);STInit(&obj->outstack);return obj;
}void myQueuePush(MyQueue* obj, int x) {STPush(&obj->instack,x);
}int myQueuePop(MyQueue* obj) {//先判断输出栈是否为空if(STEmpty(&obj->outstack)){while(STSize(&obj->instack)){STPush(&obj->outstack,STTop(&obj->instack));STPop(&obj->instack);}}int head=STTop(&obj->outstack);STPop(&obj->outstack);return head;
}int myQueuePeek(MyQueue* obj) {if(STEmpty(&obj->outstack)){while(STSize(&obj->instack)){STPush(&obj->outstack,STTop(&obj->instack));STPop(&obj->instack);}}return STTop(&obj->outstack);
}bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->instack)&&STEmpty(&obj->outstack);
}void myQueueFree(MyQueue* obj) {STDestory(&obj->instack);STDestory(&obj->outstack);free(obj);
}/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj = myQueueCreate();* myQueuePush(obj, x);* int param_2 = myQueuePop(obj);* int param_3 = myQueuePeek(obj);* bool param_4 = myQueueEmpty(obj);* myQueueFree(obj);
*/

4.设计循环队列

我们先根据题意确定我们将选择数组来存储（固定长度）；然后考虑怎么让这个数组能够循环着走？我们可以设置两个指针来判断（由于是数组，可以利用下标来进行代表指针），分别为头和尾；假设队列长度为k，一开始，头和尾下标都为0，表示这个队列为空；

那么当插入一个元素后尾向后走一步


删除一个元素头向后走一步，

当数组填满后，会发现头尾又重叠在一起，与一开始队列为空情况是一样的，这样就无法判断空与满了；

所以我们可以再增加一个多出来的空间

当尾走到最后一个多出来的空间时就表示满；
循环的尾走到最后时我们用取模来进行返回到下标为0的位置；这样子就能完成我们循环的目的。

代码：

typedef struct {int* a;int head;int rear;int k;} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj=malloc(sizeof(MyCircularQueue));obj->a=malloc(sizeof(int)*(k+1));obj->head=obj->rear=0;obj->k=k;return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->head==obj->rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {//当rear超过k+1时，归0return (obj->rear+1)%(obj->k+1)==obj->head;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}obj->a[obj->rear]=value;obj->rear++;//限制在0-kobj->rear%=(obj->k+1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}obj->head++;//限制在0-kobj->head%=(obj->k+1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->a[obj->head];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}//考虑rear-1等于-1的情况return obj->a[(obj->rear+obj->k)%(obj->k+1)];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/

这里需要注意的就是取模的问题，需要记住尾和头是不断增加的，是由于取模k+1才限制在0-k的下标中；
第一个就是在删除和插入数据的时候，当头尾超出范围时，需要进行取模k+1的操作，返回到第一个元素；
第二个是判断满时，尾+1相当于返回到头，当尾刚好处于最后下标时，需要进行取模；
最后一个是取尾的问题，当尾刚好处于第一个下标时，由于尾需要进行-1的操作才能得到尾元素，所欲在第一个下标-1会导致下标变为-1，所以可以多加一轮K+1进行取模的操作避免这个问题；