目录

栈

习题 

 结构体的创建

初始化 

销毁开辟空间 

入栈 

出栈 

当前栈顶

判断栈是否为空 

统计个数 

力扣习题——有效的括号 

 队列

 结构体的建立

初始化 

动态内存销毁 

入队

 出队

 提取数据

 判断是否为空

队内元素个数统计 

---

栈

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

 

 动态开辟在堆区，堆向上增长，递归次数过多会导致栈溢出

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

习题 

 1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出
栈的顺序是（ ）。
A 12345ABCDE
B EDCBA54321
C ABCDE12345
D 54321EDCBA

B 先进后出

2.若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,1
C A1先入，再出1，然后入2，3，4，出4，3，2

    B先入1，2出2，入3，出3，入4，出4，出1

    D入1，2，3出3，入4，出4，出2，出1

 结构体的创建

typedef int STDdtaTtype;
typedef struct Stcak
{
	STDdtaTtype* data;
	int top;
	int capacity;
}ST;

初始化 

void StackInit(ST* ps)
{
	assert(ps);
	ps->data = NULL;
	ps->capacity = ps->top = 0;
}

销毁开辟空间 

void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->data);
	ps->capacity = ps->top = 0;
	ps->data = NULL;
}

入栈 

void StackPush(ST* ps, STDdtaTtype x)//注意要看top的位置是0还是-1
{
	assert(ps);
	int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
	if (ps->capacity == ps->top)//判断是否满了
	{
		STDdtaTtype* tmp = realloc(ps->data, sizeof(ps) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
 
		}
		ps->data = tmp;
		ps->capacity = newcapacity;
	}
	ps->data[ps->top] = x;
	ps->top++;
}

出栈 

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	--ps->top;
}

当前栈顶

STDdtaTtype StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->data[ps->top - 1];
}

判断栈是否为空 

bool StackEmpty(ST* ps)//判断是否为空栈
{
	assert(ps);
	return ps->top == 0;
}

统计个数 

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

力扣习题——有效的括号 

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

 

当s指向左括号时，把该括号放入栈内

入完栈之后s不等于左括号，s等于右括号，然后将栈内的元素一个个拿出来跟s所指括号比较，若能匹配成功，则进行下一轮比较，反之则直接返回false

typedef char STDdtaTtype;
typedef struct Stcak
{
	STDdtaTtype* data;
	int top;
	int capacity;
}ST;
void StackInit(ST* ps);
void StackDestory(ST* ps);
void StackPush(ST* ps, STDdtaTtype x);
void StackPop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);
STDdtaTtype StackTop(ST* ps);
void StackInit(ST* ps)
{
	assert(ps);
	ps->data = NULL;
	ps->capacity = ps->top = 0;
}
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->data);
	ps->capacity = ps->top = 0;
	ps->data = NULL;
}
void StackPush(ST* ps, STDdtaTtype x)//注意要看top的位置是0还是-1
{
	assert(ps);
	int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
	if (ps->capacity == ps->top)//判断是否满了
	{
		STDdtaTtype* tmp = realloc(ps->data, sizeof(ps) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
 
		}
		ps->data = tmp;
		ps->capacity = newcapacity;
	}
	ps->data[ps->top] = x;
	ps->top++;
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	--ps->top;
}
STDdtaTtype StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->data[ps->top - 1];
}
bool StackEmpty(ST* ps)//判断是否为空栈
{
	assert(ps);
	return ps->top == 0;
}
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

 把上面栈的函数都复制下来，进行括号匹配

bool isValid(char * s){
ST st;
StackInit(&st);
while(*s)
{
    if(*s=='['||*s=='{'||*s=='(')
    {
       StackPush(&st,*s);
    }
    else
    {
        if(StackEmpty(&st))//若栈内为空，直接返回false，这种情况如只S数组只有一个[
{ 
       StackDestory(&st);//防止内存泄漏
        return false;
}
       STDdtaTtype top=StackTop(&st);
       StackPop(&st);
        if(*s==']'&&top!='['
        ||*s=='}'&&top!='{'
        ||*s==')'&&top!='(')
        {
            return false;
        }
    }
    s++;
}
bool flag=(StackEmpty(&st));//若全部匹配则，栈内为空，若没有则不为空
StackDestory(&st);
return flag;
}

 队列

 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头，一般用单链表实现队列，双向链表比较浪费

 结构体的建立

typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	size_t size;
}Queue;

初始化 

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

动态内存销毁 

void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
		del = NULL;
	}
	pq->head = pq->tail = NULL;
}

入队

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = pq->tail->next;
	}
	pq->size++;
}

 出队

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}//如果只剩一个节点，单独处理，要不染当head遍历到tail时候，tail会成为野指针，这里要防止tail变为野指针
	else
	{
		QNode* cur = pq->head;
		pq->head = pq->head->next;
		free(cur);
		cur = NULL;
	}
	pq->size--;
}

 提取数据

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;
}

 判断是否为空

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

队内元素个数统计 

int QueueSize(Queue* pq)
{
	return pq->size;
}