【資料結構】棧和隊列（WD）

棧的順序存儲結構

#include <bits/stdc++.h>

using namespace std;

#define MaxSize 10 //定義棧中元素的最大個數

typedef struct
{
int data[MaxSize]; //靜态數組存放棧中元素
int top;           //棧頂指針
} SqStack;             //Sq:sequence順序

//初始化棧
void initStack(SqStack &S)
{
S.top = -1; //初始化棧頂指針
}

//判斷棧是否為空
bool stackEmpty(SqStack S)
{
if (S.top == -1)
    { //棧空
return true;
    }
else
    { //不空
return false;
    }
}

//進棧
bool push(SqStack &S, int x)
{
if (S.top == MaxSize - 1)
    { //棧滿，報錯
return false;
    }
S.top++;           //指針先加1
S.data[S.top] = x; //新元素入棧
return true;
}

//出棧
bool pop(SqStack &S, int x)
{
if (S.top == -1)
    { //棧空，報錯
return false;
    }
x = S.data[S.top]; //先出棧
S.top--;           //指針再減1
return true;
}

//讀棧頂元素
bool getTop(SqStack S, int &x)
{
if (S.top == -1)
    { //棧空，報錯
return false;
    }
x = S.data[S.top]; //x記錄棧頂元素
return true;
}

//列印
void output(SqStack S)
{
for (int i = 0; i <= S.top; i++)
    {
printf("Stack[%d]=%d\n", i, S.data[i]);
    }
printf("\n");
}

int main()
{
SqStack S; //聲明一個順序棧（配置設定空間）
initStack(S);
if (stackEmpty(S))
    {
push(S, 1);
push(S, 2);
push(S, 3);
output(S);
int x;
pop(S, x);
output(S);
getTop(S, x);
printf("%d\n", x);
    }
else
    {
printf("failure!\n");
    }
return 0;
}
      

output:

Stack[0]=1

Stack[1]=2

Stack[2]=3

2

隊列的順序存儲結構

#include <bits/stdc++.h>

using namespace std;

#define MaxSize 10 //定義隊列中元素的最大個數

typedef struct
{
int data[MaxSize]; //用靜态數組存放隊列元素
int front, rear;   //隊頭指針和隊尾指針
} SqQueue;

//初始化隊列
void initQueue(SqQueue &Q)
{
//初始時，隊頭、隊尾指針指向0
Q.front = Q.rear = 0;
}

//判斷隊列是否為空
bool QueueEmpty(SqQueue Q)
{
if (Q.rear == Q.front)
    { //隊空條件
return true;
    }
else
    {
return false;
    }
}

//入隊
bool EnQueue(SqQueue &Q, int x)
{
if ((Q.rear + 1) % MaxSize == Q.front)
    {
return false; //隊滿則報錯
    }
Q.data[Q.rear] = x;              //新元素插入隊尾
Q.rear = (Q.rear + 1) % MaxSize; //隊尾指針加1取模
return true;
}

//出隊
bool DeQueue(SqQueue &Q,int &x){
if(Q.rear==Q.front){//隊空則報錯
return false;
    }
x=Q.data[Q.front];
Q.front=(Q.front+1)%MaxSize;//隊頭指針後移
return true;
}

//獲得隊頭元素的值，用x傳回
bool GetHead(SqQueue Q,int &x){
if(Q.rear==Q.front){
return false;
    }
x=Q.data[Q.front];
return true;
}

//傳回隊列元素個數
int Count(SqQueue Q){
return (Q.rear+MaxSize-Q.front)%MaxSize; 
}

//列印
void output(SqQueue Q){
for(int i=Q.front;i!=Q.rear;i=(i+1)%MaxSize){
printf("Queue[%d]=%d\n",i,Q.data[i]);
    }
printf("\n");
}

int main()
{
SqQueue Q; //聲明一個隊列
initQueue(Q);
if (QueueEmpty(Q))
    {
EnQueue(Q,1);
EnQueue(Q,2);
EnQueue(Q,3);
output(Q);
printf("number=%d\n",Count(Q));
int x;
DeQueue(Q,x);
output(Q);
GetHead(Q,x);
printf("%d\n",x);
    }
else
    {
printf("failure!\n");
    }
return 0;
}
      

Queue[0]=1

Queue[1]=2

Queue[2]=3

number=3

隊列的鍊式存儲結構

#include <bits/stdc++.h>

using namespace std;

//鍊式隊列結點
typedef struct LinkNode
{
int data;
struct LinkNode *next;
} LinkNode;

//鍊式隊列
typedef struct
{
LinkNode *front, *rear; //隊列的隊頭和隊尾指針
} LinkQueue;

//初始化隊列(帶頭結點)
void InitQueue1(LinkQueue &Q)
{
//初始時，front、rear都指向頭結點
Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
Q.front->next = NULL;
}

//初始化隊列(不帶頭結點)
void InitQueue2(LinkQueue &Q)
{
//初始時，front、rear都指向NULL
Q.front = NULL;
Q.rear = NULL;
}

//判斷隊列是否為空(帶頭結點)
bool IsEmpty1(LinkQueue Q)
{
if (Q.rear == Q.front)
    { //隊空條件
return true;
    }
else
    {
return false;
    }
}

//判斷隊列是否為空(不帶頭結點)
bool IsEmpty2(LinkQueue Q)
{
if (Q.front == NULL)
    { //隊空條件
//也可以判斷if (Q.rear == NULL)
return true;
    }
else
    {
return false;
    }
}

//入隊(帶頭結點)
void EnQueue1(LinkQueue &Q, int x)
{
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = x;
s->next = NULL;
Q.rear->next = s; //新結點插入到rear之後
Q.rear = s;       //修改表尾指針
}

//入隊(不帶頭結點)
void EnQueue2(LinkQueue &Q, int x)
{
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = x;
s->next = NULL;
if (Q.front == NULL)
    { //在空隊列中插入第一個元素
//修改隊頭隊尾指針
Q.front = s;
Q.rear = s;
    }
else
    {
Q.rear->next = s;
Q.rear = s;
    }
}

//出隊(帶頭結點)
bool DeQueue1(LinkQueue &Q, int &x)
{
if (Q.front == Q.rear)
    { //空隊
return false;
    }
LinkNode *p = Q.front->next;
x = p->data;             //用變量x傳回隊頭元素
Q.front->next = p->next; //修改頭結點的next指針
if (Q.rear == p)
    {                     //此次是最後一個結點出隊
Q.rear = Q.front; //修改rear指針
    }
free(p); //釋放結點空間
return true;
}

//出隊(不帶頭結點)
bool DeQueue2(LinkQueue &Q, int &x)
{
if (Q.front == NULL)
    { //空隊
return false;
    }
LinkNode *p = Q.front; //p指向此次出隊的結點
x = p->data;           //用變量x傳回隊頭元素
Q.front = p->next;     //修改front指針
if (Q.rear == p)
    {                   //此次是最後一個結點出隊
Q.front = NULL; //front指向NULL
Q.rear = NULL;  //rear指向NULL
    }
free(p); //釋放結點空間
return true;
}

//列印(帶頭結點)
void output1(LinkQueue Q)
{
LinkNode *p = Q.front->next;
while (p != NULL)
    {
if (p->next != NULL)
        {
printf("%d->", p->data);
        }
else
        {
printf("%d", p->data);
        }
p = p->next;
    }
printf("\n");
}

//列印(不帶頭結點)
void output2(LinkQueue Q)
{
LinkNode *p = Q.front;
while (p != NULL)
    {
if (p->next != NULL)
        {
printf("%d->", p->data);
        }
else
        {
printf("%d", p->data);
        }
p = p->next;
    }
printf("\n");
}

int main()
{
int x;

LinkQueue Q1;
InitQueue1(Q1);
if (IsEmpty1(Q1))
    {
EnQueue1(Q1, 1);
EnQueue1(Q1, 2);
EnQueue1(Q1, 3);
output1(Q1);
DeQueue1(Q1, x);
output1(Q1);
printf("x1=%d\n", x);
    }
else
    {
printf("failure!\n");
    }

LinkQueue Q2;
InitQueue2(Q2);
if (IsEmpty2(Q2))
    {
EnQueue2(Q2, 1);
EnQueue2(Q2, 2);
EnQueue2(Q2, 3);
output2(Q2);
DeQueue2(Q2, x);
output2(Q2);
printf("x2=%d\n", x);
    }
else
    {
printf("failure!\n");
    }

return 0;
}
      

1->2->3

2->3

x1=1

x2=1