C语言之数据结构之栈和队列的运用

2024-06-04 1077阅读

目录

    • 1. 用队列实现栈
      • 1.1 思路讲解
      • 1.2 代码实现
      • 2. 用栈实现队列
        • 1.1 思路讲解
        • 1.2 代码实现
        • 总结

          C语言之数据结构之栈和队列的运用 第1张

          •͈ᴗ•͈ 个人主页：御翮

          •͈ᴗ•͈ 个人专栏：C语言数据结构

          •͈ᴗ•͈ 欢迎大家关注和订阅!!!

          C语言之数据结构之栈和队列的运用 第2张

          1. 用队列实现栈

          题目描述：

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

          实现 MyStack 类：

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

            注意：

            • 你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
            • 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

              示例：

              输入：

              [“MyStack”, “push”, “push”, “top”, “pop”, “empty”]

              [ [ ], [1], [2], [ ], [ ], [ ] ]

              输出：

              [ null, null, null, 2, 2, false ]

              解释：

              MyStack myStack = new MyStack();

              myStack.push(1);

              myStack.push(2);

              myStack.top(); // 返回 2

              myStack.pop(); // 返回 2

              myStack.empty(); // 返回 False

              提示：

              • 1 struct QNode* next; QDatatype data; }QNode; typedef struct Queue { QNode* head; QNode* tail; }Queue; void Init_Queue(Queue* ptr) { assert(ptr); ptr-head = ptr-tail = NULL; } void Destroy_Queue(Queue* ptr) { assert(ptr); QNode* cur = ptr->head; while (ptr->head != NULL) { cur = ptr->head; ptr->head = ptr->head->next; free(cur); } ptr->tail = NULL; } QNode* Buy_Node() { QNode* tmp = (QNode*)malloc(sizeof(QNode)); return tmp; } void Print_Queue(Queue* ptr) { assert(ptr); QNode* cur = ptr->head; while (cur != NULL) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); } void Push_Queue(Queue* ptr, QDatatype val) { assert(ptr); QNode* newnode = Buy_Node(); if (newnode == NULL) { perror("Push_Queue\n"); exit(1); } newnode->data = val; newnode->next = NULL; if (ptr->head == NULL) { ptr->head = ptr->tail = newnode; } else { ptr->tail->next = newnode; ptr->tail = newnode; } } int Queue_Size(Queue* ptr) { assert(ptr); int count = 0; QNode* cur = ptr->head; while (cur != NULL) { cur = cur->next; count++; } return count; } void Pop_Queue(Queue* ptr) { assert(ptr); if (ptr->head == NULL) { printf("队列中没有元素\n"); return; } if (Queue_Size(ptr) == 1) { free(ptr->tail);//如果删完了但是没有将tail置为NULL，则case 5 会发生错误，显示队尾元素随机值。 ptr->tail = NULL; ptr->head = NULL; return; } QNode* pop = ptr->head; ptr->head = ptr->head->next; free(pop); } QDatatype Queue_Front(Queue* ptr) { assert(ptr); return ptr->head->data; } QDatatype Queue_Back(Queue* ptr) { assert(ptr); return ptr->tail->data; } int Check_Empty(Queue* ptr) { assert(ptr); if (Queue_Size(ptr)) return 0; else return 1; } //以上是自己创建的队列，因为c语言没有队列

                队列实现栈代码：

                typedef struct 
{
	Queue q1;
	Queue q2;
} MyStack;
// 创建栈
MyStack* myStackCreate() 
{
	MyStack* tmp = (MyStack*)malloc(sizeof(MyStack));
	if (tmp == NULL) // 开辟空间可能失败，失败则终止程序
	{
		printf("Fail: myStackCreate\n");
		exit(1);
	}
	Init_Queue(&tmp->q1); // 我们的栈由两个队列组成，所以初始化要调用队列的初始化
	Init_Queue(&tmp->q2);
	return tmp;
}
// 数据入栈
void myStackPush(MyStack* obj, int x) 
{
	if (Check_Empty(&obj->q1)) // 哪个队列有元素就往哪放，两个都没有就默认放q2，保证只有一个队列有数据
	{
		Push_Queue(&obj->q2, x);
	}
	else
		Push_Queue(&obj->q1, x);
}
// 数据出栈
int myStackPop(MyStack* obj) 
{
	//题目保证每次调用pop时栈都不为空，不用考虑为空时的pop
	if (Check_Empty(&obj->q1)) // 哪个队列有数据就将n-1个数据放到另一个队列，剩下的最后一个元素就是栈顶元素，直接出栈
	{
		int sum = Queue_Size(&obj->q2); // 获取队列元素个数n
		for (int i = 0; i q1, Queue_Front(&obj->q2));
			Pop_Queue(&obj->q2);
		}
		QDatatype tmp = Queue_Front(&obj->q2); // 保存最后一个元素的值，再pop，因为要返回出栈元素的值
		Pop_Queue(&obj->q2);
		return tmp;
	}
	else
	{
		int sum = Queue_Size(&obj->q1);
		for (int j = 0; j q2, Queue_Front(&obj->q1));
			Pop_Queue(&obj->q1);
		}
		QDatatype tmp = Queue_Front(&obj->q1);
		Pop_Queue(&obj->q1);
		return tmp;
	}
}
// 获取栈顶元素
int myStackTop(MyStack* obj) 
{
	//题目保证每次调用top时栈都不为空，不用考虑为空时的top
	if (Check_Empty(&obj->q1)) // 因为我们前面入栈时保证了只有一个队列有数据，所以队尾元素就是栈顶元素
	{
		return Queue_Back(&obj->q2);
	}
	else
		return Queue_Back(&obj->q1);
}
// 判断栈是否为空
bool myStackEmpty(MyStack* obj) 
{
	if (Check_Empty(&obj->q1) && Check_Empty(&obj->q2)) // 栈由两个队列组成，两个队列都为空栈就为空
	{
		return true;
	}
	else
		return false;
}
// 销毁栈
void myStackFree(MyStack* obj) 
{
	Destroy_Queue(&obj->q1); // 消耗栈要销毁里面的两个队列
	Destroy_Queue(&obj->q2);
	free(obj);
}

                2. 用栈实现队列

                题目描述：

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

                    示例 ：

                    输入：

                    [“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]

                    [ [ ], [1], [2], [ ], [ ], [ ] ]

                    输出：

                    [ null, null, null, 1, 1, false ]

                    解释：

                    MyQueue myQueue = new MyQueue();

                    myQueue.push(1); // queue is: [1]

                    myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)

                    myQueue.peek(); // return 1

                    myQueue.pop(); // return 1, queue is [2]

                    myQueue.empty(); // return false

                    提示：

                    1 STDataType* stack; int size; int capacity; }Stack; void Init_Stack(Stack* ptr) { assert(ptr); STDataType* tmp = (STDataType*)malloc(3 * sizeof(STDataType)); if (tmp == NULL) { perror("Init_Stack\n"); exit(1); } ptr-stack = tmp; ptr-capacity = 3; ptr->size = 0; } void Destroy_Stack(Stack* ptr) { assert(ptr); free(ptr->stack); ptr->stack = NULL; } void Check_Capacity(Stack* ptr) { assert(ptr); if (ptr->size == ptr->capacity) { STDataType* tmp = (STDataType*)realloc(ptr->stack, 2 * ptr->capacity * sizeof(STDataType)); if (tmp == NULL) { perror("Check_Capacity\n"); exit(1); } ptr->stack = tmp; ptr->capacity *= 2; } } void Print_Stack(Stack* ptr) { assert(ptr); for (int i = 0; i size; i++) { printf("%d ", ptr->stack[i]); } printf("\n"); } void Push_Stack(Stack* ptr, STDataType val) { assert(ptr); Check_Capacity(ptr); ptr->stack[ptr->size] = val; ptr->size++; } void Pop_Stack(Stack* ptr) { assert(ptr); ptr->size--; } STDataType Top_Stack(Stack* ptr) { assert(ptr); return ptr->stack[ptr->size - 1]; } int Size_Stack(Stack* ptr) { assert(ptr); return ptr->size; } int Empty_Stack(Stack* ptr) { assert(ptr); if (ptr->size == 0) return 1; else return 0; } typedef struct { Stack push; Stack pop; } MyQueue;

                    栈实现队列代码：

                    // 创建队列
MyQueue* myQueueCreate() 
{
	MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));
	if (queue == NULL) // 开辟空间有可能失败，失败则终止程序
	{
		perror("myQueueCreate");
		exit(1);
	}
	Init_Stack(&queue->push); // 初始化队列要初始化里面的栈
	Init_Stack(&queue->pop);
	return queue;
}
// 数据入队列
void myQueuePush(MyQueue* obj, int x) 
{
	Push_Stack(&obj->push, x); // 数据只入push栈
}
// 数据出队列
int myQueuePop(MyQueue* obj) 
{
	if (Empty_Stack(&obj->pop)) // 如果pop栈为空，就要从push栈里面把数据拿过来
	{
		int sum = Size_Stack(&obj->push); // 获取push中的元素个数n
		for (int i = 0; i pop, Top_Stack(&obj->push));
			Pop_Stack(&obj->push);
		}
	}
	int ret = Top_Stack(&obj->pop); // 先储存队头元素再出队列，因为题目要返回队头元素
	Pop_Stack(&obj->pop);
	return ret;
}
// 获取队头元素
int myQueuePeek(MyQueue* obj) 
{
	if (Empty_Stack(&obj->pop)) // 如果pop栈为空，那就把push栈里面的元素拿过来
	{
		int sum = Size_Stack(&obj->push);
		for (int i = 0; i pop, Top_Stack(&obj->push));
			Pop_Stack(&obj->push);
		}
	}
	return Top_Stack(&obj->pop); // 队头元素就是pop栈中的栈顶元素，因为pop栈内的元素是push栈内的元素顺序颠倒过来
}
// 判断队列是否为空
bool myQueueEmpty(MyQueue* obj) 
{
	if (Empty_Stack(&obj->push) && Empty_Stack(&obj->pop)) // 两个栈都为空，队列就为空
	{
		return true;
	}
	else
		return false;
}
// 销毁队列
void myQueueFree(MyQueue* obj) 
{
	Destroy_Stack(&obj->push);  // 销毁队列要销毁里面的两个栈
	Destroy_Stack(&obj->pop);
	free(obj);					// 不要忘记释放这个空间
}

                    总结

                    两个队列实现栈需要来回颠倒。

                    两个栈实现队列要确定一个push和一个pop。


相关阅读：

1、在 Linux 中创建属于 root 组（GID 0）的用户需要谨慎操作，因为 root 组通常拥有与 root 用户相似的高权限。以下是具体步骤和注意事项，如何在Linux中安全创建root组用户？关键步骤与风险警示！，如何在Linux中安全创建root组用户？关键步骤与风险警示！

2、VPS桌面关闭操作指南，一步步轻松解决困扰

3、独家揭秘，VPS在Minecraft世界中的使用秘籍！

4、亚马逊VPS SMTP使用指南与问题解析

5、VPS自动密码重置，保障安全，无忧使用

    高速稳定云服务器25元起
    免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!

    相关阅读

    目录[+]