【数据结构】栈、队列和数组

栈

顺序栈

#define MaxSize 50
typedef struct
{int data[MaxSize];int top;
} SqStack;// 1.(S.top == -1)
void InitStack(SqStack &S)
{S.top = -1;
}// 2.(S.top == -1)
bool Push(SqStack &S, int x)
{if (S.top = MaxSize - 1)return false;S.data[++S.top] = x;return true;
}// 3.(S.top == -1)
bool GetTop(SqStack &S, int &x)
{if (S.top == -1)return false;x = S.data[S.top];return true;
}// 4. (S.top == -1)
bool StackEmpty(SqStack &S)
{if (S.top == -1)return true;return false;
}// 5.(S.top == -1)
bool Pop(SqStack *S, int &x)
{if (S->top == -1)return false;x = S->data[S->top--];return true;
}// // 1.(S.top == 0)
// void InitStack(SqStack &S)
// {
//     S.top = 0;
// }// // 2.(S.top == 0)
// bool Push(SqStack &S, int x)
// {
//     if (S.top = MaxSize)
//         return false;
//     S.data[S.top++] = x;
//     return true;
// }// // 3.(S.top == 0)
// bool GetTop(SqStack &S, int &x)
// {
//     if (S.top == 0)
//         return false;
//     x = S.data[S.top];
//     return true;
// }// // 4. (S.top == 0)
// bool StackEmpty(SqStack &S)
// {
//     if (S.top == 0)
//         return true;
//     return false;
// }// // 5.(S.top == 0)
// bool Pop(SqStack *S, int &x)
// {
//     if (S->top == 0)
//         return false;
//     x = S->data[--S->top];
//     return true;
// }

链栈

typedef struct LinkNode
{int data;struct LinkNode *next;
} LiStack;

共享栈

#define MaxSize 50
typedef struct
{int data[MaxSize];int top0;int top1;
} ShStack;void InitStack(ShStack &S)
{S.top0 = -1;S.top1 = MaxSize;
}

队列

循环队列

#define MaxSize 50
typedef struct
{int data[MaxSize];int front, rear;
} SqQueue;// 1.初始化
void InitQueue(SqQueue &Q)
{Q.rear = Q.front = 0;
}// 2.循环队列入队
bool EnEmmpty(SqQueue &Q, int x)
{if ((Q.rear + 1) % MaxSize == Q.front)return false;Q.data[Q.rear] = x;Q.rear = (Q.rear + 1) % MaxSize;return true;
}// 3.判断队列为空
bool isEmpty(SqQueue &Q)
{if (Q.rear == Q.front)return true;return false;
}// 4. 循环队列出队
bool DeEmpty(SqQueue &Q, int &x)
{if (Q.rear == Q.front)return false;x = Q.data[Q.front];Q.front = (Q.front + 1) % MaxSize;return true;
}// 5. 获取队头元素值
bool Gethead(SqQueue Q, int &x)
{if (Q.rear == Q.front)return false;x = Q.data[Q.front];return true;
}

带头结点的链式队列

typedef struct LinkNode
{int data;struct LinkNode *next;
} LinkNode;typedef struct
{LinkNode *front, *rear;
} LinkNode;// 带头结点的实现方式// 1.初始化
void InitQueue(LinkNode &Q)
{Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));Q.front->next = NULL;
}// 2.判断是否为空
bool isEmpty(LinkNode &Q)
{if (Q.front == Q.rear)return true;return false;
}// 3.入队
bool EnEmpty(LinkNode &Q, int x)
{LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));s->data = x;s->next = NULL;Q.rear->next = s;Q.rear = s;return true;
}// 4.出队
bool DeEmpty(LinkNode &Q, int &x)
{if (Q.rear == Q.front)return false;LinkNode *p = Q.front->next;x = p->data;Q.front->next = Q.front->next->next;if (Q.rear == p)Q.rear = Q.front;free(p);return true;
}

不带头结点的链式队列

typedef struct LinkNode
{int data;struct LinkNode *next;
} LinkNode;typedef struct
{LinkNode *front, *rear;
} LinkNode;//  不带头结点的实现方式// 1.初始化
void InitQueue(LinkNode &Q)
{Q.front = Q.rear = NULL;
}// 2.判断是否为空
bool isEmpty(LinkNode &Q)
{if (Q.front == NULL)return true;return false;
}// 3.入队
bool EnEmpty(LinkNode &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;}return true;
}// 4.出队
bool DeEmpty(LinkNode &Q, int &x)
{if (Q.rear == NULL)return false;LinkNode *p = Q.front;x = p->data;Q.front = p->next;if (Q.rear == p){Q.rear = NULL;Q.front = NULL;}free(p);return true;
}