#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#define Size 6
typedef struct SqNode//隊列結點
{
int data;
struct SqNode* next;
}LinkNode;
typedef struct SqQueue//隊列
{
LinkNode* front, * rear; //頭指針和尾指針
}LinkQueue;
typedef struct LinkStack//棧
{
int data;
struct LinkStack* next;
}LinkStack;
void InitQueue(LinkQueue* Q)//假設用帶頭結點的鏈表來表示隊列
{
Q->front = Q->rear = (LinkNode*)malloc(sizeof(LinkNode));
if (Q->front == NULL)//分配失敗
return;
Q->rear->next = NULL;
return;
}
void InitStack(LinkStack** S)//用不帶頭結點的鏈表來表示棧，&S表示當前是指向鏈表指針的指針，所以要用形參要用二級指針
{
*S = NULL;
return;
}
bool EnQueue(LinkQueue* Q, int x)//入隊
{
//無需判斷滿隊
LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
if (s == NULL)//分配失敗
return false;
s->data = x;
s->next = NULL;
Q->rear->next = s;
Q->rear = s;
return true;
}
bool Push(LinkStack** S, int x)//進棧
{
//無需判斷是否滿棧
//第一次入棧
if ((*S) == NULL)
{
LinkStack* p = (LinkStack*)malloc(sizeof(LinkStack));
if (p == NULL)//分配失敗
return false;
p->data = x;
p->next = NULL;
(*S) = p;
}
//后續入棧
else?
{
LinkStack* q = (LinkStack*)malloc(sizeof(LinkStack));
if (q == NULL)//分配失敗
return false;
q->data = x;
q->next = (*S);
(*S) = q;
}
return true;
}
int* DeQueue(LinkQueue* Q, int* x)//出隊
{
if (Q->front == Q->rear)//空隊
return NULL;
LinkNode* p = Q->front->next;
if (p == Q->rear)//恰好有一個元素
{
*x = p->data;
Q->front->next = NULL;
free(p);
Q->rear = Q->front;
return x;
}
*x = p->data;
Q->front->next = p->next;
free(p);
return x;
}
bool PrintList(LinkQueue Q)//打印隊列
{
LinkNode* p = Q.front->next;
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
return true;
}
bool PrintStack(LinkStack* S)//打印棧
{
LinkStack* p = S;
if (p == NULL)//空棧
return false;
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
return true;
}
int main()
{
int arr[Size] = { 1,2,3,4,5,6 };//假設要輸入1,2,3,4,5,6
LinkQueue Q;//定義一個隊列
LinkStack* S;//定義一個棧
InitQueue(&Q);//初始化隊列
InitStack(&S);//初始化棧

?? ?int i;
for(i = 0;i < Size;i++)
EnQueue(&Q,arr[i]);//入隊

?? ?int* j;
for (i = 0; i < Size; i++)
{
j = DeQueue(&Q, &arr[i]);//出隊
Push(&S, *j);//進棧
}

?? ?//PrintList(Q);//隊列打印測試
PrintStack(S);//棧打印測試
return 0;
}