数据结构之栈和队列(超详解)_数据与结构队列ppt

文章目录

• 概念与结构
• • 栈
  • 队列
• 代码实现
• • 栈
  • • 栈是否为空，取栈顶数据、栈的有效个数
  • 队列
  • • 入队列
    • 出队列
    • 队列判空，取队头、队尾数据，队列的有效个数
• 算法题解
• • 有效的括号
  • 用队列实现栈
  • 用栈实现队列
  • • 复用
  • 设计循环队列
  • • 数组结构实现循环队列
    • • 构造、销毁循环队列
      • 判断空和满
      • 入、出队列
      • 取队头、队尾元素

概念与结构

栈

栈：⼀种特殊的线性表，只允许在固定的⼀端进行插入和删除元素操作。数据插入和删除操作
的一端称为栈顶，另⼀端称为栈底。栈中的元素遵守后进先出(或先进后出)的原则。

压栈(进栈/压栈/⼊栈)：插入数据在栈顶。
出栈：在栈顶出数据。

栈的实现可由数组或链表实现，那么哪种是优解呢？
底层用数组：在进栈时只需要在栈顶(尾部)插入数据，不用进行遍历；
底层用链表：在进栈时链表遍历到尾结点再进行插入数据，需要O(n)的时间复杂度，会有一定的消耗。
因此数组的结构实现更优⼀些。

队列

概念：只允许在⼀端插⼊数据，在另⼀端删除数据的特殊线性表，队列具有先进先出(后进后出)的原则。
入队列：在队尾插入数据。
出队列：在队头删除数据。

同样，队列底层也可由数组或链表实现，哪种是优解呢？
底层用数组：删除数据时需要将后面的数据往前挪，有一定的消耗。
底层用链表：出队列时只需要让指向第一个有效结点的指针指向第二个有效结点，不需要遍历；
因此链表的结构实现更优⼀些。

代码实现

栈

栈的底层是数组，和前面在实现顺序表的底层结构是一样的。

typedef int STDataType;typedef struct Stack{STDataType* arr;int top;//栈顶int capacity;}ST;

由于栈的初始化、销毁、入栈(顺序表尾插)、出栈(顺序表尾删)功能与顺序表功能实现是一样的，就不过多赘述。

//栈的初始化void STInit(ST* st){assert(st);st->arr = NULL;st->top = st->capacity = 0;}//栈的销毁void STDestroy(ST* st){assert(st);if (st->arr){free(st->arr);}st->arr = NULL;st->capacity = st->top = 0;}//入栈-->栈顶void STPush(ST* st, STDataType x){assert(st);//检测空间是否不足if (st->capacity == st->top){int NewCapacity = st->capacity == 0 ? 4 : 2 * st->capacity;STDataType* tmp = (STDataType*)realloc(st->arr, NewCapacity * sizeof(STDataType));if (tmp == NULL){perror(\"realloc fail!\");exit(1);}//malloc成功st->arr = tmp;st->capacity = NewCapacity;}st->arr[st->top] = x;st->top++;}//出栈帧-->栈顶void STPop(ST* st){assert(st);assert(!STEmpty(st));st->top--;}

栈是否为空，取栈顶数据、栈的有效个数

栈是否为空，即栈里面是否存在数据，即top是否为0(为0则返回真)。

bool STEmpty(ST* st){assert(st);return st->top == 0;}

取栈顶数据首先得保证栈不为空，其次取top-1的数据即可，栈的有效个数即top。

//取栈顶元素STDataType STTop(ST* st){assert(!STEmpty(st));return st->arr[st->top - 1];}//获取栈的有效个数int STSize(ST* st){assert(st);return st->top;}

队列

队列的底层是链表，和前面在实现单链表的底层结构是一样的。
但队列额外定义了指向第一个有效结点的phead指针、指向最后一个有效结点的ptail指针，目的是减少入队列的消耗（不用遍历链表）。

这里多定义的size变量是为了记录队列的有效个数。

typedef int QDataType;//定义队列结点的结构typedef struct QueueNode{QDataType data;struct QueueNode* next;}QueueNode;//定义队列的结构typedef struct Queue{QueueNode* phead;//队头QueueNode* ptail;//队尾int size;}Queue;

入队列

需要往队尾插入数据，必然涉及申请新节点 --> 在单链表中实现过。

1. 链表为空，phead和ptail指向申请的新结点；
2. 链表不为空，ptail指向新结点并成为新结点，并让size++。
   

//往队尾插入数据void QueuePush(Queue* pq, QDataType x){assert(pq);//malloc一个新节点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror(\"malloc: fail\");exit(1);}//malloc成功newnode->data = x;newnode->next = NULL;//判断链表是否为空if (pq->phead == NULL){//链表为空pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}pq->size++;}

出队列

1. 当只存在一个结点时，释放后phead和ptail指向为NULL；
2. 释放尾结点，让ptail指向上一个结点。

//队头删除数据void QueuePop(Queue* pq){assert(pq);assert(!QueueEmpty(pq));//只有一个节点if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else {QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;}

队列判空，取队头、队尾数据，队列的有效个数

//队列判空bool QueueEmpty(Queue* pq){assert(pq);return pq->phead == NULL;}//取队头数据QDataType QueueFront(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;}//取队尾数据QDataType QueueBack(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;}//队列有效元素个数int QueueSize(Queue* pq){assert(pq);return pq->size;}

算法题解

掌握了栈和队列这两种数据结构后，重点在于算法题上的解答，下面通过四种题型领略栈和队列的魅力。

有效的括号

题型 --> 有效的括号

根据题目需求判断字符串是否有效，但还存在一些特殊情况如上图所示。那这题思路该从哪里入手呢？用栈的方法实现。

1. 将s从头开始遍历直到结束，若遍历过程遇到 ‘(’ ‘{’ ‘[’ 则入栈st；
2. 若遇到 ‘)’ ‘}’ ‘]’ 时则取栈顶比较(前提是栈不为空);
3. 遍历结束后，需判断栈是否为空，因为若是有效的字符串则栈应为空(如上图特殊处理1)。
   

bool isValid(char* s) { ST st; STInit(&st); char* pi=s; while(*pi!=\'\\0\') { if(*pi==\'(\'||*pi==\'{\'||*pi==\'[\') { //入栈 STPush(&st,*pi); }else { //取栈顶，判断 if(STEmpty(&st)) { return false; } //不为空 char top=STTop(&st); if((top==\'(\'&&*pi!=\')\')||  (top==\'{\'&&*pi!=\'}\')||  (top==\'[\'&&*pi!=\']\')) { return false; } STPop(&st); } pi++; } bool ret=STEmpty(&st)?true:false; STDestroy(&st); return ret;}

用队列实现栈

题型 --> 用队列实现栈

代码实现

typedef struct { Queue q1; Queue q2;} MyStack;//初始化MyStack* myStackCreate() { MyStack* ret=(MyStack*)malloc(sizeof(MyStack)); QueueInit(&ret->q1); QueueInit(&ret->q2); return ret;}//往不为空的队列插入数据void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1,x); }else{ QueuePush(&obj->q2,x); }}int myStackPop(MyStack* obj) { //找空队列和非空队列 Queue* emp=&obj->q1; Queue* Unemp=&obj->q2; if(QueueEmpty(&obj->q2)) { emp=&obj->q2; Unemp=&obj->q1; } while(QueueSize(Unemp)>1) { QueuePush(emp,QueueFront(Unemp)); QueuePop(Unemp); } int top=QueueFront(Unemp); QueuePop(Unemp); return top;}//把不为空队列的队尾元素返回int myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); }else{ return QueueBack(&obj->q2); }}bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);}void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj); obj=NULL;}

用栈实现队列

题型 --> 用栈实现队列

将STPush栈里的数据全部导入到STPop栈里，并删除STPop栈顶元素。

代码实现

typedef struct { ST pushST; ST popST;} MyQueue;MyQueue* myQueueCreate() { MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue)); STInit(&obj->pushST); STInit(&obj->popST); return obj;}void myQueuePush(MyQueue* obj, int x) { STPush(&obj->pushST,x);}int myQueuePop(MyQueue* obj) { if(STEmpty(&obj->popST)) { //把pushST中的数据导到popST中来 while(!STEmpty(&obj->pushST)) { STPush(&obj->popST,STTop(&obj->pushST)); STPop(&obj->pushST); } } int top=STTop(&obj->popST); STPop(&obj->popST); return top;}int myQueuePeek(MyQueue* obj) { if(STEmpty(&obj->popST)) { //把pushST中的数据导到popST中来 while(!STEmpty(&obj->pushST)) { STPush(&obj->popST,STTop(&obj->pushST)); STPop(&obj->pushST); } } int top=STTop(&obj->popST); return top;}bool myQueueEmpty(MyQueue* obj) { return STEmpty(&obj->pushST)&&STEmpty(&obj->popST);}void myQueueFree(MyQueue* obj) { STDestroy(&obj->pushST); STDestroy(&obj->popST); free(obj); obj=NULL;}

复用

由于出队列和取队尾数据的代码相似度极高，因此我们可以用复用的方法使代码更简洁，增强代码可维护性。

设计循环队列

题型 --> 设计循环队列

1.若底层用链表的结构来实现，则会出现如下情况1和2出现矛盾，此时又该怎样判断循环队列是否为空呢？
因此，底层用链表的结构来实现很难行得通。

数组结构实现循环队列

如果按题目需要多少空间就开多少空间，此时会循环队列空和满的情况下，front和rear的下标都指向同一下标，那该如何判断循环队列是空还是满呢？

解决方案：给数组多开一块空间

构造、销毁循环队列

typedef struct { int* arr; int front; int rear; int capacity;} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* pq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); if(pq==NULL) { exit(1); } if(pq->arr==NULL) { exit(1); } pq->arr=(int*)malloc(sizeof(int)*(k+1)); pq->front=pq->rear=0; pq->capacity=k; return pq;}

判断空和满

bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front==obj->rear;}bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->rear+1)%(obj->capacity+1)==obj->front;}

入、出队列

入队列和出队列的时候会出现特例情况，即front和rear是否会越界。

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) { return false; } obj->arr[obj->rear++]=value; obj->rear%=obj->capacity+1; return true;}bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return false; } obj->front++; obj->front%=obj->capacity+1; return true;}

取队头、队尾元素

取队尾元素时，一般返回rear-1下标位置的元素即可。但此题是一个循环队列，因此存在特殊情况需要处理。

int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->arr[obj->rear-1];}

特例情况：若rear–则为-1，取不到队尾元素。

int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->arr[obj->front];}int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } int prev=obj->rear-1; if(obj->rear==0) { prev=obj->capacity; } return obj->arr[prev];}