# 数据结构之栈与队列

xiaoxiao2021-02-28  20

### 栈:

#include <stdio.h> #include <stdlib.h> #include <time.h> #define MaxSize 20 typedef struct _Stack { char * top; // 栈首指针 char * end; // 栈尾指针 }Stack , *pStack; // ====================顺序栈的功能封装===================================== void InitStack (pStack *p); // 初始化指针 void PushStack (pStack , char ch); // 压栈 void PopStack (pStack p , char *ch);//出栈 int LenStack (pStack p ); // 栈的长度 void TraStack (pStack p); // 遍历栈区 void DestroyStack (pStack p); // 释放栈区 int main () { pStack one = (pStack) malloc (sizeof(Stack)); InitStack (one); DestroyStack (one); return 0; } void InitStack (pStack *p ) { (*p)->top = (char *)malloc(sizeof(char)*MaxSize); (*p)->end = (*p)->top; } void PushStack (pStack p , char ch) { *(p->end) = ch; p->end++; } void PopStack (pStack p , char *ch) { p->end--; (*ch)=*(p->end); } int LenStack (pStack p ) { int i=0 ; char * pl=p->top; while (pl!=p->end) { pl++; i++; } return i; } void TraStack (pStack p) { char * str; str = p->top; while (str != p->end) { printf ("%c -> " , *str); str++; } printf ("End\n"); } void DestroyStack (pStack p) { free (p->top); }

### 队列：

#ifndef queue_Header_h #define queue_Header_h #include <stdio.h> #include <stdlib.h> #include <stdbool.h> //队列的结点结构 typedef struct Node{ int data; struct Node *next; } Node, *Queue; //队列的结构，嵌套 typedef struct{ Queue front; Queue rear; } LinkQueue; //初始化 //开始必然是空队列，队尾指针和队头指针都指向头结点 void initQueue(LinkQueue *queue) { //初始化头结点 queue->front = queue->rear = (Queue)malloc(sizeof(Node)); if (NULL == queue->front) { exit(0); } queue->front->next = NULL; } //判空 bool isEmpty(LinkQueue queue) { return queue.rear == queue.front ? true : false; } //入队,只在一端入队，另一端出队，同样入队不需要判满 void insertQueue(LinkQueue *queue, int temp) { Queue q = (Queue)malloc(sizeof(Node)); if (NULL == q) { exit(0); } //插入数据 q->data = temp; q->next = NULL; //rear 总是指向队尾元素 queue->rear->next = q; queue->rear = q; } //出队，需要判空 void deleteQueue(LinkQueue *queue) { Queue q = NULL; if (!isEmpty(*queue)) { q = queue->front->next; queue->front->next = q->next; //这句很关键，不能丢 if (queue->rear == q) { queue->rear = queue->front; } free(q); } } //遍历 void traversal(LinkQueue queue) { int i = 1; Queue q = queue.front->next; while (q != NULL) { printf("队列第%d个元素是：%d\n", i, q->data); q = q->next; i++; } } //销毁 void destoryQueue(LinkQueue *queue) { while (queue->front != NULL) { queue->rear = queue->front->next; free(queue->front); queue->front = queue->rear; } puts("销毁成功！"); } #endif