使用两个栈实现队列

一、栈和队列的基本特点

栈的特点是后进先出,而队列的特点是先进先出。
使用两个栈实现队列,必须具备队列的先进先出的功能。

举个例子:

向其中一个栈中放入4个元素,那么按照队列的特点,出队时是1先出队,所以需要把栈的所有元素全部出栈转移到空栈中。

再逐一出元素。

假如出栈一次后,又需要入栈,如下图:

则需要把元素存入空栈中,出栈的时候就出右边的非空栈。
出完右边的非空栈后,假如还想出栈,应该出的是5,那么就把左边的元素导入到右边的空栈,再出栈。

二、请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作 (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,和 isempty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque (双端队列) 来模拟一个栈,只要是标准的栈操作即可。

三、基本接口函数的实现

1.栈的接口

typedef int STDataType;

//采用顺序表来实现栈和队列
//采用链表形式来实现也可以,不过更加推荐顺序表,顺序表
//最大的优点就是支持随机访问

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void StackInit(ST* ps);
void StackDestroy(ST* ps);

void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);//取栈顶数据
STDataType StackTop(ST* ps);
int StackSize(ST* ps);
bool StackEmpty(ST* ps); //也可以用int作为类型返回值

void StackPrint(const ST *ps);

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
	//top也可以给-1,给0的意思是,先给值,再++。---指向栈顶数据的下一个
	//top给-1是先++再给值。---指向栈顶数据。
}

void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)//空间不足,增容
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newcapacity);
		//当ps->a 为NULL时,realloc相当于malloc。不用分类讨论ps->a是否为空
		assert(tmp != NULL);

		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;

}
void StackPop(ST* ps)//取栈顶数据
{
	assert(ps);
	//assert(ps->top > 0);
	assert(!StackEmpty(ps));//也可以这样写
	ps->top--;
	//但是这里有问题,top会减到小于0,所以需要断言top要>0
}

//取栈顶数据
STDataType StackTop(ST* ps)
{
	assert(ps);
	//这里也需要给定,top必须大于0,
	assert(ps->top > 0);
	return ps->a[ps->top - 1];//顺序表相当于数组,下标从0开始,并且top也是从0开始的,所以需要-1
}

int StackSize(ST* ps)//返回栈的元素个数
{
	assert(ps);
	return ps->top;
}

bool StackEmpty(ST* ps)//判断栈内是否还有元素
{
	assert(ps);
	//if (ps->top == 0)
	//{
	//	return true;
	//}
	//else
	//{
	//	return false;
	//}
	return ps->top == 0;
	//表达式为真,返回逻辑真,为假,返回逻辑假
}

void StackPrint(const ST*ps)//栈要保证后进先出。
{
	assert(ps);
	for (int i = ps->top-1; i>=0; --i)
	{
		printf("%d ",ps->a[i]);
	}
	printf("\n");
}

2.创建队列骨架

typedef struct {
    ST pushST;
    ST popST;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue*q = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&q->pushST);
    StackInit(&q->popST);

    return q;
}

这里可以细致地将两个栈分为入数据栈(pushST)和出数据栈(popST),便于操作。

3.入队操作

void myQueuePush(MyQueue* obj, int x)
{
    StackPush(&obj->pushST,x);
}

4.取出队列元素

int myQueuePop(MyQueue* obj) 
{
    //应该先要判断popST中是否有元素,如果有元素,那就直接pop掉
    //popST中的元素,如果没有元素,先全部导入进去,然后再pop
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    int top = StackTop(&obj->popST);
    StackPop(&obj->popST);
    return top;
}

注意,取出队列元素时,先判断popST栈是否为空,如果不为空,直接在这个栈中出元素。
如果为空,先将pushST栈的元素导入到popST栈,再从popST栈出元素

5.返回队首元素

//返回队列开头的元素
int myQueuePeek(MyQueue* obj) 
{
    //如果popST还有元素,则直接在这里返回,如果没有元素,则应该先把pushST的元素全部导入PopST,再取栈顶元素
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    return StackTop(&obj->popST);
}

6.判断队列是否为空

bool myQueueEmpty(MyQueue* obj) 
{
    return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}

7.销毁队列

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->pushST);
    StackDestroy(&obj->popST);
    free(obj);
}

先释放两个栈,再释放这两个栈所在的结构体。

关于Zeno Chen

本人涉及的领域较多,杂而不精 程序设计语言: Perl, Java, PHP, Python; 数据库系统: MySQL,Oracle; 偶尔做做电路板的开发,主攻STM32单片机
此条目发表在C/C++分类目录。将固定链接加入收藏夹。