目录
原题链接
剑指offer_在线编程_牛客网 (nowcoder.com)
题目描述
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
- 1 <= values <= 10000
- 最多会对
appendTail、deleteHead进行 10000 次调用
题目样例
示例 1
输入
- ["CQueue","appendTail","deleteHead","deleteHead"]
- [[],[3],[],[]]
输出
[null,null,3,-1]示例 2
输入
- ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
- [[],[],[5],[2],[],[]]
输出
[null,-1,null,null,5,2]解决方案
核心思路
- 栈是一种后进先出（LIFO, Last In First Out）的数据结构，而队列是一种先进先出（FIFO, First In First Out）的数据结构。
- 通过使用两个栈，我们可以将栈的“后进先出”特性转化为队列的“先进先出”特性。
两个栈的作用
- 栈1（
stack1）：用于插入操作 (appendTail)。 - 栈2（
stack2）：用于删除操作 (deleteHead)。
操作细节
- appendTail（插入操作）：每次插入时，直接将元素压入
stack1中。 - deleteHead（删除操作）：
- 如果
stack2为空：将stack1中的所有元素依次弹出并压入stack2中，再从stack2弹出栈顶元素作为要删除的元素。 - 如果
stack2不为空：直接从stack2弹出栈顶元素。 - 这样，当从
stack2弹出元素时，正好是队列的最前面的元素，实现了队列的FIFO特性。 - 如果
stack1和stack2都为空，返回-1。
代码解答
python语言：
class CQueue:
def __init__(self):
self.stack1 = [] # 用于插入的栈
self.stack2 = [] # 用于删除的栈
def appendTail(self, value: int) -> None:
self.stack1.append(value)
def deleteHead(self) -> int:
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop())
if not self.stack2:
return -1
else:
return self.stack2.pop()C语言:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct StackNode {
int data;
struct StackNode* next;
} StackNode;
typedef struct {
StackNode* top1;
StackNode* top2;
} CQueue;
CQueue* newCQueue() {
CQueue* queue = (CQueue*)malloc(sizeof(CQueue));
queue->top1 = NULL;
queue->top2 = NULL;
return queue;
}
void appendTail(CQueue* queue, int value) {
StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
newNode->data = value;
newNode->next = queue->top1;
queue->top1 = newNode;
}
int deleteHead(CQueue* queue) {
if (queue->top2 == NULL) {
while (queue->top1!= NULL) {
StackNode* temp = queue->top1;
queue->top1 = queue->top1->next;
temp->next = queue->top2;
queue->top2 = temp;
}
}
if (queue->top2 == NULL) {
return -1;
} else {
int value = queue->top2->data;
StackNode* temp = queue->top2;
queue->top2 = queue->top2->next;
free(temp);
return value;
}
}
void freeQueue(CQueue* queue) {
while (queue->top1!= NULL) {
StackNode* temp = queue->top1;
queue->top1 = queue->top1->next;
free(temp);
}
while (queue->top2!= NULL) {
StackNode* temp = queue->top2;
queue->top2 = queue->top2->next;
free(temp);
}
free(queue);
}Java语言：
class CQueue {
private java.util.Stack<Integer> stack1;
private java.util.Stack<Integer> stack2;
public CQueue() {
stack1 = new java.util.Stack<>();
stack2 = new java.util.Stack<>();
}
public void appendTail(int value) {
stack1.push(value);
}
public int deleteHead() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.isEmpty()? -1 : stack2.pop();
}
}复杂度分析
- 时间复杂度：
-
appendTail：每次插入操作只涉及栈1的append操作，时间复杂度为O(1)。deleteHead：最坏情况下，stack1中的所有元素都要搬到stack2，时间复杂度为O(n)，但每个元素最多只会搬一次，因此摊销时间复杂度为O(1)。
- 空间复杂度：O(n)，其中n为存储在队列中的元素个数。
总结
通过两个栈的相互配合，我们可以实现队列的插入和删除操作，使得时间复杂度达到较优水平。这种设计有效地利用了栈的特性来模拟队列的行为。