1. 用栈实现队列(OJ链接)
题目描述:请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty)
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空,返回 true ;否则,返回 false
假设入队的顺序是1,2,3,4,5,那么出队的顺序也需要是1,2,3,4,5
栈的性质是先进后出,但是我们有两个栈,如果把数据pop到另一个栈中,再出数据,那么会怎么样呢?
看下图。
此时我们从stack2中出数据会发现,出队的顺序变成了1,2,3,4,5
此时需要进数据的话,就需要进入到stack1,当stack2为空时,若需要pop数据,则将stack1的数据倒到stack2中再进行pop。
那么push和pop操作就可以理解为:有两个栈,stack1和stack2,push数据时永远push到stack1中,pop数据从stack2中pop,如果stack2为空,那么将stack1中的数据全部倒到stack2中,再进行pop。
peek操作为获取队头元素,由于经过一轮的倒入,再stack2中的栈顶数据就是队头了,直接返回该数据即可,如果stack2为空,则需要先从stack1中入数据到stack2中。
判空操作:两个栈都为空,那么队列就为空。
用栈实现队列,我们需要一个栈的数据结构,之前已经写过了,这里直接拷贝过来用即可。
完整代码如下
typedef int STDataType;
typedef struct StackNode
{
int capacity; //最大容量
int top; //栈顶数据的下一个位置
STDataType* arr; //数组
}STNode;
//初始化顺序栈
void StackInit(STNode* ps)
{
ps->arr = NULL;
ps->capacity = 0;
ps->top = 0;
}
//销毁栈
void StackDestroy(STNode* ps)
{
free(ps->arr);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
//入栈
void StackPush(STNode* ps, STDataType x)
{
//没有空间或者空间满了,先扩容
if (ps->capacity == ps->top)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->arr,sizeof(STNode) * newcapacity);
if (tmp == NULL)
{
perror("malloc()");
return;
}
ps->arr = tmp;
ps->capacity = newcapacity;
}
//插入数据
ps->arr[ps->top++] = x;
}
//出栈
void StackPop(STNode* ps)
{
ps->top--;
}
//判断栈空
bool StackEmpty(STNode* ps)
{
return ps->top == 0;
}
//获得栈顶元素
int FindTop(STNode* ps)
{
return ps->arr[ps->top - 1];
}
typedef struct
{
STNode stack1;//push数据的栈
STNode stack2;//pop数据的栈
} MyQueue;
MyQueue* myQueueCreate()
{
MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
StackInit(&obj->stack1);
StackInit(&obj->stack2);
return obj;
}
void myQueuePush(MyQueue* obj, int x)
{
StackPush(&obj->stack1,x);
}
int myQueuePop(MyQueue* obj)
{
//栈一不是空,栈二是空
if(!StackEmpty(&obj->stack1)&&StackEmpty(&obj->stack2))
{
//将数据移到栈二
while(!StackEmpty(&obj->stack1))
{
StackPush(&obj->stack2,FindTop(&obj->stack1));
StackPop(&obj->stack1);
}
int ret=FindTop(&obj->stack2);
StackPop(&obj->stack2);
return ret;
}
//栈二有数据,直接pop
else
{
int ret=FindTop(&obj->stack2);
StackPop(&obj->stack2);
return ret;
}
}
int myQueuePeek(MyQueue* obj)
{
//栈二没有数据
if(StackEmpty(&obj->stack2))
{
//将栈一的数据移到栈二
while(!StackEmpty(&obj->stack1))
{
StackPush(&obj->stack2,FindTop(&obj->stack1));
StackPop(&obj->stack1);
}
}
//返回栈顶数据
return FindTop(&obj->stack2);
}
bool myQueueEmpty(MyQueue* obj)
{
return StackEmpty(&obj->stack1)&&StackEmpty(&obj->stack2);
}
void myQueueFree(MyQueue* obj)
{
StackDestroy(&obj->stack1);
StackDestroy(&obj->stack2);
free(obj);
}
代码虽然看着很长,但是其中三分之二都是之前写过的,这里只是拿来运用而已。下一题也是如此。
2. 用队列实现栈(OJ链接)
题目描述:请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。
假设入队数据1,2,3,4,5由于需要实现栈,那么出数据的顺序需要是5,4,3,2,1,效仿上一题,将数据倒入到另一个队列后,发现再出数据还是1,2,3,4,5,因此这个方法不适用了。
需要出的数据是5,所以可以考虑把1,2,3,4倒入到另一个队列,再把5出出去。把1,2,3倒回来,把4再出出去,循环就可以实现出数据的顺序为5,4,3,2,1了
过程如图所示
最终的数据序列就是5,4,3,2,1
push数据时,需要往非空的队列内push,需要后进先出。
pop数据时需要将非空队列的前n-1个数据入到空队列里(假设非空队列有n个数据),再pop最后一个数据。
top:栈顶数据就是非空队列的队尾
empty:两个队列都为空,则栈为空
完整代码如下文章来源:https://www.toymoban.com/news/detail-848031.html
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq,QDataType x);
void QueuePop(Queue* pq);
int QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
//初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
//销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
//队尾入队
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
//创建新节点
QNode* newNode = (QNode*)malloc(sizeof(QNode));
if (newNode == NULL)
{
return;
}
newNode->val = x;
newNode->next = NULL;
//队列为空
if (pq->head == NULL)
{
pq->head = 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* cur = pq->head->next; //保留第二个结点
free(pq->head);
pq->head = cur;
}
pq->size--;
}
//队列大小
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
//队头元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->val;
}
//队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->val;
}
//判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return 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->q2,x);
}
else
{
QueuePush(&obj->q1,x);
}
}
int myStackPop(MyStack* obj)
{
//找到空的队列
Queue* Empty=&obj->q1;
Queue* NotEmpty=&obj->q2;
if(!QueueEmpty(&obj->q1))
{
Empty=&obj->q2;
NotEmpty=&obj->q1;
}
//将非空队列前n-1个数据导入到空队列
while(QueueSize(NotEmpty)>1)
{
QueuePush(Empty,QueueFront(NotEmpty));
QueuePop(NotEmpty);
}
//pop掉最后一个
int popData=QueueFront(NotEmpty);
QueuePop(NotEmpty);
return popData;
}
int myStackTop(MyStack* obj)
{
//栈顶数据就是非空队列的最后一个数据
if(QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q2);
}
else
{
return QueueBack(&obj->q1);
}
}
bool myStackEmpty(MyStack* obj)
{
return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj)
{
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}
同样,三分之二的代码是之前写过的,这里只需要拷贝过来使用即可。
运行结果如下图
3. 设计循环队列(OJ链接)
题目描述:循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
你的实现应该支持如下操作:
MyCircularQueue(k): 构造器,设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空,返回 -1 。
Rear: 获取队尾元素。如果队列为空,返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
假设k等于5,即队列的长度等于5,最多存五个数据。
这里采用数组来实现循环队列。
定义的结构体类型如下
typedef struct {
int* a; //数组
int front; //指向队头
int tail; //指向队尾下一个位置
int k; //队列元素个数
} MyCircularQueue;
开辟k个空间会有上述的歧义,所以选择多开一个空间,即开辟k+1个空间,那么队列为空时是front=tail
将上面两种情况综合,队列为满时判断条件是 ( tail + 1 ) % ( k + 1 ) = front;
出队和入队也需要注意下标的回绕,也就是求余操作,也可以使用判断语句。
完整代码如下
typedef struct {
int* a; //数组
int front; //指向队头
int tail; //指向队尾下一个位置
int k; //队列元素个数
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a=(int*)malloc(sizeof(int)*(k+1));
obj->front=obj->tail=0;
obj->k=k;
return obj;
}
//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front==obj->tail;
}
//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->tail+1)%(obj->k+1)==obj->front;
}
//入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
//队列满了
if(myCircularQueueIsFull(obj))
{
return false;
}
//入队
obj->a[obj->tail++]=value;
//下标回绕
if(obj->tail==obj->k+1)
{
obj->tail=0;
}
return true;
}
//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
//队列为空
if(myCircularQueueIsEmpty(obj))
{
return false;
}
//出队
obj->front++;
//下标回绕
if(obj->front==obj->k+1)
{
obj->front=0;
}
return true;
}
//队头元素
int myCircularQueueFront(MyCircularQueue* obj) {
//空队列返回-1
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->a[obj->front];
}
//队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
//空队列返回-1
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
//返回最后一个值
if(obj->tail==0)
{
return obj->a[obj->k];
}
return obj->a[obj->tail-1];
}
//释放空间
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
关于栈和队列的题目,就写到这里了。文章来源地址https://www.toymoban.com/news/detail-848031.html
到了这里,关于数据结构OJ题——栈和队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!