算法 [LeetCode]-225. 用队列实现栈-232. 用栈实现队列

目录

225. 用队列实现栈

题目

思路

 代码

232. 用栈实现队列

题目

 思路

代码

225. 用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）https://leetcode.cn/problems/implement-stack-using-queues/description/

题目

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

示例：

思路

两个队列，每次要删除数据时，把不删除的数据先导到另一个队列，留下的数据刚好从队头开始删除。。入队列时，入不为空的队列。出队列时，不为空队列的前N-1个数据倒入空队列中，剩下的就在队头，方便删除。

图示：

 代码

//链式结构：表示队列

typedef int QDataType;

typedef struct QueueNode

{

struct QueueNode* next;

QDataType data;

}QNode;

//队列的结构

typedef struct Queue

{

QNode* head;

QNode* tail;

int size;

}Que;

//初始化队列

void QueueInit(Que* pq);

//销毁队列

void QueueDestroy(Que* pq);

//队尾入队列

void QueuePush(Que* pq, QDataType x);

//队头出队列

void QueuePop(Que* pq);

//获取队列队头元素

QDataType QueueFront(Que* pq);

//获取队列队尾元素

QDataType QueueBack(Que* pq);

//检测队列是否为空，如果为空返回非零结果，如果非空返回0

bool QueueEmpty(Que* pq);

//检测队列中有效元素个数

int QueueSize(Que* pq);

void QueueInit(Que* pq)

{

assert(pq);

pq->head = pq->tail = NULL;

pq->size = 0;

}

void QueueDestroy(Que* 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(Que* pq, QDataType x)

{

assert(pq);

QNode* newnode = (QNode*)malloc(sizeof(QNode));

if (newnode == NULL)

{

perror("malloc fail");

exit(-1);

}

newnode->data = x;

newnode->next = NULL;

if (pq->tail == NULL)

{

pq->head = pq->tail = newnode;

}

else

{

pq->tail->next = newnode;

pq->tail = newnode;

}

pq->size++;

}

void QueuePop(Que* pq)

{

assert(pq);

assert(!QueueEmpty(pq));

if (pq->head->next == NULL)

{

free(pq->head);

pq->head = pq->tail = NULL;

}

else

{

QNode* next = pq->head->next;

free(pq->head);

pq->head = next;

}

pq->size--;

}

QDataType QueueFront(Que* pq)

{

assert(pq);

assert(!QueueEmpty(pq));

return pq->head->data;

}

QDataType QueueBack(Que* pq)

{

assert(pq);

assert(!QueueEmpty(pq));

return pq->tail->data;

}

bool QueueEmpty(Que* pq)

{

assert(pq);

return pq->head == NULL;

}

int QueueSize(Que* pq)

{

assert(pq);

return pq->size;

}

typedef struct {

Que q1;

Que q2;

} MyStack;

MyStack* myStackCreate() {

MyStack* pst=(MyStack*)malloc(sizeof(MyStack));

QueueInit(&pst->q1);

QueueInit(&pst->q2);

return pst;

}

void myStackPush(MyStack* obj, int x) {

if(!QueueEmpty(&obj->q1))

{

QueuePush(&obj->q1,x);

}

else

{

QueuePush(&obj->q2,x);

}

}

int myStackPop(MyStack* obj) {

Que* empty=&obj->q1;

Que* nonEmpty=&obj->q2;

if(!QueueEmpty(&obj->q1))

{

nonEmpty=&obj->q1;

empty=&obj->q2;

}

while(QueueSize(nonEmpty)>1)

{

QueuePush(empty,QueueFront(nonEmpty));

QueuePop(nonEmpty);

}

int top=QueueFront(nonEmpty);

QueuePop(nonEmpty);

return top;

}

int myStackTop(MyStack* obj) {

if(!QueueEmpty(&obj->q1))

{

return QueueBack(&obj->q1);

}

else

{

return QueueBack(&obj->q2);

}

}

bool myStackEmpty(MyStack* obj) {

return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);

}

void myStackFree(MyStack* obj) {

QueueDestroy(&obj->q1);

QueueDestroy(&obj->q2);

free(obj);

}

232. 用栈实现队列

232. 用栈实现队列 - 力扣（LeetCode）https://leetcode.cn/problems/implement-queue-using-stacks/description/

题目

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空，返回 true ；否则，返回 false

示例：

 思路

两个栈分别为pushst和popst，pushst负责插入，popst负责删除。插入时往pushst插入。要删除时，先将pushst中的元素一个一个移出往popst中导入，再从栈顶删除，实现先入先出。再要插入时，往pushst插入，再要删除时，先检测popst里面是否还有元素，还有就等popst里面删完了再把pushst导入popst继续删。

popst的栈顶相当于队头，pushst的栈顶相当于队尾。

图示：

代码

#include

#include

#include

#include

#include

// 下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈

//静态栈

typedef int STDataType;

#define N 10

typedef struct Stack

{

STDataType _a[N];

int _top; // 栈顶

}Stack;

//动态栈 支持动态增长的栈

typedef int STDataType;

typedef struct stack

{

STDataType* a;

int top;//栈顶

int capacity;//容量

}ST;

//初始化栈

void STInit(ST* ps);

//销毁栈

void STDestroy(ST* ps);

//入栈

void STPush(ST* ps, STDataType x);

//出栈

void STPop(ST* ps);

//获取栈顶元素

STDataType Sttop(ST* ps);

//获取栈中有效元素

int STSize(ST* ps);

//检测栈中是否为空

bool STEmpty(ST* ps);

//̬ջʼ

void STInit(ST* ps)

{

assert(ps);

ps->a = NULL;

ps->capacity = 0;//

ps->top = 0;//ջ

}

//

void STDestroy(ST* ps)

{

assert(ps);

free(ps->a);

ps->a = NULL;

ps->top = ps->capacity = 0;

}

//

void STPush(ST* ps, STDataType x)

{

assert(ps);

if (ps->top == ps->capacity)

{

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] = x;

ps->top++;

}

//ɾ

void STPop(ST* ps)//, STDataType x

{

assert(ps);

assert(ps->top > 0);

--ps->top;

}

STDataType STTop(ST* ps)

{

assert(ps);

assert(ps->top > 0);

return ps->a[ps->top - 1];

}

int STSize(ST* ps)

{

assert(ps);

return ps->top;

}

bool STEmpty(ST* ps)

{

assert(ps);

return ps->top == 0;

}

typedef struct {

ST pushst;

ST popst;

} MyQueue;

MyQueue* myQueueCreate() {

MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));

STInit(&obj->pushst);

STInit(&obj->popst);

return obj;

}

void myQueuePush(MyQueue* obj, int x) {

STPush(&obj->pushst,x);//直接往pushst插入

}

int myQueuePop(MyQueue* obj) {

int front=myQueuePeek(obj);

STPop(&obj->popst);

return front;

}

int myQueuePeek(MyQueue* obj) {

if(STEmpty(&obj->popst))

{

//倒数据

while(!STEmpty(&obj->pushst))

{

STPush(&obj->popst,STTop(&obj->pushst));

STPop(&obj->pushst);

}

}

return STTop(&obj->popst);

}

bool myQueueEmpty(MyQueue* obj) {

return STEmpty(&obj->popst)&&STEmpty(&obj->pushst);

}

void myQueueFree(MyQueue* obj) {

STDestroy(&obj->popst);

STDestroy(&obj->pushst);

free(obj);

}

好文推荐

 您阅读本篇文章共花了：