C语言用栈模拟实现队列问题详解-C/C++开发

本片文章带你分析如何用两个栈，并且只使用栈的基本功能来模拟实现队列，其中同样只实现队列的基本功能，感兴趣的朋友来看看吧

题目描述

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

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

题目链接

用栈实现队列

思路分析

题目的意思是要用两个栈来模拟实现一个队列。仅可以用栈的基本功能实现队列的基本功能。所以需要创建两个栈。所以这两个栈st1，st2可用一个结构体包含。本质就是用两个后进先出的栈，来模拟一个先进先出的队列。

思路：

1.st2这个栈用来压栈，st1的作用：把st2的所有值压到st1中，然后经过st1出栈。这样就达到了队列先进先出的性质。

2.st2一直用来压栈。如果st1为空则将st2里面的值全都转移到st1，如果st1不为空，则继续出栈，知道st1为空为止。

代码实现

ypedef char 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);
//判断栈是否为空
bool StackEmpty(ST* ps);
//得到栈的长度
int StackSize(ST* ps);


//初始化结构体
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
//销毁结构体
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;


}
//压栈
void StackPush(ST* ps, STDataType x)
{

	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* new = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (new == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = new;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}
STDataType StackTop(ST* ps)
{
	assert(ps);
    assert(ps->top>0);
	return ps->a[ps->top-1];
}
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
//得到栈的长度
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}



//创建了两个栈
typedef struct
 {
    ST st1;
    ST st2;

} MyQueue;

//对两个栈进行初始化。
MyQueue* myQueueCreate() 
{
    MyQueue* newQueue = (MyQueue*)malloc(sizeof(MyQueue));
    assert(newQueue);
    StackInit(&newQueue->st1);
    StackInit(&newQueue->st2);

    return newQueue;

}

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

}

int myQueuePop(MyQueue* obj)
 {
     assert(obj);
     if(StackEmpty(&obj->st1))
     {
        while(!StackEmpty(&obj->st2))
        {
          StackPush(&obj->st1,  StackTop(&obj->st2));
            StackPop(&obj->st2);
        }
     }
        int top = 0;
     if(!StackEmpty(&obj->st1))
     {
         top = StackTop(&obj->st1);
         StackPop(&obj->st1);
     }    
    return top;
}

int myQueuePeek(MyQueue* obj) 
{
   assert(obj);
     if(StackEmpty(&obj->st1))
     {
        while(!StackEmpty(&obj->st2))
        {
          StackPush(&obj->st1,  StackTop(&obj->st2));
            StackPop(&obj->st2);
        }
     }
 
     if(!StackEmpty(&obj->st1))
     {
         return StackTop(&obj->st1);
     }
     return 0;
}

bool myQueueEmpty(MyQueue* obj)
{
    return StackEmpty(&obj->st1) && StackEmpty(&obj->st2);
}

void myQueueFree(MyQueue* obj) 
{
    StackDestroy(&obj->st1);
    StackDestroy(&obj->st2);
    free(obj);
}

到此这篇关于C语言用栈模拟实现队列问题详解的文章就介绍到这了,更多相关C语言栈实现队列内容请搜索编程学习网以前的文章希望大家以后多多支持编程学习网！