《手撕数据结构经典题系列》用队列实现栈

用队列实现栈

力扣链接:225. 用队列实现栈 - 力扣(LeetCode) (leetcode-cn.com)

  • 题目描述:

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

  • 实现 MyStack 类:
  1. void push(int x) 将元素 x 压入栈顶。
  2. int pop() 移除并返回栈顶元素。
  3. int top() 返回栈顶元素。
  4. boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。
  • 注意:
  1. 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
  2. 你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
  • 解题思路:
  1. 栈的特性是先入后出,而队列的特性是先入先出
  2. 先让一个队列入数据,另一个队列不入数据
  3. 出数据时,先出队列到最后一个数据,而之前的数据都入到另一个空队列
  4. 最后将队列最后一个数据给出队列
  5. 以后再入数据时,都入到有数据的队列
  6. 出数据时,都现将最后一个数据之前的数据入到另一个空队列,再将最后一个数据给出队列
  7. 总之永远保持有一个队列为空
  • 图示:

《手撕数据结构经典题系列》用队列实现栈参考代码:

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


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

void myStackPush(MyStack* obj, int x) {
    //入栈时入空队列
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
    //出栈时,先将有数据的队列出队到最后一个元素,并将数据入队到空队列,最后将最后一个数据出队达到出栈的效果
    Queue* emptyQ=&obj->q1;
    Queue* noemptyQ=&obj->q2;
    if(QueueEmpty(&obj->q2))
    {
        emptyQ=&obj->q2;
        noemptyQ=&obj->q1;
    }
    while(QueueSize(noemptyQ)>1)
    {
        QueuePush(emptyQ,QueueFront(noemptyQ));
        QueuePop(noemptyQ);
    }
    int top=QueueFront(noemptyQ);
    QueuePop(noemptyQ);
    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->q1);
    free(obj);
}

队列源码

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;

typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
	// size_t _size;
}Queue;

//void QueueInit(QueueNode** pphead, QueueNode** pptail);
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}

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

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

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->data = x;
	newnode->next = NULL;

	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

void QueuePop(Queue* pq)
{
	assert(pq);
	//if (pq->head == NULL)
	//	return;
	assert(!QueueEmpty(pq));

	QueueNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

int QueueSize(Queue* pq)
{
	assert(pq);

	int n = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		++n;
		cur = cur->next;
	}

	return n;
}

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

上一篇:更加多注释地学习视觉SLAM第九讲程序[2]


下一篇:Top K Frequent WOrds