企业官网建设流程全解析

栈：限定仅在表尾进行插入或删除操作的线性表。表尾端称为栈顶，表头端称为栈底。不含元素的表的空表称为空栈。

栈遵循后进先出原则

栈的两种表现形式：顺序栈和链栈

顺序栈：

用数组实现，分配一块连续内存

结构：底层：一维数组data[ ]

top：栈顶指针（下标），指向栈顶元素；top=-1代表栈空。

#include <stdlib.h>

#define MAX 5

typedef struct {

int data[MAX]; int top;

} Stack;

顺序栈的基本操作：

入栈，出栈，访问栈顶元素，判断栈是否为空以及是否栈满。

#include <stdio.h> #include <stdlib.h> #define MAX 5 typedef struct { int data[MAX]; int top; } Stack; void initStack(Stack *stack) { stack->top = -1; } int isEmpty(Stack *stack) { return stack->top == -1; } int isFull(Stack *stack) { return stack->top == MAX - 1; } void push(Stack *stack, int value) { if (isFull(stack)) { printf("Stack is full\n"); return; } stack->data[++stack->top] = value; } int pop(Stack *stack) { if (isEmpty(stack)) { printf("Stack is empty\n"); return -1; } return stack->data[stack->top--]; } int peek(Stack *stack) { if (isEmpty(stack)) { printf("Stack is empty\n"); return -1; } return stack->data[stack->top]; } int main() { Stack stack; initStack(&stack); push(&stack, 10); push(&stack, 20); push(&stack, 30); printf("Top element is: %d\n", peek(&stack)); printf("Popped element is: %d\n", pop(&stack)); printf("Top element after pop is: %d\n", peek(&stack)); return 0; }

链栈：用单链表实现的栈，不带头结点/带头结点均可，链表头部作为栈顶.把栈顶放在链表头，入栈出栈都在表头，不需要遍历，时间复杂度也就为O（1).

链栈结点结构：

typedef struct SNode{ int data; struct SNode *next; }SNode,*LinkStack;

top：栈顶指针，指向链表第一个结点；

top=NULL为空栈。

链栈基本操作：

初始化：top=NULL；

判空：top =NULL；

入栈：新建结点，新结点next=top；top=新结点（头插法）

出栈：判空；保存旧top；top=top->next;释放旧结点

访问栈顶元素：先判断，定义整型指针指向栈顶数据域*val=top->data

#include <stdio.h> #include <stdlib.h> // 链栈结点结构体 typedef struct SNode { int data; // 数据域 struct SNode *next; // 指针域 } SNode, *LinkStack; // 1.初始化链栈 void InitStack(LinkStack *top) { *top = NULL; // 栈顶置空，空栈 } // 2.判栈空 int StackEmpty(LinkStack top) { if(top == NULL) return 1; // 空返回1 else return 0; } // 3.入栈（头插法） int Push(LinkStack *top, int val) { // 新建结点 SNode *p = (SNode *)malloc(sizeof(SNode)); if(p == NULL) { // 内存分配失败 printf("内存分配失败！\n"); return 0; } p->data = val; p->next = *top; // 新结点指向原来栈顶 *top = p; // top更新为新结点，新结点成为栈顶 return 1; } // 4.出栈，用val接收弹出元素 int Pop(LinkStack *top, int *val) { if(StackEmpty(*top)) { printf("栈为空，无法出栈\n"); return 0; } SNode *p = *top; // p保存栈顶结点 *val = p->data; // 取出栈顶数据 *top = (*top)->next;// top下移 free(p); // 释放原栈顶结点 return 1; } // 5.取栈顶元素（不删除） int GetTop(LinkStack top, int *val) { if(StackEmpty(top)) { printf("栈为空，无栈顶元素\n"); return 0; } *val = top->data; return 1; } // 6.遍历链栈（从栈顶到栈底输出） void TraverseStack(LinkStack top) { SNode *p = top; printf("链栈元素(栈顶→栈底)："); while(p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n"); } // 7.销毁链栈，释放全部结点 void DestroyStack(LinkStack *top) { SNode *p, *q; p = *top; while(p != NULL) { q = p->next; free(p); p = q; } *top = NULL; } // 测试主函数 int main(void) { LinkStack st; int ret, topVal; InitStack(&st); Push(&st, 10); Push(&st, 20); Push(&st, 30); TraverseStack(st); GetTop(st, &topVal); printf("栈顶元素：%d\n", topVal); Pop(&st, &ret); printf("弹出元素：%d\n", ret); TraverseStack(st); DestroyStack(&st); return 0; }

顺序栈与链栈的区别

队列：先进先出的线性表，只允许在表的一端进行插入，而在另一端删除元素。允许插入的一端叫做队尾，允许删除的一端叫做队头。

队列的基本操作：

创建队列：

typedef struct

{

int data[MAXSIZE];

int front; int rear;

}SqQueue;

初始化：队首下标和队尾下标都为0

判空：队列没有元素

入队：先确认是否队满，队满无法入队，未满则插入队尾，队尾下标加1；

出队：先确认是否队空，队空无法出队，队首有元素就删除该元素，队头后移；（顺序非循环队列极易出现假溢出现象：front后面还有大量空间，rear到数组末尾就认为队列满而无法继续入队，可采用循环顺序队列来解决假溢出）

访问队首元素：若队列不为空，返回队首元素

#include <stdio.h> #define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int front; int rear; } SqQueue; // 初始化队列 void InitQueue(SqQueue *q) { q->front = 0; q->rear = 0; } // 判断队列是否为空 int IsEmpty(SqQueue *q) { return q->front == q->rear; } // 入队操作 int Enqueue(SqQueue *q, int x) { if (q->rear == MAXSIZE) { printf("队列已满无法入队"); return 0; } q->data[q->rear] = x; q->rear++; return 1; } // 出队操作 int Dequeue(SqQueue *q, int *x) { if (IsEmpty(q)) { printf("队列为空，无法执行出队操作"); return 0; } *x = q->data[q->front]; q->front++; return 1; } //访问队首元素 int Getqueue(SqQueue *q, int *x) { if (IsEmpty(q)) { printf("队列为空，无法进行访问"); return 0; } *x = q->data[q->front]; return 1; }

链队列：

用单链表实现队列，由数据结点和存放头尾指针的队列结构两部分组成；采用带表头结点的单链表，设置队头指针front指向头结点，队尾指针rear指向队尾数据结点。

• 判空：front == rear
• 入队：在队尾 rear 处插入新结点，更新 rear；
• 出队：删除头结点后继结点；删除最后一个结点时，必须将 rear 赋值为 front，避免 rear 悬空。
• 链队列没有假溢出，动态分配结点，长度不受预先定义常量限制。

#include <stdio.h> #include<stdlib.h> // 数据结点 typedef struct QNode { int data; struct QNode *next; } QNode; // 链队列，封装头尾指针 typedef struct { QNode *front; QNode *rear; } LinkQueue; void InitQueue(LinkQueue *q) { q->front = q->rear = (QNode *)malloc(sizeof(QNode)); q->front->next = NULL; } int IsEmpty(LinkQueue *q) { return q->front == q->rear; } int Enqueue(LinkQueue *q, int x) { QNode *s = (QNode *)malloc(sizeof(QNode)); if (s == NULL) { printf("内存分配失败"); return 0; } s->data = x; s->next = NULL; q->rear->next = s; //尾结点指向新结点 q->rear = s; //rear后移到新的队尾 return 1; } int Dequeue(LinkQueue *q, int *x) { if (IsEmpty(q)) { printf("链队列为空，无法出队"); return 0; } QNode *p = q->front->next; //p指向真正队头数据结点，初始化时front==rear代表此时front、rear都指向头结点，头结点不存有效数据 *x = p->data; q->front->next = p->next; // 如果删的是最后一个结点，rear要回指向头结点防止rear变成野指针 if (q->rear == p) { q->rear = q->front; } free(p); return 1; } int Getfront(LinkQueue *q, int *x) { if (IsEmpty(q)) { printf("队列为空，无法访问"); return 0; } *x = q->front->next->data; return 1; }

循环队列：

顺序数组实现，利用取模运算%，把数组看成环形，解决普通顺序队列的假溢出问题，牺牲一个储存单元区分队空、队满。

结构体定义：

例：MAXSIZE=5，数组下标0，1，2，3，4，牺牲一格，最多存四个元素

#define MAXSIZE 5 // 队列最大容量：实际最多存 MAXSIZE‑1 个元素 typedef struct{ int data[MAXSIZE]; int front; // 队头：指向队头元素下标 int rear; // 队尾：指向**下一个要插入的空位** } SqQueue;

初始化与判空条件与普通顺序队列一致

判满条件：

牺牲一个单元：不能存满全部数组，留一个空位用来区分空和满

int IsFull(SqQueue *q){ return (q->rear + 1) % MAXSIZE == q->front; }

虽然循环队列本质成环，但不能采用front=rear，队列空、队列满都会出现front==rear，条件冲突

入队操作：

先判满，将数据放入data[rear];rear=(rear+1)%MAXSIZE;

int EnQueue(SqQueue *q, int x){ if(IsFull(q)){ printf("队列满\n"); return 0; } q->data[q->rear] = x; q->rear = (q->rear + 1) % MAXSIZE; return 1; }

出队操作：

判空；取出data[front];front指向下一个位置：front=(front+1)%MAXSIZE，实现环形回转，解决假溢出。

int DeQueue(SqQueue *q, int *x){ if(IsEmpty(q)){ printf("队列空\n"); return 0; } *x = q->data[q->front]; q->front = (q->front + 1) % MAXSIZE; return 1; }

示例说明模运算全过程：

执行示例 MAXSIZE=5（最多 4 个元素）

1. 初始：front=0,rear=0 →空
2. En(q,10): data[0]=10; rear=(0+1)%5=1
3. En(q,20): data[1]=20; rear=2
4. En(q,30): data[2]=30; rear=3
5. En (q,40): data [3]=40; rear=4 →此时队列满(4+1)%5=0 == front=0

data[4]就是牺牲的空闲位置，不存数据。