【落羽的落羽 数据结构篇】栈和队列

一、栈

1. 概念

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

把栈想象成一个桶，数据只能从最上面投入，拿出时只能先拿出最上面的数据。比如：依次放入data1、data2、data3，再依次拿出，顺序则是data3、data2、data1

• 栈的插入数据操作叫做进栈/入栈/压栈，入数据在栈顶
• 栈的删除数据操作叫做出栈，出数据也在栈顶

栈既然也是一种线性表，说明它在逻辑上是线性的，在物理上不一定是线性的。它的物理结构是否线性，取决于栈的底层结构，是数组还是链表。实现链表的操作中使用哪种都可以，相对而言数组的结构更优，因为使用数组新增数据比较容易，而链表还涉及开辟新节点。今天我们就展示用数组实现栈。

2. 栈操作

2.1 定义栈结构

typedef struct Stack
{STDataType* arr;int top; //指向栈顶的位置int capacity; //栈容量
}ST;

2.2 栈的初始化

void STInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}

测试：

2.3 入栈

插入数据前先检查空间是否足够，将新入栈的元素置于下标为top的位置，然后top++

void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity) //如果空间不够，要增容{int newcapacity = ps->capacity == 0 ? 5 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}//空间足够ps->arr[ps->top++] = x;
}

测试：

2.4 出栈

void StackPop(ST* ps)
{assert(ps);assert(ps->top != 0); //保证栈不为空，否则无数据可删ps->top--;
}

测试：

2.5 取栈顶元素

STDataType StackTop(ST* ps)
{assert(ps);assert(ps->top != 0); //保证栈不为空，否则无数据可删return ps->arr[ps->top - 1];
}

测试：

3. 栈的使用实例

有些算法题要用到栈的特性，题目实例：有效的括号
https://leetcode.cn/problems/valid-parentheses/description/

思路：借助栈的特性，遍历字符串，遇到左括号入栈，遇到右括号就跟栈顶元素看是否是匹配的左括号，匹配就让左括号出栈，不匹配或栈为空则返回false，遍历完栈为空则返回true：

typedef struct Stack
{char arr[10001];int top; 
}ST;bool isValid(char* s) {ST stack;stack.top = 0;char* pcur = s;while(*pcur != '\0'){if(*pcur == '(' || *pcur == '[' || *pcur == '{'){stack.arr[stack.top++] = *pcur;}else{if(stack.top == 0){return false;}char top = stack.arr[stack.top-1];if(top == '(' && *pcur != ')'|| top == '[' && *pcur != ']'|| top == '{' && *pcur != '}'){return false;}stack.top--;}pcur++;}bool ret = stack.top == 0? true: false;return ret; 
}

二、队列

1. 概念

队列（queue）是另一种特殊线性表，它只允许在一端进行插入数据操作，在另一端进行删除数据操作，队列具有先进先出（First In First Out）的特性。

• 进行插入数据操作的一端称为队尾
• 进行删除数据操作的一端称为队头

把队列想象成一个单向通道，数据只能依次从一端进入，依次从另一端出去
队列也是线性表，说明队列的逻辑上是线性的。队列的底层结构要用数组还是链表呢？

不难想象：若用数组作为队列底层结构，把下标0作为队头，插入数据操作的时间复杂度为O(1)，删除数据操作的时间复杂度为O(n)，因为要把后面数据的下标遍历前挪；把下标0作为队尾，删除数据操作的时间复杂度为O(1)，插入数据操作的时间复杂度为O(n)，因为从队尾插入新数据要把后面数据的下标遍历后挪。
使用链表作为底层结构，只要保存队尾节点指针和队头节点指针，删除插入操作的时间复杂度都是O(1)。综上来看，使用链表实现队列更优。

2. 队列操作

2.1 定义队列结构

typedef int QDataType;typedef struct QueueNode //队列节点结构
{QDataType data;struct QueueNode* next;
}QueueNode;typedef struct Queue //队列结构
{QueueNode* phead; //队头QueueNode* ptail; //队尾//有时也需要来一个int size;记录有效元素个数
}Queue;

2.2 入队列

将一个新数据从队尾插入队列中

void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;if (pq->phead == NULL) //队列为空，则newnode是队头也是队尾{pq->phead = pq->ptail = newnode;}else //队列不为空，则newnode插入到队尾{pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}//pq->size++;
}

测试：

2.3 出队列

将队头数据从队列中删除

void QueuePop(Queue* pq)
{assert(pq->phead != NULL); //队列不能为空，否则无数据可出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--;
}

测试：

2.4 销毁队列

void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;
}

测试：

三、用队列实现栈

题目：用队列实现栈
https://leetcode.cn/problems/implement-stack-using-queues/

我们要用两个队列实现栈的特性先进后出

• push：入栈：往不为空的队列中插入数据
• pop：出栈：把不为空的队列中的前size-1个数据挪到另一个队列中，再将该队列中的最后一个数据出队列
• top：取栈顶元素（不出数据）：取不为空的队列中的队尾数据
• empty：判断栈是否为空：看两个队列是不是都为空

typedef struct QueueNode
{int data;struct QueueNode* next;
}QueueNode;//定义队列的结构
typedef struct Queue {QueueNode* phead;//队头QueueNode* ptail;//队尾int size;//记录有效数据个数
}Queue;//初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;
}//入队---队尾
void QueuePush(Queue* pq, int x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;//队列为空，newnode是队头也是队尾if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else {//队列非空，直接插入到队尾pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}pq->size++;
}//出队---队头
void QueuePop(Queue* pq)
{assert(pq->phead != NULL);//只有一个结点的情况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--;
}/以上是要用到的队列操作typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst = (MyStack*)malloc(sizeof(MyStack));QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;
}void myStackPush(MyStack* obj, int x) {if(obj->q1.phead != NULL){QueuePush(&obj->q1, x);}else{QueuePush(&obj->q2, x);}
}int myStackPop(MyStack* obj) {//找不为空的队列，将不为空队列的前size-1个数据挪到空队列Queue* empty = &obj->q1;Queue* noempty = &obj->q2;if(obj->q1.phead != NULL){empty = &obj->q2;noempty = &obj->q1;}while(noempty->size > 1){//把noempty的队头数据挪到空队列中QueuePush(empty, noempty->phead->data);QueuePop(noempty);}int top = noempty->phead->data;QueuePop(noempty);return top;
}int myStackTop(MyStack* obj) {if(obj->q1.phead != NULL){return obj->q1.ptail->data;}else{return obj->q2.ptail->data;}
}bool myStackEmpty(MyStack* obj) {if(obj->q1.phead == NULL && obj->q2.phead == NULL)return true;return false;
}void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);obj == NULL;
}

四、用栈实现队列

题目：用栈实现队列
https://leetcode.cn/problems/implement-queue-using-stacks/description/

我们要用两个栈实现队列的特性先进先出
思路：一个栈命名为pushST，一个栈命名为popST

• 入队：往pushST中插入数据
• 出队：若popST不为空则直接出数据，否则将pushST的数据先挪到popST中再从popST出数据
• 找队头数据：逻辑同出队操作，只不过只取数据不用pop

typedef struct Stack
{int* arr;int top;       //指向栈顶的位置int capacity;  //容量
}ST;//栈初始化
void STInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}//栈销毁
void STDestroy(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}//入栈----栈顶
void StackPush(ST* ps, int x)
{assert(ps);if (ps->top == ps->capacity){//空间不够---增容int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;int* tmp = (int*)realloc(ps->arr, newCapacity * sizeof(int));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}//出栈----栈顶
void StackPop(ST* ps)
{assert(ps->top != 0);--ps->top;
}//取栈顶数据
int StackTop(ST* ps)
{assert(ps->top != 0);return ps->arr[ps->top - 1];
}//以上是要用到的栈操作typedef struct {ST pushST;ST popST;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));STInit(&pq->pushST);STInit(&pq->popST);return pq;
}void myQueuePush(MyQueue* obj, int x) {//往pushST中插入数据StackPush(&obj->pushST, x);
}int myQueuePop(MyQueue* obj) {if(obj->popST.top == 0) //popST为空{//从pushST中挪数据while(obj->pushST.top != 0){StackPush(&obj->popST, StackTop(&obj->pushST));StackPop(&obj->pushST);}}//popST不为空int top = StackTop(&obj->popST);StackPop(&obj->popST);return top;
}int myQueuePeek(MyQueue* obj) {if(obj->popST.top == 0) //popST为空{//从pushST中挪数据while(obj->pushST.top != 0){StackPush(&obj->popST, StackTop(&obj->pushST));StackPop(&obj->pushST);}}//popST不为空int top = StackTop(&obj->popST);return top;
}bool myQueueEmpty(MyQueue* obj) {if(obj->pushST.top == 0 && obj->popST.top == 0)return true;return false;
}void myQueueFree(MyQueue* obj) {STDestroy(&obj->pushST);STDestroy(&obj->popST);free(obj);obj = NULL;
}

本篇完，感谢阅读