1. Toy模板网首页
  2. > Toy博客

LeetCode 热题100——栈与队列专题（三）

10月前 作者：日刷百题 分类：Toy博客 阅读(45) 违法举报

这篇具有很好参考价值的文章主要介绍了LeetCode 热题100——栈与队列专题（三）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、有效的括号

20.有效的括号（题目链接）

LeetCode 热题100——栈与队列专题（三）,LeetCode,leetcode,算法,java

思路：

1）括号的顺序匹配：用栈实现，遇到左括号入，遇到右括号出（保证所出的左括号与右括号对应），否则顺序不匹配。

2）括号的数量匹配：

1>左括号大于右括号：用栈实现，遇到左括号入，遇到右括号出，遍历完字符数组，此时栈不为空，则说明左括号数量大于右括号；

2>右括号大于左括号：遇到右括号出时，判断栈是否为空，若此时栈为空，说明右括号数量大于左括号；

typedef char  SDateType;
typedef struct Stack
{
	SDateType* a;
	int top;
	int capacity;

}Stack;
//初始化栈和销毁栈
void InitStack(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
void DestoryStack(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;

}

//出栈和入栈
void StackPush(Stack* ps, SDateType x)
{
	assert(ps);
	//扩容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SDateType* tmp = (SDateType*)realloc( ps->a,newcapacity * sizeof(SDateType));
		if (tmp == NULL)
		{
			perror("realloc fail:");
			return;
		}
		ps->a = tmp;
		ps->capacity = newcapacity;

	}
	//尾插
	ps->a[ps->top] = x;
	ps->top++;
}
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);//只少有一个元素，才能删除
	ps->top--;
}

//栈的有效个数和栈顶元素
int  StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}
int   StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

//栈是否为空
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}
int isValid(char* s) {
	Stack ps;
	InitStack(&ps);

	while (*s)
	{
		if (*s == '[' || *s == '(' || *s == '{')
		{
			StackPush(&ps, *s);
			s++;
		}
		else

		{
			if (StackEmpty(&ps))
			{
				return false;
			}
			char tmp = StackTop(&ps);
			StackPop(&ps);
			if ((*s == ']' && tmp != '[') ||
				(*s == '}' && tmp != '{') ||
				(*s == ')' && tmp != '('))
			{
				return false;
			}

			s++;

		}
	}
	if (!StackEmpty(&ps))
	{
		return false;
	}
	else {
		return true;
	}
	DestoryStack(&ps);
}

二、用队列实现栈 

225. 用队列复制栈（题目链接）

LeetCode 热题100——栈与队列专题（三）,LeetCode,leetcode,算法,java

思路： 栈是后进先出，队列是先进先出。

用俩队列实现栈

1）入栈时，选择有数据的队列入数据；

2）出栈时，将有数据队列中前k-1个数据出队列，并入到空队列中，返回并出有数据队列的最后一个数据

LeetCode 热题100——栈与队列专题（三）,LeetCode,leetcode,算法,java

typedef int QDateType;
typedef struct QueueNode
{
	QDateType val;
	struct QueueNode * next;
}QueueNode;
typedef struct Queue
{
	QueueNode *head;
	QueueNode *tail;
	QDateType size;
}Queue;

// 初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueuePush(Queue* pq, QDateType x)
{
	assert(pq);
	QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
	
	node->val = x;
	node->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = node;
		pq->size++;
	}
	else
	{
		pq->tail->next = node;
		pq->tail = node;
		pq->size++;
	}
}
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);//只少保证一个节点
	QueueNode* del = pq->head;
	pq->head = pq->head->next;
	free(del);
	del = NULL;
	pq->size--;
	if (pq->head == NULL)//只有一个节点处理
	{
		pq->tail = NULL;
	}
}

// 返回队头和队尾
QDateType QueueFront(Queue* pq)
{
	assert(pq);
	return pq->head->val;
}
QDateType QueueBack(Queue* pq)
{
	assert(pq);
	return pq->tail->val;
}

// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}



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

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;

}
typedef struct {
    Queue q1;
     Queue q2;

} MyStack;


MyStack* myStackCreate() {
    MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;

}

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else{
        QueuePush(&obj->q2,x);
    }
}
bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

int myStackPop(MyStack* obj) {
    assert(!myStackEmpty(obj));
    Queue * empty=&obj->q1;
    Queue * nonempty=&obj->q2;
    if(!QueueEmpty(empty))
    {
        empty=&obj->q2;
        nonempty=&obj->q1;
    }
    while(QueueSize(nonempty)!=1)
    {
       int tmp= QueueFront(nonempty);
       QueuePush(empty,tmp);
        QueuePop(nonempty);
    }
     int tmp= QueueFront(nonempty);
      QueuePop(nonempty);
      return tmp;
}

int myStackTop(MyStack* obj) {
     assert(!myStackEmpty(obj));
    Queue * empty=&obj->q1;
    Queue * nonempty=&obj->q2;
    if(!QueueEmpty(empty))
    {
        empty=&obj->q2;
        nonempty=&obj->q1;
    }
    return QueueBack(nonempty);
}



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

}

三、用栈实现队列 

225. 用栈实现队列（题目链接）

LeetCode 热题100——栈与队列专题（三）,LeetCode,leetcode,算法,java

思路： 栈是后进先出，队列是先进先出。

1）入队列：s1栈用来在栈顶入数据；

2）出队列：s2栈用来出栈顶数据，如果s2为空，则从s1出数据入到s2中去（比如;s1中的数据为1，2，3，入到s2变为3，2，1），再出s2的栈顶数据，这样就满足队列的性质了

 LeetCode 热题100——栈与队列专题（三）,LeetCode,leetcode,算法,java

typedef int  SDateType;
typedef struct Stack
{
	SDateType* a;
	int top;
	int capacity;

}Stack;
//初始化栈和销毁栈
void InitStack(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
void DestoryStack(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;

}

//出栈和入栈
void StackPush(Stack* ps, SDateType x)
{
	assert(ps);
	//扩容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SDateType* tmp = (SDateType*)realloc( ps->a,newcapacity * sizeof(SDateType));
		if (tmp == NULL)
		{
			perror("realloc fail:");
			return;
		}
		ps->a = tmp;
		ps->capacity = newcapacity;

	}
	//尾插
	ps->a[ps->top] = x;
	ps->top++;
}
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);//只少有一个元素，才能删除
	ps->top--;
}

//栈的有效个数和栈顶元素
int  StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}
int   StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

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



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


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

}

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

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

int myQueuePop(MyQueue* obj) {
    assert(!myQueueEmpty(obj));
    if(StackEmpty(&obj->s2))
    {
       while(!StackEmpty(&obj->s1))
       {
          int tmp= StackTop(&obj->s1);
          StackPush(&obj->s2,tmp);
          StackPop(&obj->s1);
       }
      
    }
     int tmp= StackTop(&obj->s2);
       StackPop(&obj->s2);
       return tmp;
}

int myQueuePeek(MyQueue* obj) {
     assert(!myQueueEmpty(obj));
    if(StackEmpty(&obj->s2))
    {
       while(!StackEmpty(&obj->s1))
       {
          int tmp= StackTop(&obj->s1);
          StackPush(&obj->s2,tmp);
          StackPop(&obj->s1);
       }
       
    }
    return StackTop(&obj->s2);
}



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



}

 四、设计循环队列

622.设计循环队列（题目链接）

LeetCode 热题100——栈与队列专题（三）,LeetCode,leetcode,算法,java

思路一：数组

以front为队列头下标，tail为队列尾下一个元素下标，一共k个数据，开辟k+1个整型大小空间，方便区分队列为空、为满以及一个元素的情况

1）队列为空，front=tail

2）队列为1个元素，front+1=tail

3)   队列为满，（tail+1)%(k+1)==front

 LeetCode 热题100——栈与队列专题（三）,LeetCode,leetcode,算法,java

typedef struct {
    int *a;
    int front;
    int rear;
    int n;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    int * tmp=(int *)malloc(sizeof(int)*(k+1));
    obj->a=tmp;
    obj->front=0;
    obj->rear=0;
    obj->n=k;
    return obj;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if((obj->rear+1)%(obj->n+1)==obj->front)
    {
        return true;
    }
    return false;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull( obj))
    {
        return false;
    }
    obj->a[obj->rear]=value;
    obj->rear++;
    obj->rear=obj->rear%(obj->n+1);
    return true;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if(obj->front==obj->rear)
    {
        return true;
    }
    return false;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty( obj))
    {
        return false;
    }
    obj->front++;
    obj->front=obj->front%(obj->n+1);
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty( obj))
    {
        return -1;
    }
    return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty( obj))
    {
        return -1;
    }
    return  obj->a[(obj->rear-1+obj->n+1)%(obj->n+1)];
}




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

思路二：单向循环链表

以head为队列头节点，tail为队列尾尾节点的下一个节点，一共k个数据，开辟k+1个节点的循环单向链表，方便区分队列为空、为满以及一个元素的情况

1）队列为空，head=tail

2）队列为1个元素，head->next=tail

3)   队列为满，tail->next=head

LeetCode 热题100——栈与队列专题（三）,LeetCode,leetcode,算法,java LeetCode 热题100——栈与队列专题（三）,LeetCode,leetcode,算法,java文章来源地址https://www.toymoban.com/news/detail-758748.html

typedef struct QueueNode
{
	int val;
	struct QueueNode * next;
}QueueNode;

QueueNode* BuyNode(int x)
{
    QueueNode* node=(QueueNode*)malloc(sizeof(QueueNode));
    node->val=x;
    node->next=NULL;
    return node;
}
typedef struct MyCircularQueue{
   QueueNode *head;
	QueueNode *tail;
    QueueNode * pretail;
	int n;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    QueueNode* node=BuyNode(0);
    obj->pretail=NULL;
    obj->head=obj->tail=node;
    obj->n=(k+1);
    QueueNode* cur=obj->tail;
    while(k--)
    {
       QueueNode* node=BuyNode(0);
     
      cur->next=node;
        cur= cur->next;
    }
   
   cur->next=obj->head;
    return obj;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if(obj->tail->next==obj->head)
    {
        return true;
    }
    return false;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull( obj))
    {
        return false;
    }
    obj->tail->val=value;
    obj->pretail=obj->tail;
    obj->tail=obj->tail->next;
   
     
    return true;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if(obj->head==obj->tail)
    {
        return true;
    }
    return false;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty( obj))
    {
        return false;
    }
    obj->head=obj->head->next;
   
    return true;
}

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

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




void myCircularQueueFree(MyCircularQueue* obj) {
   while(obj->n--)
   {
       QueueNode*next=obj->head->next;
       free(obj->head);
       obj->head=next;
   }
   obj->head=NULL;
    free(obj);
}

到了这里，关于LeetCode 热题100——栈与队列专题（三）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • LeetCode 热题 100 | 哈希

    LeetCode 热题 100 | 哈希

    目录 1  基础知识 1.1  定义哈希表 1.2  遍历哈希表 1.3  查找某一个键 1.4  插入键值对 1.5  获取键值对的值 1.6  搜索功能 2  三道题 2.1  1. 两数之和 2.2  49. 字母异位词分组 2.3  128. 最长连续序列 菜鸟做题第一周，语言是 C++ 1  基础知识 1.1  定义哈希表 unordered_map 用于定义

    2024年01月18日
    浏览(47)

  • 螺旋矩阵 LeetCode热题100

    给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。 模拟，朝一个方向走，走过的点标记一下，直到碰到边界或碰到已经走过的路，换个方向。右-下，下-左，左-上，上-右。直到走完所有点。

    2024年02月14日
    浏览(63)
  • LeetCode热题100——链表

    LeetCode热题100——链表

    给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回

    2024年02月05日
    浏览(43)
  • LeetCode 热题 100 | 链表（上）

    LeetCode 热题 100 | 链表（上）

    目录 1  基础知识 1.1  空指针 1.2  结构体 1.3  指针访问 1.4  三目运算符 2  160. 相交链表 3  206. 反转链表 4  234. 回文链表 菜鸟做题第三周，语言是 C++ 1  基础知识 1.1  空指针 使用 nullptr 来判断是否为空指针： “NULL 在 C++ 中就是 0，这是因为在 C++ 中 void* 类型是不允许隐式

    2024年02月19日
    浏览(41)

  • Leetcode热题100

    暴力：{i,j}直接返回vectorint 哈希表： map: 红黑树 具有自动排序的功能，是非严格的二叉搜索树。map内部的所有元素都是有序的，使用中序遍历可将键值按照从小到大遍历出来。插入的时间是O(logn),查询时间是O(logn)。可以支持所有类型的键值对 unordered_map: 哈希表（也叫散列表

    2024年02月14日
    浏览(51)
  • LeetCode 热题100——单调栈

    LeetCode 热题100——单调栈

    ​   个人主页： 日刷百题 系列专栏 ： 〖C语言小游戏〗 〖Linux〗 〖数据结构〗   〖C语言〗 🌎 欢迎各位 → 点赞 👍+ 收藏 ⭐️+ 留言 📝  ​ ​ 递增单调栈：栈中元素从栈底到栈顶依次增大 递减单调栈：栈中元素从栈底到栈顶依次减小 在学习完朴素的数据结构栈之后，

    2024年02月04日
    浏览(40)
  • LeetCode热题 100整理

    LeetCode热题 100整理

    35. 搜索插入位置 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 输入: nums = [1,3,5,6], target = 5 输出: 2 示例 2: 输入: nums = [1,3,5,6], target

    2024年02月13日
    浏览(38)
  • LeetCode热题100——图论

    LeetCode热题100——图论

    给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 输入：grid = [ [“1”,“1”,“1”,“1”,“0”], [“1”,“1”,“0”,“1”,“0”], [“1”,“1”

    2024年01月16日
    浏览(76)
  • LeetCode 热题 HOT 100

    LeetCode 热题 HOT 100

    重点是当有一个链表为空了不单独处理，按节点为0处理。 滑动窗口！ 首先要判断slow需不需要更新，怎么判断？slow = max(umap[s[fast]], slow);什么意思，就是说：**umap[s[fast]]的意义是，为了在slow和fast之间不出现重复字符，slow能处于的最左位置。**如图，当j第一次到d，将umap[s[j

    2024年02月07日
    浏览(47)
  • 【LeetCode热题100】【矩阵】螺旋矩阵

    【LeetCode热题100】【矩阵】螺旋矩阵

    题目链接：54. 螺旋矩阵 - 力扣（LeetCode） 先走外面的圈再走里面的圈，可以用递归来解决，对于要走的一个圈，由四个角决定，其实是三个数，（0，0），（0，n），（m，0），（m，n），每次先从左上角走到右上角，再走到右下角，再走到左下角，再走回来 对于后面两个的往

    2024年04月16日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包