C语言描述数据结构 —— 栈和队列OJ题
1.括号匹配问题
很显然,本篇文章的标题出卖了这道题,我们将使用栈来解决这道题。对于栈和队列,C 语言的库中并没有这两个数据结构,但在 C++ 的库中是可以直接使用这两种数据结构的。局限于目前我们只会使用 C 语言,所以在解这道题时,需要做一个前置工作,就是将我们写好的栈复制过来。这里我给出了上一篇关于栈和队列实现的代码。
//可以动态开辟空间的栈
typedef char StackData;//注意是字符元素
typedef struct Stack
{
StackData* a;
int top;//与顺序表的 size 一致
int capacity;
}Stack;
void StackInit(Stack* ps);//栈初始化
void StackPush(Stack* ps,StackData x);//入栈
void StackPop(Stack* ps);//出栈
StackData StackTop(Stack* ps);//获取栈顶元素
bool StackEmpty(Stack* ps);//判断栈是否为空
int StackSize(Stack* ps);//计算栈元素个数
void StackDestroy(Stack* ps);//栈销毁
//初始化栈
void StackInit(Stack* ps)
{
assert(ps);
//栈的初始容量置空
ps->a = NULL;
ps->top = ps->capacity = 0;
}
//入栈
void StackPush(Stack* ps,StackData x)
{
assert(ps);
//入栈只有一种方式,所以不需要将扩容独立封装
if (ps->top == ps->capacity)
{
int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
StackData* tmp = (StackData*)realloc(ps->a, NewCapacity*sizeof(StackData));
assert(tmp);
ps->a = tmp;
ps->capacity = NewCapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
//出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
//获取栈顶元素
StackData StackTop(Stack* ps)
{
assert(ps);
return ps -> a[ps->top - 1];
}
//判断栈是否为空
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;//等于 0 则返回true,即栈为空
}
//计算栈中元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
//栈销毁
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
做好了前置工作之后现在我们就要试着来解题。我们来分析一下思路:
我们将它们转换为代码:
bool isValid(char * s){
Stack st;
StackInit(&st);
while(*s)
{
if(*s == '(' || *s == '[' || *s == '{')
{
StackPush(&st,*s);
}
else
{
//如果没有一个左括号入栈
if(StackEmpty(&st))
{
StackDestroy(&st);
return false;
}
else
{
char top = StackTop(&st);
StackPop(&st);
//如果有任何不满足匹配的情况就返回 false
if(*s == ')' && top == '(' ||
*s == ']' && top == '[' ||
*s == '}' && top == '{')
{
StackDestroy(&st);
return false;
}
}
}
s++;
}
//如果括号匹配的话,那么栈中就应该没有任何元素
//这个例子见于字符串中全是左括号,没有满足任何匹配条件,就不会出栈
//不会出栈就会导致栈中有元素,即不为空
bool flag = StackEmpty(&st);
StackDestroy(&st);
return flag;
}
2.用队列实现栈
注意看题,题目的要求是让我们用两个队列来实现栈。那么现在就要搞清楚队列转化为栈的难点是什么。队列的特征是先进先出,如果我们入队的数据是 1、2、3、4、5 ,那么出队的顺序也是 1、2、3、4、5 。而栈的特征是先进后出,即我们入栈的数据是 1、2、3、4、5,那么出栈的顺序是 5、4、3、2、1 。由此可见入队和入栈的方式一样,差别在于出队和出栈的顺序不同。我们需要解决的便是出的问题,还有就是删除的问题。
我们知道,我们实现队列的数据结构是链表。题目的要求是让我们使用两个队列,两个队列如何实现获取队尾元素和尾删呢?
我们拿出我们使用链表实现队列的代码,并将它复制到我们的题目上面去。
//链表的结点
typedef int QueueData;
typedef struct QueueNode
{
QueueData val;
struct QueueNode* next;
}QueueNode;
//存储头、尾结点地址的指针
typedef struct HeadTail
{
QueueNode* head;
QueueNode* tail;
int size;//记录队列有几个元素
}HeadTail;
void QueueInit(HeadTail* p);//初始化队列
void QueuePush(HeadTail* p,QueueData x);//进入队列
QueueData QueueHead(HeadTail* p);//获取队头元素
QueueData QueueTail(HeadTail* p);//获取队尾元素
void QueuePop(HeadTail* p);//删除操作,出队
bool QueueEmpty(HeadTail* p);//检查队列是否为空
int QueueSize(HeadTail* p);//获取队列元素个数
void QueuePopTail(HeadTail* p);
void QueueDestroy(HeadTail* p);//销毁队列
//初始化
void QueueInit(HeadTail* p)
{
assert(p);
p->head = p->tail = NULL;
p->size = 0;
}
//队列尾插
void QueuePush(HeadTail* p, QueueData x)
{
assert(p);
//创建一个新结点
QueueNode* newnode = (QueueNode*)calloc(1, sizeof(QueueNode));
assert(newnode);
newnode->val = x;
newnode->next = NULL;
//如果链表内没有结点,头尾指针指向同一个结点
if (p->head == NULL)
{
p->head = newnode;
p->tail = newnode;
}
//否则尾指针需要变化
else
{
p->tail->next = newnode;
p->tail = newnode;
}
p->size++;
}
//获取队头元素
QueueData QueueHead(HeadTail* p)
{
assert(p);
assert(!QueueEmpty(p));
return p->head->val;
}
//获取队尾元素
QueueData QueueTail(HeadTail* p)
{
assert(p);
assert(!QueueEmpty(p));
return p->tail->val;
}
//删除、出队
void QueuePop(HeadTail* p)
{
assert(p);
assert(!QueueEmpty(p));
//如果链表只有一个结点
if (p->head == p->tail)
{
free(p->head);
p->head = p->tail = NULL;
}
//否则进行头删
else
{
QueueNode* cur = p->head;
p->head = p->head->next;
free(cur);
cur = NULL;
}
p->size--;
}
//检测队列是否为空
bool QueueEmpty(HeadTail* p)
{
assert(p);
return p->head == NULL && p->tail == NULL;
}
//获取队列元素个数
int QueueSize(HeadTail* p)
{
assert(p);
return p->size;
}
//销毁队列
void QueueDestroy(HeadTail* p)
{
assert(p);
QueueNode* cur = p->head;
while (cur)
{
QueueNode* del = cur;
cur = cur->next;
free(del);
}
}
typedef struct {
HeadTail q1;
HeadTail q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* obj = (MyStack*)calloc(1,sizeof(MyStack));
//取 q1、q2 的地址传入函数
QueueInit(&obj->q1);
QueueInit(&obj->q2);
return obj;
}
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的size-1个倒入q1
//并将q2剩下的最后一个当成栈顶元素返回
if(QueueEmpty(&obj->q1))
{
while(QueueSize(&obj->q2) > 1)
{
QueuePush(&obj->q1,QueueHead(&obj->q2));
QueuePop(&obj->q2);
}
int ret = QueueTail(&obj->q2);
QueuePop(&obj->q2);
return ret;
}
//如果q2为空,将q1的size-1个倒入q2
//并将q1剩下的最后一个当成栈顶元素返回
else
{
while(QueueSize(&obj->q1) > 1)
{
QueuePush(&obj->q2,QueueHead(&obj->q1));
QueuePop(&obj->q1);
}
int ret = QueueTail(&obj->q1);
QueuePop(&obj->q1);
return ret;
}
}
int myStackTop(MyStack* obj) {
//这个函数并没有要求要删除数据
//所以直接返回非空队列的队尾元素
if(!QueueEmpty(&obj->q1))
{
return QueueTail(&obj->q1);
}
else
{
return QueueTail(&obj->q2);
}
}
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
//obj里面存放的只是q1、q2空间的地址
//所以需要独立释放q1、q2空间
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}
3.用栈实现队列
这里的题目要求是用两个栈实现队列,那么肯定是要涉及倒数据的。我们现在来具体分析如何倒数据。
我们将我们实现栈的数据结构的代码复制到题目中去:
//可以动态开辟空间的栈
typedef int StackData;
typedef struct Stack
{
StackData* a;
int top;//与顺序表的 size 一致
int capacity;
}Stack;
void StackInit(Stack* ps);//栈初始化
void StackPush(Stack* ps,StackData x);//入栈
void StackPop(Stack* ps);//出栈
StackData StackTop(Stack* ps);//获取栈顶元素
bool StackEmpty(Stack* ps);//判断栈是否为空
int StackSize(Stack* ps);//计算栈元素个数
void StackDestroy(Stack* ps);//栈销毁
//初始化栈
void StackInit(Stack* ps)
{
assert(ps);
//栈的初始容量置空
ps->a = NULL;
ps->top = ps->capacity = 0;
}
//入栈
void StackPush(Stack* ps,StackData x)
{
assert(ps);
//入栈只有一种方式,所以不需要将扩容独立封装
if (ps->top == ps->capacity)
{
int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
StackData* tmp = (StackData*)realloc(ps->a, NewCapacity*sizeof(StackData));
assert(tmp);
ps->a = tmp;
ps->capacity = NewCapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
//出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
//获取栈顶元素
StackData StackTop(Stack* ps)
{
assert(ps);
return ps -> a[ps->top - 1];
}
//判断栈是否为空
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;//等于 0 则返回true,即栈为空
}
//计算栈中元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
//栈销毁
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
typedef struct {
Stack push;
Stack pop;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* obj = (MyQueue*)calloc(1,sizeof(MyQueue));
StackInit(&obj->push);
StackInit(&obj->pop);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
//只向push栈插入数据
StackPush(&obj->push,x);
}
int myQueuePop(MyQueue* obj) {
//要向pop栈中倒入数据
if(StackEmpty(&obj->pop))
{
while(!StackEmpty(&obj->push))
{
StackPush(&obj->pop,StackTop(&obj->push));
StackPop(&obj->push);
}
}
int ret = StackTop(&obj->pop);
StackPop(&obj->pop);
return ret;
}
int myQueuePeek(MyQueue* obj) {
//只有向pop栈倒入数据才能取到最先进去的那个元素
if(StackEmpty(&obj->pop))
{
while(!StackEmpty(&obj->push))
{
StackPush(&obj->pop,StackTop(&obj->push));
StackPop(&obj->push);
}
}
return StackTop(&obj->pop);
}
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->push) && StackEmpty(&obj->pop);
}
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->push);
StackDestroy(&obj->pop);
free(obj);
}
4.设计循环队列
我们先不关注题目的要求,就单单循环队列而言,我们先选择合适的数据结构。
我们有两种数据结构可选,一是链表,而是顺序表。那么那种数据结构优势较大呢?首先我们来看看循环队列是什么。
那么其次,我们把这个逻辑结构套到两种数据结构上面去。
有了上面的分析基础,现在就可以尝试去解题了。
typedef struct {
int* a;
int head;//头
int tail;//尾
int size;//长度
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)calloc(1,sizeof(MyCircularQueue));
obj->a = (int*)calloc(1,sizeof(int)*(k+1));//顺序表的空间多开一个
obj->head = obj->tail = 0;
obj->size=k+1;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->head == obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->tail+1)%obj->size == obj->head;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
return false;
obj->a[obj->tail]=value;
obj->tail++;
obj->tail %= obj->size;//确保tail的值不会超过长度范围
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return false;
obj->head++;
obj->head %= obj->size;//确保head的值不会超过长度范围
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;
//推导的公式,以防tail的值为 0
return obj->a[(obj->tail-1+obj->size)%obj->size];
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
版权声明:本文为weixin_59913110原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
THE END