C++数据结构深入探究栈与队列
时间：2022-11-14 09:31:49|栏目：C代码|点击： 次
1. 栈
1.1 栈的概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
1.2 栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小。
Stack.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int bool;
#define TRUE 1;
#define FALSE 0;
typedef int STDataType;
struct Stack
{
STDataType* a;
int top; //栈顶
int capacity; //容量，方便增容
};
//typedef struct Stack ST;
typedef struct Stack Stack;
//初始化
void StackInit(Stack* pst);
//销毁
void StackDestroy(Stack* pst);
//入栈
void StackPush(Stack* pst, STDataType x);
//出栈
void StackPop(Stack* pst);
//返回栈顶数据
STDataType StackTop(Stack* pst);
//判断栈是否为空,空返回1非空返回0
//int StackEmpty(Stack* pst);
bool StackEmpty(Stack* pst);
//栈中数据个数
int StackSize(Stack* pst);
Stack.c
#include "Stack.h"
//初始化
void StackInit(Stack* pst)
{
assert(pst);
/*pst->a = NULL;
pst->top = 0;
pst->capacity = 0;*/
//开始就申请空间，好处在于空间不够时直接容量*2即可(如果刚开始是0就要单独处理)
pst->a = malloc(sizeof(STDataType) * 4);
pst->top = 0;
pst->capacity = 4;
}
//销毁
void StackDestroy(Stack* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->capacity = pst->top = 0;
}
//入栈
void StackPush(Stack* pst, STDataType x)
{
assert(pst);
//从top为0的位置开始放
//如果满了就增容
if (pst->top == pst->capacity)
{
STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * pst->capacity * 2);
if (tmp == NULL)
{
//如果开辟空间失败
printf("realloc fail\n");
exit(-1);//结束整个程序(-1表示异常退出)
}
pst->a = tmp;
pst->capacity *= 2;
}
//入数据
pst->a[pst->top] = x;
pst->top++;
}
//出栈
void StackPop(Stack* pst)
{
assert(pst);//不能是空指针
assert(!StackEmpty(pst)); //栈内还有元素才能出战
pst->top--;
}
//返回栈顶数据
STDataType StackTop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));
return pst->a[pst->top - 1];
}
//判断栈是否为空,空返回1非空返回0
bool StackEmpty(Stack* pst)
{
assert(pst);
return pst->top == 0;
}
int StackSize(Stack* pst)
{
assert(pst);
return pst->top;
}
test.c
#include "Stack.h"
//对栈操作的测试
void TestStack()
{
Stack st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
//栈遍历数据
while (!StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
//4 3 2 1
StackDestroy(&st);
}
int main()
{
TestStack();
return 0;
}
2. 队列
2.1 队列的概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
2.2 队列的实现
Queue.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int QDataType;
//队列中的一个结点
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QueueNode;
//队列(由于需要两个指针，所以用结构体定义)
typedef struct Queue
{
QueueNode* head; //头指针
QueueNode* tail; //尾指针
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//计算队列元素个数
int QueueSize(Queue* pq);
Queue.c
#include "Queue.h"
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
//不带哨兵位
pq->head = pq->tail = NULL;
}
//销毁
void QueueDestroy(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while (cur)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
//判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL; //等于空就为真, 不为空就是假
}
//入队
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)//申请空间失败
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
//出队
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));//空队列也不能调用出队操作
if (pq->head->next == NULL)//只有一个结点的情况(如果不单独考虑，那当只有一个结点时，tail会仍然指向曾经的队尾)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
//取队头数据
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
//取队尾数据
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
int QueueSize(Queue* pq)
{
int size = 0;
QueueNode* cur = pq->head;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
test.c
#include "Queue.h"
//对队列操作的测试
void TestQueue()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
printf("%d\n", QueueSize(&q)); //4
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
//1 2 3 4
QueueDestroy(&q);
}
int main()
{
TestQueue();
return 0;
}
3. 栈和队列面试题
3.1 括号匹配问题
bool isValid(char * s)
{
Stack st;
StackInit(&st);
while(*s)
{
//左括号入栈，右括号找最近的左括号匹配
if(*s == '[' || *s == '(' || *s == '{')
{
StackPush(&st, *s);
s++;
}
else
{
if(StackEmpty(&st))//只有后括号的情况
{
StackDestroy(&st);
return false;
}
char top = StackTop(&st);
//不匹配的情况
if ( (top == '[' && *s != ']')
|| (top == '(' && *s != ')')
|| (top == '{' && *s != '}') )
{
StackDestroy(&st);
return false;
}
else //匹配的情况
{
StackPop(&st);
s++;
}
}
}
//如果最后栈内为空才说明是匹配的(防止最后栈内还剩下前括号的情况)
bool ret = StackEmpty(&st);
StackDestroy(&st);
return ret;
//特别注意:在return之前需要先把栈销毁掉
}
3.2用队列实现栈
//思路:
//入栈: 向不为空的队列入数据,始终保持另一个队列为空
//出栈: 前size-1个数据导入空队列，删除最后一个
typedef struct
{
Queue q1;
Queue q2;
} MyStack;
//*为什么下面代码传参都要传&obj->q1/q2？
//因为应该传入函数中的是队列的指针
MyStack* myStackCreate()
{
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&pst->q1);
QueueInit(&pst->q2);
return pst;
}
void myStackPush(MyStack* obj, int x)
{
//往不为空的队列里入数据
if(!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1, x);
}
else
{
QueuePush(&obj->q2, x);
}
}
int myStackPop(MyStack* obj)
{
//假设q1为空q2不为空
Queue* pEmpty = &obj->q1;
Queue* pNonEmpty = &obj->q2;
if(!QueueEmpty(&obj->q1))
{
pEmpty = &obj->q2;
pNonEmpty = &obj->q1;
}
//取出前size-1个插入空队列
while(QueueSize(pNonEmpty) > 1)
{
QueuePush(pEmpty, QueueFront(pNonEmpty));
QueuePop(pNonEmpty);
}
//"干掉"最后一个
int front = QueueBack(pNonEmpty);
QueuePop(pNonEmpty);
return front;
}
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)
{
//先释放两个队列，再释放malloc出来的结构体
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}
3.3 用栈实现队列
typedef struct
{
Stack pushST;
Stack popST;
} MyQueue;
MyQueue* myQueueCreate()
{
MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
StackInit(&q->pushST);
StackInit(&q->popST);
return q;
}
void myQueuePush(MyQueue* obj, int x)
{
//不管栈内有没有数据，只要是入队操作就向Push栈入数据即可
StackPush(&obj->pushST, x);
}
//获取队头数据
int myQueuePeek(MyQueue* obj)
{
//如果pop栈为空,先把push栈数据导入pop栈
if(StackEmpty(&obj->popST))
{
while(!StackEmpty(&obj->pushST))
{
StackPush(&obj->popST, StackTop(&obj->pushST));
StackPop(&obj->pushST);
}
}
return StackTop(&obj->popST);
}
//出队
int myQueuePop(MyQueue* obj)
{
//如果pop栈为空,先把push栈数据导入pop栈
/*if(StackEmpty(&obj->popST))
{
while(!StackEmpty(&obj->pushST))
{
StackPush(&obj->popST, StackTop(&obj->pushST));
StackPop(&obj->pushST);
}
}
*/
//复用
int top = myQueuePeek(obj);//易错点:不能写&obj->popST,因为该传入队列的指针
StackPop(&obj->popST);
return top;
}
bool myQueueEmpty(MyQueue* obj)
{
//push栈和pop栈同时为空,队列才为空
return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}
void myQueueFree(MyQueue* obj)
{
StackDestroy(&obj->pushST);
StackDestroy(&obj->popST);
free(obj);
}
3.4 设计循环队列
题目描述：
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
//循环队列是逻辑上的循环(数组、链表都可以实现,本题使用数组)
//永远空出一个位置不存储数据(目的是区分空和满)
//当front = tail说明循环队列空
//当tail+1 = front说明循环队列满
typedef struct
{
int* a; //数组
int k; //循环队列最多能存多少个数据
int front; //头指针
int tail; //尾指针(队尾数据的下一个位置)
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a = (int*)malloc(sizeof(int)*(k+1)); //需要多开一个空间
obj->front = 0;
obj->tail = 0;
obj->k = k;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->front == obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
int tailNext = obj->tail + 1;
if(tailNext == obj->k+1)
{
//如果tail已经走到尾(不存放数据的位置),此时认为tailNext回到了数组首元素位置
tailNext = 0;
}
return tailNext == obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
if(myCircularQueueIsFull(obj))
{
return false;
}
else
{
obj->a[obj->tail] = value;
obj->tail++;
if(obj->tail == obj->k+1) //也可以取模
{
obj->tail = 0;
}
/* //取模
obj->tail %= (obj->k+1);
*/
return true;
}
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))//如果obj为空了就不能出数据
{
return false;
}
else
{
obj->front++;
//极端情况:front加到尾后重新回到数组首元素
if(obj->front == obj->k+1)
{
obj->front = 0;
}
return true;
}
}
int myCircularQueueFront(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
return obj->a[obj->front];
}
}
int myCircularQueueRear(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
//由于取尾需要去tail的前一个,那么当tail就在首元素的时候,要把它挪到最后一个元素的位置去
int tailPrev = obj->tail - 1;
if(tailPrev == -1)
{
tailPrev = obj->k;
}
return obj->a[tailPrev];
}
}
void myCircularQueueFree(MyCircularQueue* obj)
{
free(obj->a);
free(obj);
}
