……接上文
4.2 顺序栈
4.2.2 代码实现
头文件seqstack.h:
#ifndef __SEQSTACK_H__
#define __SEQSTACK_H__
typedef int datatype;
typedef struct seqstack
{
datatype *data; //指向栈的存储位置
int maxlen; //保存栈的最大长度
int top; //称为栈针，用的时候可以当作顺序表里的last来使用
//top始终代表当前栈内最后一个有效元素的下标
} seqstack_t;
//1.创建一个空栈，len代表创建栈时的最大长度。
seqstack_t *createEmptySeqStack(int len);
//2.判断是否为满,满返回1 未满返回0
int isFullSeqStack(seqstack_t *p);
//3.入栈,data代表入栈的数据
int pushStack(seqstack_t *p, int data);
//4.判断栈是否为空
int isEmptySeqStack(seqstack_t *p);
//5.出栈，返回出栈数据
int popSeqStack(seqstack_t *p);
//6. 清空栈
void clearSeqStack(seqstack_t *p);
//7. 获取栈顶数据(注意不是出栈操作，如果出栈，相当于删除了栈顶数据，只是将栈顶的数据获取到，不需要移动栈针)
int getTopSeqStack(seqstack_t *p);
//8. 求栈的长度,返回长度。
int lengthSeqStack(seqstack_t *p);
#endif
3) 入栈
//3.入栈,data代表入栈的数据
int pushStack(seqstack_t *p, int data)
{
// 1. 容错判断
if(isFullSeqStack(p))
{
perror("pushStack: isFullSeqStack");
return -1;
}
// 2. 往上移动栈针
p->top++;
// 3. 将数据入栈
p->data[p->top] = data;
}
4) 判断栈是否为空
//4.判断栈是否为空
int isEmptySeqStack(seqstack_t *p)
{
return p->top == -1;
}
5) 出栈
//5.出栈，返回出栈数据
int popSeqStack(seqstack_t *p)
{
// int data = p->data[p->top];
// p->top--;
// return data;
// 1. 容错判断
if(isEmptySeqStack(p))
{
perror("popSeqStack: isEmptySeqStack");
return -1;
}
// 2. 往下移动栈针
p->top--;
// 3. 将栈顶数据取出
return p->data[p->top+1];
}
6) 清空栈
//6. 清空栈
void clearSeqStack(seqstack_t *p)
{
p->top = -1;
}
7) 获取栈顶数据
// 7. 获取栈顶数据(注意不是出栈操作，如果出栈，相当于删除了栈顶数据，只是将栈顶的数据获取到，不需要移动栈针)
int getTopSeqStack(seqstack_t *p)
{
// 1. 容错判断
if (isEmptySeqStack(p))
{
perror("getTopSeqStack: isEmptySeqStack");
return -1;
}
return p->data[p->top];
}
8) 求栈的实际长度
//8. 求实际栈的长度,返回长度。
int lengthSeqStack(seqstack_t *p)
{
return p->top+1;
}
main函数：
int main(int argc, char const *argv[])
{
seqstack_t *p = createEmptySeqStack(5);
for (int i = 1; i <= 6; i++)
{
pushStack(p, i);
}
printf("栈顶是：%d\n", getTopSeqStack(p));
//只要栈不为空就出栈
printf("出栈");
while(!isEmptySeqStack(p))
{
printf("%d ", popSeqStack(p)); //出栈的顺序是 5 4 3 2 1 ，因为栈的思想先进后出
}
printf("\n");
return 0;
}
练习：
软通动力校园招聘笔试题
1. 若进栈顺序为 1,2,3,4 一下四种情况不可能出现的出栈序列是( )
A. 1,4,3,2
B. 2,3,4,1
C. 3,1,4,2
D. 3,4,2,1
C
2. 下列叙述正确的是( )
A. 线性表是线性结构
B. 栈与队列是非线性结构
C. 线性链表是非线性结构
D. 二叉树是线性结构
A
3. 下列关于栈叙述正确的是( )
A.在栈中只能插入数据
B.在栈中只能删除数据
C.栈是先进先出的线性表
D.栈是先进后出的线性表
D
4. 请问下面的程序有问题吗？如果有问题在哪儿？
#include <stdio.h>
#include <stdlib.h>
void get_memory(int *q)
{
q = (int *)malloc(sizeof(int));
}
int main()
{
int i;
int *p = NULL;
get_memory(p);
for(i = 0; i < 10; i++)
{
p[i] = i;
}
for(i = 0; i < 10; i++)
{
printf("%d\n", p[i]);
}
return 0;
}
错误：相当于值传递，并且开辟的空间大小不够用
修改：可以通过传递二级指针，或者返回值。
#include <stdio.h>
#include <stdlib.h>
void get_memory(int **q)
{
*q = (int *)malloc(sizeof(int) * 10);
}
int main()
{
int i;
int *p = NULL;
get_memory(&p);
for(i = 0; i < 10; i++)
{
p[i] = i;
}
for(i = 0; i < 10; i++)
{
printf("%d\n", p[i]);
}
free(p);
p=NULL;
return 0;
}
4.3 链式栈
4.3.1 特性
逻辑结构：线性结构
存储结构：链式存储
顺序栈和链式栈的区别：存储结构不同，实现的方式不同，顺序栈用顺序表实现而链栈用链表实现。
栈的操作：创建、入栈、出栈、清空、获取
4.3.2 代码实现
头节点：
#ifndef __LINKSTACK_H__
#define __LINKSTACK_H__
typedef int datatype;
typedef struct linkstack
{
datatype data;
struct linkstack *next;
} linkstack_t;
//1.创建一个空的栈
void createEmptyLinkStack(linkstack_t **ptop);
//2.入栈,ptop是传入的栈针的地址，data是入栈的数据
int pushLinkStack(linkstack_t **ptop, datatype data);
//3.判断栈是否为空
int isEmptyLinkStack(linkstack_t *top);
//4.出栈
datatype popLinkStack(linkstack_t **ptop);
//5.清空栈
void clearLinkStack(linkstack_t **ptop);
//6.求栈的长度
int lengthLinkStack(linkstack_t *top);
//7.获取栈顶数据,不是出栈,不需要移动main函数中的top，所以用一级指针
datatype getTopLinkStack(linkstack_t *top);
#endif
a) 创建一个空的栈
//1.创建一个空的栈
void createEmptyLinkStack(linkstack_t **ptop)
{
*ptop = NULL;
}
b) 入栈，ptop是传入的栈针的地址，data是入栈的数
//2.入栈,ptop是传入的栈针的地址，data是入栈的数据
int pushLinkStack(linkstack_t **ptop, datatype data)
{
// 1. 创建一个新节点保存即将入栈的数据
linkstack_t *pnew = (linkstack_t *)malloc(sizeof(linkstack_t));
// 2. 申请节点空间就是为了data
pnew->data = data;
// 3. 将新节点插入无头链表的头
pnew->next = *ptop;
// 4. 移动栈针，栈针top永远指向无头单向链表的头
*ptop = pnew;
return 0;
}
c) 判断栈是否为空
//3.判断栈是否为空
int isEmptyLinkStack(linkstack_t *top)
{
return top == NULL;
}
d) 出栈
//4.出栈
datatype popLinkStack(linkstack_t **ptop)
{
linkstack_t *pdel = NULL;
// 1. 容错判断
if(isEmptyLinkStack(*ptop))
{
perror("isEmptyLinkStack!!!");
return -1;
}
// 2. 定义一个pdel指针，指向被删除的节点也就是栈顶的第一个节点
pdel = *ptop;
// 3. 定义一个临时变量，保存出栈的数据，也就是保存栈针所指节点中的数据域
datatype temp = (*ptop)->data;
// 4. 跨过删除节点，将栈针即头指针向后移动一个位置
(*ptop) = (*ptop)->next;
// 5. 释放被删除节点
free(pdel);
pdel = NULL;
// 6. 返回出栈数据
return temp;
}
e) 清空栈
//5.清空栈
void clearLinkStack(linkstack_t **ptop)
{
while(!isEmptyLinkStack(*ptop))
popLinkStack(ptop);
}
f) 求栈的长度
//6.求栈的长度
int lengthLinkStack(linkstack_t *top)
{
int len = 0;
while(top != NULL)
{
len++;
top = top->next;
}
return len;
}
g) 获取栈顶数据
//7.获取栈顶数据,不是出栈,不需要移动main函数中的top，所以用一级指针
datatype getTopLinkStack(linkstack_t *top)
{
if(isEmptyLinkStack(top))
{
printf("getTopLinkStack: isEmptyLinkStack");
return -1;
}
return top->data;
}
总结：
顺序栈和链式栈的区别是什么？
(1) 存储结构不同：顺序栈是顺序存储，内存连续；链式栈是链式存储，内存不连续。
(2) 顺序栈的长度受限制，而链栈不会。
5. 队列
5.1 特性
队列是只允许再两端进行插入和删除操作的线性表，在队尾插入，在队头删除，插入的一段被称为“队尾”，删除的一端被称为“队头”。队列包括顺序队列(循环队列)、链式队列。
结构：先进先出FIFO
操作：创建、入列、出列、判断是否为空、判断是否为满、清空。
注意：为了避免假溢出问题，即队列前面还有空闲，但是队尾已经出现越界，所以在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进，需要引入循环队列。一般顺序队列也指循环队列。
循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。
5.2 循环队列(顺序队列)
逻辑结构：线性结构
存储结构：顺序存储结构
操作：创建、入列、出列、判空和满、清空
#define N 6
typedef int datatype;
typedef struct
{
datatype data[N];//循环队列的数组
int rear;//存数据端 rear 后面
int front;//取数据端 front 前面
}sequeue_t;
利用"模运算" （大家习惯用这个方法）
front==(rear+1)%N；
代码：
#include <stdio.h>
#include <stdlib.h>
#define N 6
typedef int datatype;
typedef struct
{
datatype data[N];//循环队列的数组
int rear;//存数据端 rear 后面
int front;//取数据端 front 前面
}sequeue_t;
//循环队列中，假设数组的元素个数为N，那么循环队列中存储最多的数据个数为N-1个
// 创建一个空队列
sequeue_t *createEmptySequeue()
{
sequeue_t *p = (sequeue_t *)malloc(sizeof(sequeue_t));
if(p == NULL)
{
perror("createEmptySequeue malloc failed");
return NULL;
}
p->rear = 0; // 使用时是数组的下标 尾
p->front = 0; // 使用时是数组的下标 头
return p;
}
// 判断队列是否为满
int isFullSequeue(sequeue_t *p)
{
//思想上，舍去数组上的一个存储位置,用于判断队列是否为满
//先判断rear的下一个位置是否等于front
return (p->rear + 1) % N == p->front;
}
//入列 data代表入列的数据
int inSequeue(sequeue_t *p,datatype data)
{
// 1. 容错判断
if(isFullSequeue(p))
{
perror("isFullSequeue!!");
return -1;
}
// 2. 入列，对尾rear移动
p->data[p->rear] = data;
p->rear = (p->rear + 1) % N;
}
//判断队列是否为空
int isEmptySequeue(sequeue_t *p)
{
return p->rear == p->front;
}
//出列
datatype outSequeue(sequeue_t *p)
{
datatype temp; // 临时保存即将出列的数据
// 1. 容错判断
if(isEmptySequeue(p))
{
perror("isEmptySequeue!!!");
return -1;
}
// 2. 出列数据：思想是先取出数据，然后front向后移动
// 1) 取出数据
temp = p->data[p->front];
// 2) 移动对头 front
p->front = (p->front + 1) % N;
return temp;
}
//清空队列函数
void clearSequeue(sequeue_t *p)
{
// 思想，只要队列不为空，就出列
while(!isEmptySequeue(p))
outSequeue(p);
}
//求队列实际的长度
int lengthSequeue(sequeue_t *p)
{
// 长度情况分为 rear >= front
// rear < front
if(p->rear >= p->front)
{
return p->rear - p->front;
}
else
return p->rear + N - p->front;
}
int main(int argc, char const *argv[])
{
sequeue_t *p = createEmptySequeue();
for (int i = 1; i <= N-1; i++)
{
inSequeue(p, i);
}
printf("len is %d \n", lengthSequeue(p));
printf("rear is %d front is %d\n", p->rear, p->front);
outSequeue(p);
outSequeue(p);
printf("len is %d \n", lengthSequeue(p));
inSequeue(p, 100);
printf("len is %d \n", lengthSequeue(p));
printf("rear is %d front is %d\n", p->rear, p->front);
while(!isEmptySequeue(p))
printf("%d ", outSequeue(p));
printf("\n");
return 0;
}
循环队列，如果数组的元素个数为N，那么队列中最多能够存储的数据数的多少？ N-1个 为什么？
答：rear 后面 队尾，在插入的时候，插入之前需要先判断 rear+1，也就是他的下一个为位置是否 等于 front 来判断队列是否为满，会造成浪费一个存储位置。
5.3 链式队列
逻辑结构：线性结构
存储结构：链式结构
操作：创建、入列、出列、判空、清空
队列结构体：
typedef int datatype;
typedef struct node_t
{
datatype data;
struct node_t *next;
} linkqueue_node_t, *linkqueue_list_t;
typedef struct //将队列头指针和尾指针封装到一个结构体里
{
linkqueue_list_t front; //相当于队列的头指针
linkqueue_list_t rear; //相当于队列的尾指针
//有了链表的头指针和尾指针，那么我们就可以操作这个链表
} linkqueue_t;
建立空队列：
代码：
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node_t
{
datatype data;
struct node_t *next;
} linkqueue_node_t, *linkqueue_list_t;
typedef struct //将队列头指针和尾指针封装到一个结构体里
{
linkqueue_list_t front; //相当于队列的头指针
linkqueue_list_t rear; //相当于队列的尾指针
//有了链表的头指针和尾指针，那么我们就可以操作这个链表
} linkqueue_t;
// 1. 创建一个空的队列，用有头链表
linkqueue_t *createEmptyLinkQueue()
{
// 1) 申请队列空间，就是为了装东西
linkqueue_t *p = (linkqueue_t *)malloc(sizeof(linkqueue_t));
if (NULL == p)
{
perror("createEmptyLinkQueue p malloc err");
return NULL;
}
// 2) 申请链表的头节点空间，让rear和front都指向头结点
p->front = p->rear = (linkqueue_list_t)malloc(sizeof(linkqueue_node_t));
if (NULL == p->rear)
{
perror("createEmptyLinkQueue p->front malloc err");
return NULL;
}
// 可以将 p->front 当作h
// 可以将 p->rear 当作 ptail
p->rear->next = NULL;
return p;
}
//2.入列 data代表入列的数据
int inLinkQueue(linkqueue_t *p, datatype data)
{
//1.创建一个新的节点，用来保存即将插入的数据
linkqueue_list_t pnew = (linkqueue_list_t)malloc(sizeof(linkqueue_node_t));
//2.将入列的数据放入到新的节点中
pnew->data = data;
pnew->next = NULL;
//3.将新节点链链接到链表的尾巴
p->rear->next = pnew; // 新节点链接到链表的尾
p->rear = pnew; //rear移动，因为rear永远指向当前链表的尾
return 0;
}
//4.判断队列是否为空
int isEmptyLinkQueue(linkqueue_t *p)
{
return p->rear == p->front;
}
int main(int argc, char const *argv[])
{
/* code */
return 0;
}
未完待续……
标签：return,int,笔记,学习,队列,front,数据结构,data,rear From： https://blog.csdn.net/m0_64412253/article/details/144247267