文章目錄
- 一：思路
- 二：實作
- （1）結構體定義
- （2）初始化和銷毀
- （3）進“堆疊”
- （4）出“堆疊”
- 三：代碼
一：思路
二：實作
（1）結構體定義
（2）初始化和銷毀
注意：在測驗檔案外新建一個Mystack結構體時，不能只有一句Mystack ms，因為使用佇列實作堆疊，那么該堆疊的底層是佇列，所以必須同時要創建佇列結構體，然后進行賦值才可以
（3）進“堆疊”
注意：進堆疊和出堆疊本質是在操作佇列，所以這里僅僅使用的佇列操作的介面，如果想要了解佇列的出隊和入隊操作，請看：
資料結構-線性表之堆疊和佇列
（4）出“堆疊”
三：代碼
QueueToStack.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int DataType;
typedef struct QNode
{
DataType _val;
struct QNode* _next;
}QNode;
typedef struct Queue
{
QNode* _front;
QNode* _rear;
}Queue;
typedef struct MyStack
{
Queue* _q1;//儲備元素的堆疊
Queue* _q2;//進元素的堆疊
}MyStack;
void MyStackInit(MyStack* ps);
void MyStackPush(MyStack* ps, DataType x);//進堆疊
DataType MystackPop(MyStack* ps);//出堆疊
QueueToStack.c
#include "QueueToStack.h"
void MyStackInit(MyStack* ps)
{
assert(ps);
ps->_q1->_front = NULL;
ps->_q1->_rear = NULL;
ps->_q2->_front = NULL;
ps->_q2->_rear = NULL;
printf("初始化成功\n");
}
void MystackDestory(MyStack* ps)
{
assert(ps);
//釋放儲存堆疊
QNode* cur = ps->_q1->_front;
QNode* pre;
while (cur)
{
pre = cur;
cur = cur->_next;
free(pre);
}
free(ps);
}
//入隊
void QueuePush(Queue* pq, DataType x)
{
assert(pq);
QNode* NewNode = (QNode*)malloc(sizeof(QNode));
NewNode->_val = x;
NewNode->_next = NULL;
if (pq->_rear == NULL)
{
pq->_rear = NewNode;
pq->_front = NewNode;
}
else
{
pq->_rear->_next = NewNode;
pq->_rear = NewNode;
}
}//
//出隊
DataType QueuePop(Queue* pq)
{
assert(pq);
if (pq->_front == pq->_rear)
{
DataType rec = pq->_front->_val;
free(pq->_rear);
pq->_rear = NULL;
pq->_front = NULL;
return rec;
}
else
{
QNode* cur = pq->_front;
pq->_front = pq->_front->_next;
return cur->_val;
free(cur);
}
}
void MyStackPush(MyStack* ps,DataType x)
{
//如果佇列1不空就先把佇列1中的元素出佇列然后進入佇列2
if (ps->_q1->_front != NULL)
{
DataType save = QueuePop(ps->_q1);//出佇列1
QueuePush(ps->_q2,save);//進佇列2
}
QueuePush(ps->_q2, x);//而后在正常進“堆疊”
}
DataType MystackPop(MyStack* ps)
{
if (ps->_q2->_front == NULL && ps->_q1->_front !=NULL)
//如果佇列2為空，佇列1不空，將隊1所有元素出隊1，依次進隊2
{
while (ps->_q1->_front)
{
DataType save = QueuePop(ps->_q1);
QueuePush(ps->_q2, save);
}
}
//出“堆疊”時，第一個元素就是佇列2的尾元素
while(ps->_q2->_front!=ps->_q2->_rear)//出隊2直到佇列2剩余最后一個元素
{
DataType save = QueuePop(ps->_q2);
QueuePush(ps->_q1, save);
}
DataType rec = QueuePop(ps->_q2);
return rec;
}
test.c
#include "QueueToStack.h"
void test()
{
MyStack ms;
Queue q1;
Queue q2;
ms._q1 = &q1;
ms._q2 = &q2;
MyStackInit(&ms);
MyStackPush(&ms, 1);
MyStackPush(&ms, 2);
MyStackPush(&ms, 3);
MyStackPush(&ms, 4);
MyStackPush(&ms, 5);
printf("%d ", MystackPop(&ms));
printf("%d ", MystackPop(&ms));
printf("%d ", MystackPop(&ms));
printf("%d ", MystackPop(&ms));
printf("%d ", MystackPop(&ms));
}
int main()
{
test();
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/253505.html
標籤：其他