[算法] leetcode栈与队列相关题目详解

迈不过友情╰ 2022-10-15 00:52 195阅读 0赞

leetcode栈与队列相关题目详解

### 目录 ###

*  1. leetcode 225\_用队列实现栈
 *   *  题目描述
     *  解题思路
     *  代码实现
 *  2. leetcode 232\_用栈实现队列
 *   *  题目描述
     *  解题思路
     *  代码实现
 *  3. leetcode 622\_设计循环队列
 *   *  题目描述
     *  解题思路
     *  代码实现

# 1. leetcode 225\_用队列实现栈 #

## 题目描述 ##

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通队列的全部四种操作（push、top、pop 和 empty）。
    
    	实现 MyStack 类：
    	void push(int x) 将元素 x 压入栈顶。
    	int pop() 移除并返回栈顶元素。
    	int top() 返回栈顶元素。
    	boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
    
    	注意：
    	你只能使用队列的基本操作 ―― 也就是 push to back、peek / pop from front、size 和 is empty 这些操作。
    	你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列, 只要是标准的队列操作即可。
    
    	示例：
    	输入：
    	["MyStack", "push", "push", "top", "pop", "empty"]
    	[[], [1], [2], [], [], []]
    	输出：
    	[null, null, null, 2, 2, false]
    
    	解释：
    	MyStack myStack = new MyStack();
    	myStack.push(1);
    	myStack.push(2);
    	myStack.top(); // 返回 2
    	myStack.pop(); // 返回 2
    	myStack.empty(); // 返回 False
    
    	提示：
    	1 <= x <= 9
    	最多调用100 次 push、pop、top 和 empty
    	每次调用 pop 和 top 都保证栈不为空
    
    	https://leetcode-cn.com/problems/implement-stack-using-queues/

## 解题思路 ##

需要使用两个队列模拟实现栈。  
  入栈时，判断哪个队列不空，将元素放入不空的队列中。  
  出栈时，判断哪个队列中有元素，将有元素的队列前 N-1个元素放入另外一个队列中，最后队剩余元素出队。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center]

## 代码实现 ##

typedef struct { 
    	Queue q1;
    	Queue q2;
    } MyStack;
    
    /** Initialize your data structure here. */
    
    MyStack* myStackCreate() { 
    	MyStack* stack = (MyStack*)malloc(sizeof(MyStack));
    	if (stack == NULL)
    		return NULL;
    
    	QueueInit(&stack->q1);
    	QueueInit(&stack->q2);
    
    	return stack;
    }
    
    /** Push element x onto stack. */
    void myStackPush(MyStack* obj, int x) { 
    	if (!QueueEmpty(&obj->q1))
    	{ 
    		QueuePush(&obj->q1, x);
    	}
    	else
    	{ 
    		QueuePush(&obj->q2, x);
    	}
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int myStackPop(MyStack* obj) { 
    
    	int data = 0;
    
    	// q1不空将前 n-1 个元素搬移到q2
    	if (!QueueEmpty(&obj->q1))
    	{ 
    		while (QueueSize(&obj->q1) > 1)
    		{ 
    			QueuePush(&obj->q2, QueueFront(&obj->q1));
    			QueuePop(&obj->q1);
    		}
    
    		data = QueueFront(&obj->q1);
    		QueuePop(&obj->q1);
    	}
    	else
    	{ 
    		while (QueueSize(&obj->q2) > 1)
    		{ 
    			QueuePush(&obj->q1, QueueFront(&obj->q2));
    			QueuePop(&obj->q2);
    		}
    
    		data = QueueFront(&obj->q2);
    		QueuePop(&obj->q2);
    	}
    
    	return data;
    }
    /** Get the top element. */
    int myStackTop(MyStack* obj) { 
    
    	if (!QueueEmpty(&obj->q1))
    	{ 
    		return QueueBack(&obj->q1);
    	}
    
    	return QueueBack(&obj->q2);
    }
    
    /** Returns whether the stack is empty. */
    bool myStackEmpty(MyStack* obj) { 
    	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
    }
    
    void myStackFree(MyStack* obj) { 
    	QueueDestroy(&obj->q2);
    	QueueDestroy(&obj->q1);
    
    	free(obj);
    }

# 2. leetcode 232\_用栈实现队列 #

## 题目描述 ##

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
    
    	实现 MyQueue 类：
    	void push(int x) 将元素 x 推到队列的末尾
    	int pop() 从队列的开头移除并返回元素
    	int peek() 返回队列开头的元素
    	boolean empty() 如果队列为空，返回 true ；否则，返回 false
    
    
    	说明：
    	你只能使用标准的栈操作 ―― 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
    	你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
    
    	示例：
    	输入：
    	["MyQueue", "push", "push", "peek", "pop", "empty"]
    	[[], [1], [2], [], [], []]
    	输出：
    	[null, null, null, 1, 1, false]
    
    	解释：
    	MyQueue myQueue = new MyQueue();
    	myQueue.push(1); // queue is: [1]
    	myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
    	myQueue.peek(); // return 1
    	myQueue.pop(); // return 1, queue is [2]
    	myQueue.empty(); // return false
    
    
    	提示：
    	1 <= x <= 9
    	最多调用 100 次 push、pop、peek 和 empty
    	假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
    
    	https://leetcode-cn.com/problems/implement-queue-using-stacks/

## 解题思路 ##

该题与上题思路基本一致，同样采用两个栈实现。  
  入队列时：直接向其中一个栈入栈。  
  出队列时：检测另一个栈是否有元素，有元素则出栈，没有元素则将s1元素导入至s2中，并队栈顶出栈。

## 代码实现 ##

typedef struct { 
    	Stack s1;
    	Stack s2;
    } MyQueue;
    
    /** Initialize your data structure here. */
    
    MyQueue* myQueueCreate() { 
    	MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));
    	if (NULL == queue)
    		return NULL;
    
    	StackInit(&queue->s1);
    	StackInit(&queue->s2);
    
    	return queue;
    }
    
    /** Push element x to the back of queue. */
    void myQueuePush(MyQueue* obj, int x) { 
    	assert(obj);
    
    	StackPush(&obj->s1, x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int myQueuePop(MyQueue* obj) { 
    	assert(obj);
    
    	DataType data = 0;
    
    	if (StackEmpty(&obj->s2))
    	{ 
    		while (StackSize(&obj->s1) > 0)
    		{ 
    			StackPush(&obj->s2, StackTop(&obj->s1));
    			StackPop(&obj->s1);
    		}
    
    		// 出栈
    		data = StackTop(&obj->s2);
    		StackPop(&obj->s2);
    	}
    	else
    	{ 
    		data = StackTop(&obj->s2);
    		StackPop(&obj->s2);
    	}
    
    	return data;
    }
    
    /** Get the front element. */
    int myQueuePeek(MyQueue* obj) { 
    
    	// 如果s1不为空并且s2不为空，则代表刚入栈完成，所以要将s1的元素搬移至s2，并输出栈顶元素
    	if (!StackEmpty(&obj->s1) && StackEmpty(&obj->s2))
    	{ 
    		while (StackSize(&obj->s1))
    		{ 
    			StackPush(&obj->s2, StackTop(&obj->s1));
    			StackPop(&obj->s1);
    		}
    
    		return StackTop(&obj->s2);
    	}
    
    	return StackTop(&obj->s2);
    }
    
    /** Returns whether the queue is empty. */
    bool myQueueEmpty(MyQueue* obj) { 
    	return StackEmpty(&obj->s1) && StackEmpty(&obj->s2);
    }
    
    void myQueueFree(MyQueue* obj) { 
    	StackDestroy(&obj->s1);
    	StackDestroy(&obj->s2);
    	free(obj);
    }

# 3. leetcode 622\_设计循环队列 #

## 题目描述 ##

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
    
    循环队列的一个好处是我们可以利用这个队列之前用过的空间。
    在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，
    即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
    
    你的实现应该支持如下操作：
    MyCircularQueue(k) : 构造器，设置队列长度为 k 。
    Front : 从队首获取元素。如果队列为空，返回 - 1 。
    Rear : 获取队尾元素。如果队列为空，返回 - 1 。
    enQueue(value) : 向循环队列插入一个元素。如果成功插入则返回真。
    deQueue() : 从循环队列中删除一个元素。如果成功删除则返回真。
    isEmpty() : 检查循环队列是否为空。
    isFull() : 检查循环队列是否已满。
    
    
    示例：
    MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
    circularQueue.enQueue(1);  // 返回 true
    circularQueue.enQueue(2);  // 返回 true
    circularQueue.enQueue(3);  // 返回 true
    circularQueue.enQueue(4);  // 返回 false，队列已满
    circularQueue.Rear();  // 返回 3
    circularQueue.isFull();  // 返回 true
    circularQueue.deQueue();  // 返回 true
    circularQueue.enQueue(4);  // 返回 true
    circularQueue.Rear();  // 返回 4
    
    
    提示：
    所有的值都在 0 至 1000 的范围内；
    操作数将在 1 至 1000 的范围内；
    请不要使用内置的队列库。
    
    https://leetcode-cn.com/problems/design-circular-queue/

## 解题思路 ##

利用数组实现循环队列，具体思路点击 [队列与循环队列][Link 1]。

## 代码实现 ##

typedef int DataType;
    
    typedef struct { 
    	DataType* data;
    	int front;
    	int rear;
    	int size;
    	int count;
    } MyCircularQueue;
    
    
    MyCircularQueue* myCircularQueueCreate(int k) { 
    	MyCircularQueue* mcq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    	if (NULL == mcq)
    	{ 
    		return NULL;
    	}
    
    	mcq->data = (DataType*)malloc(k * sizeof(DataType) + 1);
    	if (NULL == mcq->data)
    	{ 
    		return NULL;
    	}
    
    	mcq->front = mcq->rear = 0;
    	mcq->size = k;
    	mcq->count = 0;
    
    	return mcq;
    }
    
    bool myCircularQueueIsEmpty(MyCircularQueue* obj) { 
    	if (obj->count == 0)
    	{ 
    		return true;
    	}
    
    	return false;
    }
    
    bool myCircularQueueIsFull(MyCircularQueue* obj) { 
    	if (obj->count == obj->size)
    	{ 
    		return true;
    	}
    
    	return false;
    }
    
    bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { 
    	if (myCircularQueueIsFull(obj))
    	{ 
    		return false;
    	}
    
    	if (obj->rear == obj->size)
    		obj->rear = 0;
    
    	obj->data[obj->rear++] = value;
    	obj->count++;
    	return true;
    }
    
    bool myCircularQueueDeQueue(MyCircularQueue* obj) { 
    	if (myCircularQueueIsEmpty(obj))
    		return false;
    
    	if (obj->front == obj->size)
    		obj->front = 0;
    	else
    		obj->front++;
    	obj->count--;
    
    	return true;
    }
    
    int myCircularQueueFront(MyCircularQueue* obj) { 
    	if (myCircularQueueIsEmpty(obj))
    		return -1;
    
    	return obj->data[obj->front];
    }
    
    int myCircularQueueRear(MyCircularQueue* obj) { 
    	if (myCircularQueueIsEmpty(obj))
    		return -1;
    
    	return obj->data[obj->rear - 1];
    }
    
    void myCircularQueueFree(MyCircularQueue* obj) { 
    	free(obj->data);
    	obj->data = NULL;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221014/053f2feb96a9495c802cd18a520ce86d.png
[Link 1]: https://blog.csdn.net/weixin_43717520/article/details/117151413?spm=1001.2014.3001.5501