栈和队列的总结与应用

椰

发布于 2024-05-16 15:10:02

580

发布于 2024-05-16 15:10:02

文章被收录于专栏：转自CSDN转自CSDN

什么是栈

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。出栈：栈的删除操作叫做出栈。出数据也在栈顶。

就类似于在一个竖直的容器里面放木头，你最先取出来的是你最后放进去的。

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

代码：

头文件

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


typedef int StDataType;

typedef struct Stack
{
	StDataType * a;
	int top;
	int capacity;
}ST;

void STinit(ST* st);
void STDestroy(ST* st);
//入栈 出栈
void STPush(ST* st, StDataType x);
void StPop(ST* st);
//读取数据
StDataType STTop(ST* st);
//判空
bool STEmpty(ST* st);
//获取数据个数
bool STSize(ST* st);

实现文件

#define _CRT_SECURE_NO_WARNINGS
#include"Stack.h"
void STinit(ST* st)
{
	assert(st);
	st->a = NULL;
	st->top = 0;
	st->capacity = 0;
}
void STDestroy(ST* st)
{
	assert(st);
	free(st->a);
	st->a = NULL;
	st->capacity = st->top = 0;
}
//入栈 出栈
void STPush(ST* st, StDataType x)
{
	assert(st);
	if (st->top == st->capacity)
	{
		int newcapacity = st->capacity == 0 ? 4: st->capacity * 2;
		StDataType* tmp = (StDataType*)realloc(st->a, newcapacity * sizeof(StDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		st->a = tmp;
		st->capacity = newcapacity;
	}
	st->a[st->top++] = x;
}
void StPop(ST* st)
{
	assert(st&&st->top>0);
	st->top--;
}
//读取数据
StDataType STTop(ST* st)
{
	assert(st && st->top > 0);
	return st->a[st->top - 1];
}

//判空
bool STEmpty(ST* st)
{
	assert(st);

	return st->top == 0;
}
//获取数据个数
bool STSize(ST* st)
{
	assert(st);

	return st->top;
}

什么是队列

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为队头。

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

代码：

头文件

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

typedef int QDataType;

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

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

void QueueInit(Queue* p);
void QueuePush(Queue* p, QDataType x);
QDataType QueueFront(Queue* p);
QDataType QueueBack(Queue* p);
void QueuePop(Queue* p);
QDataType QueueSize(Queue* p);
bool QueueEmpty(Queue* p);
void QueueDestroy(Queue* p);

实现文件

#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"
void QueueInit(Queue* p)
{
	assert(p);
	p->phead = p->ptail = NULL;
	p->size = 0;
}
void QueuePush(Queue* p, QDataType x)//尾插
{
	assert(p);
	QNode* next = (QNode*)malloc(sizeof(QNode));
	if (next == NULL)
	{
		perror("error malloc");
		exit(1);
	}
	next->next = NULL;
	next->val = x;
	if (p->phead != NULL)
	{
		p->ptail->next = next;
		p->ptail = p->ptail->next;
	}
	else
	{
		p->phead = p->ptail = next;
	}
	p->size++;
}
//头删
void QueuePop(Queue* p)
{
	assert(p&&p->phead);
	if (p->phead->next == NULL)
	{
		free(p->phead);
		p->phead = p->ptail = NULL;
	}
	else
	{
		QNode* ptr = p->phead->next;
		free(p->phead);
		p->phead = ptr;
	}
	p->size--;
}
//读取队列的长度
QDataType QueueSize(Queue* p)
{
	assert(p);
	return p->size;
}
//摧毁队列
void QueueDestroy(Queue* p)
{
	assert(p);
	while (p->phead)
	{
		QueuePop(p);
	}
	p->phead = p->ptail = NULL;
	p->size = 0;
}

bool QueueEmpty(Queue* p)
{
	assert(p);
	return p->size == 0;
}
//查看头部元素
QDataType QueueFront(Queue* p)
{
	assert(p && p->ptail);
	return p->phead->val;
}
//查看尾部元素
QDataType QueueBack(Queue* p)
{
	assert(p && p->ptail);
	return p->ptail->val;
}

例题：

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

typedef char StDataType;

typedef struct Stack
{
	StDataType * a;
	int top;
	int capacity;
}ST;

void STinit(ST* st);
void STDestroy(ST* st);
//入栈 出栈
void STPush(ST* st, StDataType x);
void StPop(ST* st);
//读取数据
StDataType STTop(ST* st);
//判空
bool STEmpty(ST* st);
//获取数据个数
bool STSize(ST* st);
void STinit(ST* st)
{
	assert(st);
	st->a = NULL;
	st->top = 0;
	st->capacity = 0;
}
void STDestroy(ST* st)
{
	assert(st);
	free(st->a);
	st->a = NULL;
	st->capacity = st->top = 0;
}
//入栈 出栈
void STPush(ST* st, StDataType x)
{
	assert(st);
	if (st->top == st->capacity)
	{
		int newcapacity = st->capacity == 0 ? 4: st->capacity * 2;
		StDataType* tmp = (StDataType*)realloc(st->a, newcapacity * sizeof(StDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		st->a = tmp;
		st->capacity = newcapacity;
	}
	st->a[st->top++] = x;
}
void StPop(ST* st)
{
	assert(st&&st->top>0);
	st->top--;
}
//读取数据
StDataType STTop(ST* st)
{
	assert(st && st->top > 0);
	return st->a[st->top - 1];
}

//判空
bool STEmpty(ST* st)
{
	assert(st);

	return st->top == 0;
}
//获取数据个数
bool STSize(ST* st)
{
	assert(st);

	return st->top;
}
bool isValid(char* s) {
    ST st;
    STinit(&st);
    while(*s != 0)
    {
        if(*s == '{' || *s == '[' || *s == '(')
        {
            STPush(&st,*s);
        }
        else
        {
            if(STEmpty(&st))
            {
            STDestroy(&st);
            return false;
            }
            char top = STTop(&st);
            StPop(&st);
            if(top == '(' && *s != ')')
            {
                STDestroy(&st);
                return false;
            }
            if(top == '[' && *s != ']')
            {
                STDestroy(&st);
                return false;
            }  
            if(top == '{' && *s != '}')
            {
                STDestroy(&st);
                return false;
            }
        }
        s++;
    }   
    if(!STEmpty(&st))
    {
    STDestroy(&st);
    return false;
    }
    return true;
}

. - 力扣（LeetCode）

typedef int StDataType;

typedef struct Stack
{
	StDataType * a;
	int top;
	int capacity;
}ST;

void STinit(ST* st);
void STDestroy(ST* st);
//入栈 出栈
void STPush(ST* st, StDataType x);
void StPop(ST* st);
//读取数据
StDataType STTop(ST* st);
//判空
bool STEmpty(ST* st);
//获取数据个数
bool STSize(ST* st);

void STinit(ST* st)
{
	assert(st);
	st->a = NULL;
	st->top = 0;
	st->capacity = 0;
}
void STDestroy(ST* st)
{
	assert(st);
	free(st->a);
	st->a = NULL;
	st->capacity = st->top = 0;
}
//入栈 出栈
void STPush(ST* st, StDataType x)
{
	assert(st);
	if (st->top == st->capacity)
	{
		int newcapacity = st->capacity == 0 ? 4: st->capacity * 2;
		StDataType* tmp = (StDataType*)realloc(st->a, newcapacity * sizeof(StDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		st->a = tmp;
		st->capacity = newcapacity;
	}
	st->a[st->top++] = x;
}
void StPop(ST* st)
{
	assert(st&&st->top>0);
	st->top--;
}
//读取数据
StDataType STTop(ST* st)
{
	assert(st && st->top > 0);
	return st->a[st->top - 1];
}

//判空
bool STEmpty(ST* st)
{
	assert(st);

	return st->top == 0;
}
//获取数据个数
bool STSize(ST* st)
{
	assert(st);

	return st->top;
}

typedef struct {
    ST s1;
    ST s2;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    STinit(&obj->s1);
    STinit(&obj->s2);
    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    if(!STEmpty(&obj->s1))
    {
        STPush(&obj->s1, x);
    }
    else
    {
        STPush(&obj->s2, x);
    }
}

int myQueuePop(MyQueue* obj) {
    ST* Empty = &(obj->s1);
    ST* NonEmpty = &(obj->s2);
    if(!STEmpty(&obj->s1))
    {
        NonEmpty = &(obj->s1);
        Empty = &(obj->s2);
    }
    while(STSize(NonEmpty) > 1)
    {
        STPush(Empty, STTop(NonEmpty));
        StPop(NonEmpty);
    }
    int top = STTop(NonEmpty);
    StPop(NonEmpty);
    return top;
}

int myQueuePeek(MyQueue* obj) {
    ST* Empty = &(obj->s1);
    ST* NonEmpty = &(obj->s2);
    if(!STEmpty(&obj->s1))
    {
        NonEmpty = &(obj->s1);
        Empty = &(obj->s2);
    }
    while(STSize(NonEmpty) > 1)
    {
        STPush(Empty, STTop(NonEmpty));
        StPop(NonEmpty);
    }
    int top = STTop(NonEmpty);
    STPush(Empty, STTop(NonEmpty));
    StPop(NonEmpty);
    return top;
}

bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->s1) && STEmpty(&obj->s2);
}

void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->s1);
    STDestroy(&obj->s2);
    free(obj);
}

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

typedef int StDataType;

typedef struct Stack
{
	StDataType * a;
	int top;
	int capacity;
}ST;

void STinit(ST* st);
void STDestroy(ST* st);
//入栈 出栈
void STPush(ST* st, StDataType x);
void StPop(ST* st);
//读取数据
StDataType STTop(ST* st);
//判空
bool STEmpty(ST* st);
//获取数据个数
int STSize(ST* st);

void STinit(ST* st)
{
	assert(st);
	st->a = NULL;
	st->top = 0;
	st->capacity = 0;
}
void STDestroy(ST* st)
{
	assert(st);
	free(st->a);
	st->a = NULL;
	st->capacity = st->top = 0;
}
//入栈 出栈
void STPush(ST* st, StDataType x)
{
	assert(st);
	if (st->top == st->capacity)
	{
		int newcapacity = st->capacity == 0 ? 4: st->capacity * 2;
		StDataType* tmp = (StDataType*)realloc(st->a, newcapacity * sizeof(StDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		st->a = tmp;
		st->capacity = newcapacity;
	}
	st->a[st->top++] = x;
}
void StPop(ST* st)
{
	assert(st&&st->top>0);
	st->top--;
}
//读取数据
StDataType STTop(ST* st)
{
	assert(st && st->top > 0);
	return st->a[st->top - 1];
}

//判空
bool STEmpty(ST* st)
{
	assert(st);

	return st->top == 0;
}
//获取数据个数
int STSize(ST* st)
{
	assert(st);

	return st->top;
}

typedef struct {
    ST s1;
    ST s2;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    STinit(&obj->s1);
    STinit(&obj->s2);
    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    if(!STEmpty(&obj->s1))
    {
        STPush(&obj->s1, x);
    }
    else
    {
        STPush(&obj->s2, x);
    }
}

int myQueuePop(MyQueue* obj) {
    ST* Empty = &(obj->s1);
    ST* NonEmpty = &(obj->s2);
    if(!STEmpty(&obj->s1))
    {
        NonEmpty = &(obj->s1);
        Empty = &(obj->s2);
    }
    while(STSize(NonEmpty) > 1)
    {
        STPush(Empty, STTop(NonEmpty));
        StPop(NonEmpty);
    }
    int top = STTop(NonEmpty);
    StPop(NonEmpty);
     if(!STEmpty(&obj->s1))
    {
        NonEmpty = &(obj->s1);
        Empty = &(obj->s2);
    }
    while(STSize(NonEmpty))
    {
        STPush(Empty, STTop(NonEmpty));
        StPop(NonEmpty);
    }

    return top;
}

int myQueuePeek(MyQueue* obj) {
    ST* Empty = &(obj->s1);
    ST* NonEmpty = &(obj->s2);
    if(!STEmpty(&obj->s1))
    {
        NonEmpty = &(obj->s1);
        Empty = &(obj->s2);
    }
    while(STSize(NonEmpty) > 1)
    {
        STPush(Empty, STTop(NonEmpty));
        StPop(NonEmpty);
    }
    int top = STTop(NonEmpty);
    STPush(Empty, STTop(NonEmpty));
    StPop(NonEmpty);
    if(!STEmpty(&obj->s1))
    {
        NonEmpty = &(obj->s1);
        Empty = &(obj->s2);
    }
    while(STSize(NonEmpty))
    {
        STPush(Empty, STTop(NonEmpty));
        StPop(NonEmpty);
    }
    return top;
}

bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->s1) && STEmpty(&obj->s2);
}

void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->s1);
    STDestroy(&obj->s2);
    free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

. - 力扣（LeetCode）

typedef struct {
	int* arr;
	int phead;
	int tail;
	int k;
} MyCircularQueue;

//检查队列是否空了
bool Empty(MyCircularQueue* obj)
{
	return obj->tail == obj->phead;
}
//检查队列是否为满的
bool Full(MyCircularQueue* obj)
{
	return (obj->tail + 1 + obj->k + 1) % (obj->k + 1) == obj->phead;
}

MyCircularQueue* myCircularQueueCreate(int k) {
	int* ptr = (int*)malloc((k+1) * sizeof(int*));//创建出K+1 个空间 多出的空间用于判断
	if (ptr == NULL)
	{
		perror("error malloc");
		exit(1);
	}
	MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	obj->arr = ptr;
	obj->phead = obj->tail = 0;
	obj->k = k;
	return obj;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//插
	if (Full(obj))
	{
		return false;
	}
	else//插入元素
	{
		obj->arr[obj->tail] = value;
		obj->tail = (++obj->tail) % (obj->k + 1);
        return true;
	}
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {//删除元素
	if (Empty(obj))
	{
		return false;
	}
	else
	{
		obj->phead = (++obj->phead) % (obj->k + 1);
        return true;
	}
}

int myCircularQueueFront(MyCircularQueue* obj) {
	if (Empty(obj))
	{
		return -1;
	}
	else
	{
		return obj->arr[obj->phead];
	}
}

int myCircularQueueRear(MyCircularQueue* obj) {
	if (Empty(obj))
	{
		return -1;
	}
	else
	{
		return obj->arr[(obj->tail -1 + obj->k + 1) % (obj->k + 1)];
	}
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
	return Empty(obj);
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
	return Full(obj);
}

void myCircularQueueFree(MyCircularQueue* obj) {
	free(obj->arr);
	free(obj);
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-05-14，如有侵权请联系 cloudcommunity@tencent.com 删除

数组