栈和队列的实现及相关面试题

栈和队列

栈
- 概念与结构
- 栈的功能
- 栈的实现
- - 头文件Stack.h
  - - 栈的结构体 Stack
  - 源文件Stack.c
  - - 初始化 void StackInit(Stack* ps)
    - 压栈 void StackPush(Stack* ps, STDataType data)
    - 出栈 void StackPop(Stack* ps)
    - 返回栈顶的值 STDataType StackTop(Stack* ps)
    - 返回栈中元素的个数 int StackSize(Stack* ps)
    - 判断栈是否为空 bool StackEmpty(Stack* ps)
    - 销毁栈 void StackDestroy(Stack* ps)
队列
- 概念与结构
- 队列的功能
- 队列的实现
- - 头文件 Queue.h
  - - 队列的结构体 Queue
  - 队列源文件 Queue.c
  - - 初始化队列 void QueueInit(Queue* q)
    - 队尾入队列 void QueuePush(Queue* q, QDataType data)
    - 队头出队列 void QueuePop(Queue* q)
    - 获取队列头部元素 QDataType QueueFront(Queue* q)
    - 获取队列队尾元素 QDataType QueueBack(Queue* q)
    - 获取队列中有效元素个数 int QueueSize(Queue* q)
    - 判断队列是否为空 bool QueueEmpty(Queue* q)
    - 销毁队列 void QueueDestroy(Queue* q)
栈和队列的结合笔试题
- - 力扣20. 有效的括号
  - - 解题思路
    - 具体步骤
  - 答案
  - - 力扣20.有效的括号

栈

概念与结构

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

栈的功能

1.进栈（压栈）：栈的插入操作，入数据在栈顶，如下图所示：
在这里插入图片描述
2.出栈：栈的删除操作，出数据也在栈顶，如下图所示：

栈的实现

这里栈的实现，我们可以使用链表或者顺序表的结构来实现，这里我们使用顺序表的结构来实现，因为数组栈相较于链表栈更容易实现。

头文件Stack.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int STDataType;
typedef struct Stack
{
	STDataType* _a;
	int _top;		// 栈顶
	int _capacity;  // 容量 
}Stack;

void StackInit(Stack* ps);
void StackPush(Stack* ps, STDataType data);

void StackPop(Stack* ps);
STDataType StackTop(Stack* ps);

int StackSize(Stack* ps);
bool StackEmpty(Stack* ps);

void StackDestroy(Stack* ps);

栈的结构体 Stack

typedef int STDataType;

typedef struct Stack
{
	STDataType* _a;
	int _top;		// 栈顶
	int _capacity;  // 容量 
}Stack;

本次变量我们以int类型来进行充当栈的存储数据类型，所以利用typedef对STDataType进行命名。
再创建一种结构体类型Stack，这里的Stack结构体与顺序表中的结构体相同，内含一个**STDataType数组类型的成员变量**，一个表示栈顶的下标的整型变量_top，还有一个表示栈空间大小的整型变量_capacity。

源文件Stack.c

初始化 void StackInit(Stack* ps)

void StackInit(Stack* ps)
{
	assert(ps);
	ps->_a = NULL;
	ps->_capacity = 0;
	ps->_top = -1;
}

先断言确保程序的正常运行。
将数组指针置空以防止野指针的使用，再将数组空间_capacity置为0，栈的下标置为-1，因为此时栈中没有一个数组元素。

压栈 void StackPush(Stack* ps, STDataType data)

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	
	if (ps->_capacity == ps->_top + 1)
	{
		int newcapacity = !ps->_capacity ? 4 : 2 * ps->_capacity;
		STDataType* tmp = (STDataType*)realloc(ps->_a, sizeof(STDataType) * newcapacity);
		if(!tmp)
		{
			perror("realloc");
			return;
		}
		ps->_a = tmp;
		tmp = NULL;
		ps->_capacity = newcapacity;
	}

	ps->_top++;
	ps->_a[ps->_top] = data;
}

先断言确保程序的正常运行。
利用if语句对栈的内存空间进行检查，若空间不够就进行扩容，利用三目运算符进行扩容空间大小的选择判断，再利用realloc来为结构体中的数组重新分配空间，为防止分配失败，我们利用新命名的tmp来接收，即使分配失败我们也可以避免返回NULL来覆盖原有的数组ps->_a数据。
确保空间足够后，将栈的下标_top让自增1，再将数据放到数组的相应下标即可。

出栈 void StackPop(Stack* ps)

void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > -1);
	ps->_top--;
}

先断言确保程序的正常运行，栈的下标为-1时数组中没有一个元素，不存在出栈。
这里的出栈只要让ps->_top自减1即可，因为我们是通过下标进行访问的。

返回栈顶的值 STDataType StackTop(Stack* ps)

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > -1);
	return ps->_a[ps->_top];
}

先断言确保程序的正常运行，栈的下标为-1时数组中没有一个元素，也就不存在栈顶的值了。
利用下标直接返回数组的值即可。

返回栈中元素的个数 int StackSize(Stack* ps)

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top + 1;
}

先断言确保程序的正常运行。
返回数组下标的值加1即可。

判断栈是否为空 bool StackEmpty(Stack* ps)

int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->_top == -1;
}

先断言确保程序的正常运行。
若为空则返回0，但栈顶下标为-1时，栈为空，所以返回 ps->_top == -1 这判断语句的值即可。

销毁栈 void StackDestroy(Stack* ps)

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_capacity = 0;
	ps->_top = -1;
}

先断言确保程序的正常运行。
先free栈中的数组ps->_a，再将ps->_capacity，ps->_top置为初始值即可。

队列

概念与结构

队列只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列要求先进先出
FIFO(First In First Out)的方式。

队列的功能

入队列：进行插入操作的一端称为队尾。
出队列：进行删除操作的一端称为队头。

队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
所以，在这里我们使用链表来实现队列。

头文件 Queue.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QDataType;

typedef struct QListNode
{
	QDataType _data;
	struct QListNode* _next;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
}Queue;

void QueueInit(Queue* q);

void QueuePush(Queue* q, QDataType data);

void QueuePop(Queue* q);

QDataType QueueFront(Queue* q);

QDataType QueueBack(Queue* q);

int QueueSize(Queue* q);

bool QueueEmpty(Queue* q);

void QueueDestroy(Queue* q);

队列的结构体 Queue

typedef struct QListNode
{
	QDataType _data;
	struct QListNode* _next;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
}Queue;

struct QListNode：定义一个链表结点的结构体。
struct Queue：定义一个存放链表头结点_front与尾结点_rear的结构体，这就表示一个队列的结构体。

队列源文件 Queue.c

初始化队列 void QueueInit(Queue* q)

void QueueInit(Queue* q)
{
	assert(q);
	q->_front = q->_rear = NULL;
}

先断言确保程序的正常运行。
将队列中表示链表头结点与尾结点的指针都置为空即可，因为队列中没有任何数据。

队尾入队列 void QueuePush(Queue* q, QDataType data)

void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* node = (QNode*)malloc(sizeof(QNode));
	assert(node);
	node->_next = NULL;
	node->_data = data;
	if (q->_front == NULL)
	{
		q->_front = q->_rear = node;
		return;
	}
	q->_rear->_next = node;
	q->_rear = node;
}

先断言确保程序的正常运行。
定义一个node指针，指向malloc所申请的一块大小为QNode的空间，再断言node，以确保node指针的正常使用，再将其初始化即可。
利用if语句判断队列中的头结点是否为空，若为空则将刚刚申请的node赋给队列的头结点与尾结点，然后直接退出函数即可；
若不为空，则向链表进行尾插，再将node指向尾结点的指针赋给q->_rear即可。

队头出队列 void QueuePop(Queue* q)

void QueuePop(Queue* q)
{
	assert(q);
	assert(q->_front);

	if (q->_front == q->_rear)
	{
		free(q->_front);
		q->_front = q->_rear = NULL;
		return;
	}

	QNode* pcur = q->_front->_next;

	free(q->_front);
	q->_front = pcur;
}

先断言确保程序的正常运行，若q->_front为空，则不存在出队列这一说法。
利用if语句判断队列是否只有一个结点这一特殊情况，若为特殊情况，则先用free释放掉唯一的结点，再将q->_front 与q->_rear置为空即可。
若为正常情况，则进行单链表的头删。

获取队列头部元素 QDataType QueueFront(Queue* q)

QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->_front);
	return q->_front->_data;
}

先断言确保程序的正常运行，若q->_front为空，则不存在获取队列头部元素这一说法。
若通过，直接返回头结点的值即可。

获取队列队尾元素 QDataType QueueBack(Queue* q)

QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->_rear);
	return q->_rear->_data;
}

先断言确保程序的正常运行，若q->_rear为空，则不存在获取队列尾部元素这一说法。
若通过，直接返回尾结点的值即可。

获取队列中有效元素个数 int QueueSize(Queue* q)

int QueueSize(Queue* q)
{
	assert(q);
	QNode* pcur = q->_front;
	int x = 0;
	while (pcur)
	{
		x++;
		pcur = pcur->_next;
	}
	return x;
}

先断言确保程序的正常运行。
定义一个指向队列头结点的指针pcur和一个记录队列中有效元素的整型变量x，再利用while循环进行链表的遍历，最后在返回x即可。

判断队列是否为空 bool QueueEmpty(Queue* q)

bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->_front == NULL;
}

先断言确保程序的正常运行。
若队列中的头结点为空，则返回1，反之返回0。

销毁队列 void QueueDestroy(Queue* q)

void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* pcur = q->_front;

	while (pcur)
	{
		QNode* del = pcur;
		pcur = pcur->_next;
		free(del);
	}

	q->_front = q->_rear = NULL;
}

先断言确保程序的正常运行。
再定义一个指向队列头结点的指针pcur，再利用while循环依次删除即可，最后将q->_front 与 q->_rear 置为空。

栈和队列的结合笔试题

力扣20. 有效的括号

题目如下：
在这里插入图片描述

解题思路

这道题目就很适合使用栈来解决，我们可以假定有一个" { [ ( ) ] } ( ) "这样的字符串，根据括号的顺序，我们可以先让指向字符串首元素的指针s遍历整个字符串，在遍历的同时把左括号'{' '[' '('放入栈中，当遇到右括号'}' ']' ')'这个时候就是利用栈判断的时候，根据逻辑在遇到右括号前，上一个遇到的一定是其相应的左括号，所以若栈顶不是右括号的相应括号或栈中为空，则一定不满足条件；若s遍历了整个字符串，且此时栈中为空时则说明整个字符串都满足条件。

在这里插入图片描述

具体步骤

先将我们上面写的栈的头文件与源文件的源代码复制过来。
再新建一个栈并初始化，利用while循环遍历字符串，当字符s为左括号时将其压栈，若不为右括号，则进行判断，如果栈中为空，则说明不满足条件，若不为空，则定义一个字符变量top，将栈顶的值赋给top，再利用if循环判断括号是否同类对应，若不为对应，则销毁站并返回，代码如下：

    while(*s)
    {
        if(*s=='['||*s=='('||*s=='{')
        {
            StackPush(&st,*s);
        }
        else 
        {
			if(!StackEmpty(&st))
			{
				StackDestroy(&st);
            	return false;
			}
			char top = StackTop(&st);
			StackPop(&st);
            if((*s==']'&&top!='[')
            ||(*s==')'&&top!='(')
            ||(*s=='}'&&top!='{'))
            {
				StackDestroy(&st);
                return false;
            }
        }
        s++;
    }

如此循环，遍历每一个字符，遍历完全之后跳出循环，定义布尔变量ret，若栈中为空，这说明整个字符串都满足条件返回1 ，反之返回 0 ，

	bool ret=!StackEmpty(&st);
	StackDestroy(&st);
    return ret;

答案

代码如下：

力扣20.有效的括号


typedef char STDataType;
typedef struct Stack
{
	STDataType* _a;
	int _top;		
	int _capacity;  
}Stack;

void StackInit(Stack* ps);
void StackPush(Stack* ps, STDataType data);

void StackPop(Stack* ps);
STDataType StackTop(Stack* ps);

int StackSize(Stack* ps);
int StackEmpty(Stack* ps);

void StackDestroy(Stack* ps);


void StackInit(Stack* ps)
{
	assert(ps);
	ps->_a = NULL;
	ps->_capacity = 0;
	ps->_top = -1;
}

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	
	if (ps->_capacity == ps->_top + 1)
	{
		int newcapacity = !ps->_capacity ? 4 : 2 * ps->_capacity;
		STDataType* tmp = (STDataType*)realloc(ps->_a, sizeof(STDataType) * newcapacity);
		assert(tmp);
		ps->_a = tmp;
		tmp = NULL;
		ps->_capacity = newcapacity;
	}

	ps->_top++;
	ps->_a[ps->_top] = data;
}

void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > -1);
	ps->_top--;
}

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > -1);
	return ps->_a[ps->_top];
}

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top + 1;
}

int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->_top > -1;
}

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_capacity = 0;
	ps->_top = -1;
}

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;
			}
			char top = StackTop(&st);
			StackPop(&st);
            if((*s==']'&&top!='[')
            ||(*s==')'&&top!='(')
            ||(*s=='}'&&top!='{'))
            {
				StackDestroy(&st);
                return false;
            }
        }
        s++;
    }
	bool ret=!StackEmpty(&st);
	StackDestroy(&st);
    return ret;
}