C语言实现数据结构的栈和队列（附三题OJ+画图-＞解析

 

开端：栈和队列是重要的数据结构，其特性会很好地使其在处理数据关系地题目中出现身影。 一、栈

  在操作系统中，栈的特性是数据后进先出。数据结构中利用顺序表实现栈，栈的插入相当于顺序表的尾插，出栈相当于顺序表的尾删。

上代码！

//Stack.h
#pragma once
#include
#include
#include
#include
typedef int STDataType;
typedef struct Stack
{
	STDataType* p;
	int Capacity;
	int top;
}ST;

//初始化栈
void StackInit(ST* ps);

//压栈
void StackPush(ST* ps, STDataType x);

//弹栈
void StackPop(ST* ps);

//取栈顶数据
STDataType StackTop(ST* ps);

//判断栈是否为空
bool IsStackEmpty(ST* ps);

//计算栈内数据个数
int StackSize(ST* ps);

//销毁栈
void StackDestroy(ST* stack);

Stack.c
void StackInit(ST* ps)
{
	ps->p = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->p == NULL) {
		printf("开辟失败n");
		return;
	}
	ps->Capacity = 4;
	ps->top = 0;
}
void StackPush(ST* ps, int x)
{
	if (ps->top == ps->Capacity) {
		STDataType* tmp = realloc(ps->p, sizeof(STDataType) * ps->Capacity * 2);
		if (tmp==NULL) {
			printf("开辟失败n");
			return;
		}
		else {
			printf("开辟成功n");
			ps->p = tmp;
			ps->Capacity *= 2;
		}
	}
	ps->p[ps->top] = x;
	ps->top++;
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}
STDataType StackTop(ST*ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->p[ps->top-1];
}
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
bool IsStackEmpty(ST*ps)
{
	assert(ps);
	return ps->top == 0;
}
void StackDestroy(ST* ps)
{
	free(ps->p);
	ps->p = NULL;
	ps->Capacity = ps->top = 0;
}

---

二、队列

  队列的特性正好与栈相反，队列是数据先进先出。数据结构中用链表实现队列，出列相当于链表的头删，入列相当于链表的尾插。

直接上代码~

//Queue.h
#include
#include
#include
#include
typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

//初始化队列
void QueueInit(Queue* pq);


//销毁队列
void QueueDestory(Queue* pq);


// 队尾入
void QueuePush(Queue* pq, QDataType x);


// 队头出
void QueuePop(Queue* pq);


//取队头元素
QDataType QueueFront(Queue* pq);


//取队尾元素
QDataType QueueBack(Queue* pq);


//计算队列数据个数
int QueueSize(Queue* pq);


//判断队列是否为空
bool QueueEmpty(Queue* pq);

//Queue.c
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

void QueueDestory(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->head = pq->tail = NULL;
}

// 队尾入
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc failn");
		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(pq->head);

	// 1、一个
	// 2、多个
	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;
	}
}


QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->tail->data;
}

int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}

	return size;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

---

三、栈和队列OJ

Q1: 20. 有效的括号 - 力扣（LeetCode）

题目描述：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：1.左括号必须用相同类型的右括号闭合。
                                 2.左括号必须以正确的顺序闭合。

举个例子：s = "{[]}"就是有效的        s = "([)]"是无效的

思路：栈的特点是后进先出，可以很好地解决后入栈的左括号与新入栈的右括号进行匹对。本题要考虑很多种特殊情况，代码细节量比较多，思维考虑比较多，很好地锻炼了代码能力！

typedef char STDataType;
typedef struct Stack
{
	STDataType* p;
	int Capacity;
	int top;
}ST;
void StackInit(ST* ps);
void StackPush(ST* ps,  STDataType x);
void StackPop(ST* ps);
STDataType StackTop(ST* ps);
bool IsStackEmpty(ST* ps);
void StackDestroy(ST* stack);
void StackInit(ST* ps)
{
	ps->p = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->p == NULL) {
		printf("开辟失败n");
		return;
	}
	ps->Capacity = 4;
	ps->top = 0;
}
void StackPush(ST* ps, STDataType x)
{
	if (ps->top == ps->Capacity) {
		STDataType* tmp = realloc(ps->p, sizeof(STDataType) * ps->Capacity * 2);
		if (tmp==NULL) {
			printf("开辟失败n");
			return;
		}
		else {
			printf("开辟成功n");
			ps->p = tmp;
			ps->Capacity *= 2;
		}
	}
	ps->p[ps->top] = x;
	ps->top++;
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}
STDataType StackTop(ST*ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->p[ps->top-1];
}
bool IsStackEmpty(ST*ps)
{
    return ps->top==0;
}
void StackDestroy(ST* ps)
{
	free(ps->p);
	ps->p = NULL;
    ps->Capacity = ps->top = 0;
}

//接口型没有Stack,需要我们自己创建并写函数接口代码！！

//用栈的特点解决
bool isValid(char * s){
ST stack;
StackInit(&stack);
while(*s)
{
    //左括号入栈
    if(*s=='('||*s=='['||*s=='{')
    {
        StackPush(&stack,*s);
    }
    else{
        //判断栈是否为空而有右括号入栈
        if(IsStackEmpty(&stack))
        {
            StackDestroy(&stack);
            return false;
        }
        //取出栈顶元素与右括号匹配
        char top=StackTop(&stack);
        StackPop(&stack);
        //1.匹配失败
        if((*s==')'&&top!='(')||
        (*s==']'&&top!='[')||
        (*s=='}'&&top!='{'))
       { 
           StackDestroy(&stack);
           return false;
       }
    }
    //2.成功继续
    s++;
}
//判断栈是否为空，为空说明完全匹配，否则匹配不完全
if(IsStackEmpty(&stack))
{
    StackDestroy(&stack);
    return true;
}
else{
    StackDestroy(&stack);
    return false;
}
}

---

Q2：225. 用队列实现栈 - 力扣（LeetCode）

题目：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

思路：画图出思路！

Pop数据思路

将有数据队列N个数据得前N-1数据放入另一个空队列中，再Pop数据

Push数据思路

插入数据Push应该向非空列队插入，配合Pop思路，现探究中途插入数据的情况下得此结论！

 其它函数实现难度不大，现在上代码！注意队列函数需要我们自己拷贝进来，我省去了！

//1.确定基本结构框架（两个队列
typedef struct {
Queue q1;
Queue q2;
} MyStack;

//2.初始化栈
MyStack* myStackCreate() {
MyStack*obj=(MyStack*)malloc(sizeof(MyStack));//切记勿直接定义一个栈，返回栈地址！局部变量生命周期！
QueueInit(&obj->q1);
QueueInit(&obj->q2);
return obj;
}
//3.哪个队列不为空，就往哪个队列插入
void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty(&obj->q1))
{
    QueuePush(&obj->q1,x);
}
else{
    QueuePush(&obj->q2,x);
}
}
//哪个队列为空，就将有数据队列Pop数据到空队列去，直到有数据队列数据Size==1,保存（栈顶）元素再Pop
int myStackPop(MyStack* obj) {
if(!QueueEmpty(&obj->q1))
{
    while(QueueSize(&obj->q1)!=1)
    {
        QueuePush(&obj->q2,QueueFront(&obj->q1));
        QueuePop(&obj->q1);
    }
    int top=QueueFront(&obj->q1);
    QueuePop(&obj->q1);
    return top;
}
else{
    while(QueueSize(&obj->q2)!=1)
    {
        QueuePush(&obj->q1,QueueFront(&obj->q2));
        QueuePop(&obj->q2);
    }
    int top=QueueFront(&obj->q2);
    QueuePop(&obj->q2);
    return top;
}
}
//利用队列Back函数功能，获得队列队尾（栈的栈顶）的Data
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) {
QueueDestory(&obj->q1);
QueueDestory(&obj->q2);
free(obj);
}

---

Q3：232. 用栈实现队列 - 力扣（LeetCode）

题目：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

思路还是用画图出结果！

归纳一下思路，设计两个栈，一个栈负责入数据，一个栈负责出数据，将入数据栈的数据导入出数据栈，前提必须是出数据栈是空！ 

上代码！同样栈接口函数要自己拷贝进去，我省略了！

typedef struct {
    ST stackPush;
    ST stackPop;
} MyQueue;

//将入数据栈的数据导入出数据栈中
void StackPushToPop(MyQueue*obj)
{
    while(!IsStackEmpty(&obj->stackPush))
    {
        StackPush(&obj->stackPop,StackTop(&obj->stackPush));
        StackPop(&obj->stackPush);
    }
}

//初始化队列
MyQueue* myQueueCreate() {
MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
StackInit(&obj->stackPush);
StackInit(&obj->stackPop);
return obj;
}

//入列
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->stackPush,x);
}

//出列，如果出数据栈为空，那就先导入数据，否则直接出数据！！！
int myQueuePop(MyQueue* obj) {
if(IsStackEmpty(&obj->stackPop))
StackPushToPop(obj);
int top=StackTop(&obj->stackPop);
StackPop(&obj->stackPop);
return top;
}

//获得队头数据，就是出数据栈顶数据
int myQueuePeek(MyQueue* obj) {
if(IsStackEmpty(&obj->stackPop))
StackPushToPop(obj);
return StackTop(&obj->stackPop);
}

//判断队列是否为空，两栈都空说明数据出完了
bool myQueueEmpty(MyQueue* obj) {
return IsStackEmpty(&obj->stackPush)&&IsStackEmpty(&obj->stackPop);
}

//销毁队列
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->stackPush);
StackDestroy(&obj->stackPop);
free(obj);
}

四、OJ小结

  以上三道OJ题需要通过画图可以很好地获取思路，希望读者看完这篇文章以后可以多画画图，实现图码结合，相信你会有很大进步的！