【leetcode】学了栈和队列却觉得无用武之地？试试这几道题目吧！

admin • 2023-02-18 19:58 • C/C++

0.写在前面

1.leetcode.20 有效的括号

2.leetcode.225 用队列实现栈

3.用栈实现队列

4.设计循环队列

0.写在前面

这些题目所用语言为C语言，由于C语言未提供栈和队列的数据结构，所以需要我们手动实现栈和队列。此外熟练掌握栈和队列的性质对解题尤为重要。如果忘记了栈和队列的使用方法可在此直接跳转到栈和队列详解篇。

＜栈＞的概念&结构&实现【C语言版】http://t.csdn.cn/lqe2X ＜队列＞的概念&结构&实现【C语言版】http://t.csdn.cn/iXiZI

1.leetcode.20 有效的括号

OJ链接：有效的括号（点此跳转）

解题思路：遍历字符串，如果碰到 ' ( ' 或 ' [ ' 或 ' { ' 就入栈；如果碰到字符是 ' ) ' ，栈顶的元素又是 ' ( '，就将栈顶的元素出栈。其他两种情况与之类似。

解题实战：

typedef char STDataType;

typedef struct Stack
{
	STDataType* a;  //动态开辟数组
	int capacity; //记录栈的容量大小
	int top; //记录栈顶的位置
}Stack;

//栈的初始化
void StackInit(Stack* ps);
//释放动态开辟的内存
void StackDestroy(Stack* ps);
//压栈
void StackPush(Stack* ps, STDataType data);
//出栈
void StackPop(Stack* ps);
//读取栈顶的元素
STDataType StackTop(Stack* ps);
//判断栈是否为空
bool StackEmpty(Stack* ps);
//栈存储的数据个数
int StackSize(Stack* ps);

void StackInit(Stack* ps)
{
	assert(ps);
	//初始化时，可附初值，也可置空
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void StackDestroy(Stack* ps)
{
	assert(ps);
	//若并未对ps->a申请内存，则无需释放
	if (ps->capacity == 0)
		return;
	//释放
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void StackPush(Stack* ps,STDataType data)
{
	assert(ps);
	//若容量大小等于数据个数，则说明栈已满，需扩容
	if (ps->capacity == ps->top)
	{
		//若为第一次扩容，则大小为4，否则每次扩大2倍
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	//压栈
	ps->a[ps->top] = data;
	ps->top++;
}

void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	//出栈
	ps->top--;
}

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	//返回栈顶的数据
	return ps->a[ps->top - 1];
}

bool StackEmpty(Stack* ps)
{
	assert(ps);
	//返回top
	return ps->top == 0;
}

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}
bool isValid(char* s) {
    Stack ST;
    StackInit(&ST);

    int pos=0;
    //遍历字符串，遇到''结束
    while(*(s+pos) != '')
    {
        if(*(s+pos) == '(' || *(s+pos) == '[' || *(s+pos) == '{')
        {
            StackPush(&ST,*(s+pos));
        }
        else
        {
            if(StackEmpty(&ST))
                return false;
            if((ST.top != 0) &&
               (*(s+pos) == ')' && StackTop(&ST) == '(')||
               (*(s+pos) == ']' && StackTop(&ST) == '[')||
               (*(s+pos) == '}' && StackTop(&ST) == '{'))
            {
                StackPop(&ST);
            }
            else
            {
                return false;
            }
        } 

        pos++;
    }

    if( StackEmpty(&ST) )
    {
        return true;
    }
    else
    {
        return false;
    }
}

2.leetcode.225 用队列实现栈

OJ链接：用队列实现栈

解题思路：首先我们要清楚栈和队列的性质：

栈：先进后出。只在尾部删数据。

队列：先进先出。只在头部删数据。

也就是说，添加数据时，两个是一样的，区别在于删数据时。栈要pop一个数据时，其实pop的是队尾的数据，而不巧的是，队列不能在队尾pop数据。所以此时，我们用两个队列来完成。

栈的结构定义用两个队列来实现。

typedef struct {
    Queue q1;
    Queue q2;
    int size;
} MyStack;

使用两个队列的目的是，其中一个队列用来存储数据，另外一个空的队列在pop的时候用来接收非空的队列的数据。非空队列将数据全部拷贝到空队列，只留下一个队尾的数据，此时，队列只剩一个元素，它既在队尾也在队头，所以就可以pop了。

解题实战：

typedef int QDataType;

typedef struct QueueNode
{
	QDataType data; //存储的数据
	struct QueueNode* next; //记录下一个结点的位置
}QNode;

typedef struct Queue
{
	QNode* head; //记录队头的位置
	QNode* tail; //记录队尾的位置
	int size; //记录队列的长度
}Queue;

//队列的初始化
void QueueInit(Queue* pq);
//释放malloc出的内存
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//获取队头的数据
QDataType QueueFront(Queue* pq);
//获取队尾的数据
QDataType QueueBack(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//队列数据的个数
int QueueSize(Queue* pq);
void QueueInit(Queue* pq)
{
	assert(pq);

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

void QueueDestroy(Queue* pq)
{
	assert(pq);
	//用cur找尾
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;

		free(del);
	}
	pq->size = 0;
	pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq,QDataType data)
{
	assert(pq);

	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	//初始化结点
	newNode->data = data;
	newNode->next = NULL;

	if (pq->tail == NULL)
	{
		//队列为空时入队
		pq->head = newNode;
		pq->tail = newNode;
	}
	else
	{
		//队列不为空时入队
		pq->tail->next = newNode;
		pq->tail = newNode;
	}
	
	pq->size++;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL)
	{
		//只有一个结点时
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		//一般情况
		QNode* del = pq->head;
		pq->head = pq->head->next;

		free(del);
	}
	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->size==0;
	return pq->head == NULL && pq->tail == NULL;
}

int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}


typedef struct {
    Queue q1;
    Queue q2;
    int size;
} MyStack;


MyStack* myStackCreate() {
    MyStack* ps=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&ps->q1);
    QueueInit(&ps->q2);
    ps->size=0;
    return ps;
}

void myStackPush(MyStack* obj, int x) {
    //找一个不为空的队列来push数据
    Queue* noneQueue=(&obj->q1)->size == 0?&obj->q2:&obj->q1;
    QueuePush(noneQueue,x);
    obj->size++;
}

int myStackPop(MyStack* obj) {
    //找空队列
    if ((obj->q2).size == 0)
    {
        QDataType top;
        //复制数据
        while ((&obj->q1)->size > 1)
        {
            top = QueueFront(&obj->q1);
            QueuePop(&obj->q1);
            QueuePush(&obj->q2,top);
        }
        top=QueueFront(&obj->q1);
        QueuePop(&obj->q1);
        obj->size--;
        return top;
    }
    else
    {
        QDataType top;
        //复制数据
        while ((&obj->q2)->size > 1)
        {
            top = QueueFront(&obj->q2);
            QueuePop(&obj->q2);
            QueuePush(&obj->q1,top);
        }
        top = QueueFront(&obj->q2);
        QueuePop(&obj->q2);
        obj->size--;
        return top;
    }
 
}                                        

int myStackTop(MyStack* obj) {
    
    if ((&obj->q1)->size != 0)
        return (&obj->q1)->tail->data;
    else
        return (&obj->q2)->tail->data;

}

bool myStackEmpty(MyStack* obj) {
    return !obj->size;
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
    obj=NULL;
}

3.leetcode.232 用栈实现队列

OJ链接：用栈实现队列

解题思路：同上一题的思路，本题也是用两个栈实现队列。其中s1用来push，s2用来pop和peek。与上一题不同的是，这次pop时，不用一直将s1的数据导入到s2中。而是当s2为空时再导入。

解题实战：

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;  //动态开辟数组
	int capacity; //记录栈的容量大小
	int top; //记录栈顶的位置
}Stack;

//栈的初始化
void StackInit(Stack* ps);
//释放动态开辟的内存
void StackDestroy(Stack* ps);
//压栈
void StackPush(Stack* ps, STDataType data);
//出栈
void StackPop(Stack* ps);
//读取栈顶的元素
STDataType StackTop(Stack* ps);
//判断栈是否为空
bool StackEmpty(Stack* ps);
//栈存储的数据个数
int StackSize(Stack* ps);

void StackInit(Stack* ps)
{
	assert(ps);
	//初始化时，可附初值，也可置空
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void StackDestroy(Stack* ps)
{
	assert(ps);
	//若并未对ps->a申请内存，则无需释放
	if (ps->capacity == 0)
		return;
	//释放
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void StackPush(Stack* ps,STDataType data)
{
	assert(ps);
	//若容量大小等于数据个数，则说明栈已满，需扩容
	if (ps->capacity == ps->top)
	{
		//若为第一次扩容，则大小为4，否则每次扩大2倍
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	//压栈
	ps->a[ps->top] = data;
	ps->top++;
}

void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	//出栈
	ps->top--;
}

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	//返回栈顶的数据
	return ps->a[ps->top - 1];
}

bool StackEmpty(Stack* ps)
{
	assert(ps);
	//返回top
	return ps->top == 0;
}

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

typedef struct {
    Stack s1; //用来push数据
    Stack s2; //用来pop和peek
} MyQueue;

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

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->s1, x);
}

int myQueuePeek(MyQueue* obj) {
    //s2不为空时，不用再将s1的数据导入到s2
    if(StackEmpty(&obj->s2))
    {
        //将s1的数据倒着push到s2中
        while (!StackEmpty(&obj->s1))
        {
            STDataType top = StackTop(&obj->s1);
            StackPop(&obj->s1);
            StackPush(&obj->s2, top);
        }
    }
    //此时s2的数据是逆置的，所以栈顶的数据也就是队头的数据
    return StackTop(&obj->s2);

}

int myQueuePop(MyQueue* obj) {

    STDataType top= myQueuePeek(obj);
    //此时s2的数据是逆置的，pop s2栈顶的数据，也就是pop队头的数据
    StackPop(&obj->s2);
    return top;
}


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

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->s1);
    StackDestroy(&obj->s2);
    free(obj);
    obj = NULL;

4.leetcode.622 设计循环队列

OJ链接：设计循环队列

解题思路：循环队列与普通的队列就两点差别。

1.增加一个capacity来记录队列的容量

2.队尾与队头相连（称之为循环）

解题实战：

typedef int QDataType;

typedef struct QueueNode
{
	QDataType data; //存储的数据
	struct QueueNode* next; //记录下一个结点的位置
}QNode;

typedef struct {
    QNode* head;
    QNode* tail;
    int size;
    int capacity;
} MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* tmp=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    tmp->head=NULL;
    tmp->tail=NULL;
    tmp->size=0;
    tmp->capacity=k;
    return tmp;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    
    if(myCircularQueueIsFull(obj))
        return false;

    QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newNode->next = NULL;
	newNode->data = value;
	if (obj->size == 0)
	{
	    obj->head = obj->tail = newNode;
		obj->size++;

	}
	else
	{
		obj->tail->next = newNode;
		obj->tail = newNode;
        newNode->next=obj->head;
		obj->size++;
	}

    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    
    if(myCircularQueueIsEmpty(obj))
        return false;

    QNode* cur=obj->head;
    obj->head=obj->head->next;
    obj->tail->next=obj->head;
    free(cur);
    obj->size--;
    return true;

}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->head->data;
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->tail->data;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return !obj->size;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->size==obj->capacity;
}

void myCircularQueueFree(MyCircularQueue* obj) {

    if(myCircularQueueIsEmpty(obj))
    {
        free(obj);
        return;
    }
    while(obj->head!=obj->tail)
    {
        QNode* cur=obj->head;
        obj->head=obj->head->next;
        free(cur);
    }
    free(obj->head);
    free(obj);
    obj=NULL;
}

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

c语言 leetcode 数据结构栈队列

二维码

微服务 Spring Boot 整合 Redis BitMap 实现签到与统计

< <上一篇

C语言进阶——字符函数和字符串函数（上）

下一篇>>

搜索内容

【leetcode】学了栈和队列却觉得无用武之地？试试这几道题目吧！

0.写在前面

1.leetcode.20 有效的括号

2.leetcode.225 用队列实现栈

3.leetcode.232 用栈实现队列

4.leetcode.622 设计循环队列

最新文章

分类

标签云