本文主要是介绍郝斌数据结构--栈和队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
线性结构的两种常见应用之一 栈
定义 一种可以实现“先进后出”的存储结构
分类
静态栈 类似数组的结构
动态栈 类似链表的结构
栈的应用
（1）函数调用（所有的函数调用都是压栈与出栈）
所谓函数A调用函数B就是把A的最后执行的一个语句的地址与调用的B函数的
所有内容压到一个栈内部去执行，执行完毕出栈，然后地址出栈接着执行A函数
（2）中断（中断一个进程去执行下一个进程）
（3）表达式求值（表达式的数值部分与运算符会分开存放，利用两个栈可以制作一个简易计算器）
（4）内存分配（动态内存在堆中分配）
（5）缓冲处理
（6）迷宫（游戏中的地图，为什么走到一部分就走不动了）
# include <stdio.h>
# include <malloc.h>
# include <stdlib.h>
# include <stdbool.h>
typedef struct Node
{
int data;
struct Node *pNext;
}NODE, *PNODE;
typedef struct Stack
{
PNODE pTop;
PNODE pBottom;
}STACK, *PSTACK;
void init(PSTACK pS);
void push(PSTACK pS, int val);
bool pop(PSTACK pS, int *pVal);
bool clear(PSTACK pS);
bool traverse(PSTACK pS);
bool is_empty(PSTACK pS);
int main(void)
{
STACK S;
int val;
init(&S);
push(&S, 1);
push(&S, 2);
//push(&S, 3);
//push(&S, 5);
//push(&S, 6);
traverse(&S);
if (pop(&S, &val))
printf("出栈成功 值为%d \n", val);
traverse(&S);
if (pop(&S, &val))
printf("出栈成功 值为%d \n", val);
traverse(&S);
if (clear(&S))
printf("清除成功 \n");
traverse(&S);
return 0;
}
void init(PSTACK pS)
{
PNODE pNode = (PNODE)malloc(sizeof(NODE));
if (pS == NULL)
{
printf("内存分配失败！\n");
exit(-1);
}
pS->pTop = pNode;
pS->pBottom = pNode;
pS->pBottom->pNext = NULL;// pS->pTop->pNext = NULL;
}
void push(PSTACK pS, int val)
{
PNODE pNode = (PNODE)malloc(sizeof(NODE));
if (pS == NULL)
{
printf("内存分配失败！\n");
exit(-1);
}
pNode->data = val;
pNode->pNext = pS->pTop;
pS->pTop = pNode;
return;
}
bool traverse(PSTACK pS)
{
if (is_empty(pS))
{
return false;
}
PNODE pNode = pS->pTop;
while (pNode != pS->pBottom) //while (pNode->pNext != NULL)
{
printf("%d ", pNode->data);
pNode = pNode->pNext;
}
printf("\n");
}
bool pop(PSTACK pS, int *pVal)
{
if (is_empty(pS))
{
return false;
}
else
{
PNODE pNode = pS->pTop;
*pVal = pNode->data;
pS->pTop = pNode->pNext;
free(pNode);
return true;
}
}
bool is_empty(PSTACK pS)
{
if (pS->pTop == pS->pBottom)
{
printf("空栈\n");
return true;
}
else
{
return false;
}
}
// 类似于 pop
bool clear(PSTACK pS)
{
if (is_empty(pS))
{
return false;
}
PNODE pNode;
while (pS->pTop != pS->pBottom)
{
pNode = pS->pTop;
pS->pTop = pNode->pNext;
free(pNode);
printf("清除中...\n");
}
}
线性结构的两种常见应用之二 队列
定义 一种可以实现“先进先出”的存储结构
分类
- 链式队列 用链表实现
- 静态队列 用数组实现
静态队列通常都必须使循环队列
循环队列的讲解：
1. 静态队列为什么必须是循环队列
2. 循环队列需要几个参数来确定 及其含义
需要2个参数来确定
front
rear
3. 循环队列各个参数的含义
2个参数不同场合有不同的含义
1）队列初始化
front和rear的值都是零
2）队列非空
front代表的是队列的第一个元素
rear代表的是队列的最后一个有效元素的下一个元素
3）队列空
front和rear的值相等， 但不一定是空
4. 循环队列入队伪算法讲解
两步完成
1. 将值存入r所代表的 位置
2.错误写法 r=r+1
正确写法 r=（r+1）% 数组的长度
5. 循环队列出队伪算法讲解
f = （f+1）% 数组的长度
6. 如何判断循环队列是否为空
判断 front 与 rear 的值是否相等
7. 如何判断循环队列是否已满
预备知识 front的值可能比rear大 也可能比reat小 也可能相等
两种方式
1. 多增加一个标志参数（ f 和 r 相等）
2. 少用一个元素 （通常使用第二种方式）
如果 r 和 f 紧挨着，则队列已满
if（（r +1）% 数组长度 == f ）
已满
else
不满
# include <stdio.h>
# include <stdbool.h>
# include <stdlib.h>
typedef struct Queue
{
int * pBase;
int front;
int rear;
}QUEUE;
void init(QUEUE *);
bool en_queue(QUEUE *, int val);
void traverse_queue(QUEUE *);
bool full_queue(QUEUE *);
bool out_queue(QUEUE *, int *);
bool empty_queue(QUEUE *);
int main(void)
{
QUEUE Q;
int val;
init(&Q);
en_queue(&Q, 1);
en_queue(&Q, 2);
en_queue(&Q, 3);
en_queue(&Q, 4);
en_queue(&Q, 5);
en_queue(&Q, 6);
en_queue(&Q, 7);
en_queue(&Q, 8);
traverse_queue(&Q);
if (out_queue(&Q, &val))
{
printf("出栈成功 值为%d\n", val);
}
else
{
printf("出栈失败\n");
}
traverse_queue(&Q);
return 0;
}
void init(QUEUE *pQ)
{
pQ->pBase = (int *)malloc(sizeof(int) * 6);
pQ->front = 0;
pQ->rear = 0;
return;
}
bool en_queue(QUEUE * pQ, int val)
{
if (full_queue(pQ))
{
return false;
}
else
{
pQ->pBase[pQ->rear] = val;
pQ->rear = (pQ->rear + 1) % 6;
return true;
}
}
void traverse_queue(QUEUE * pQ)
{
int i;
i = pQ->front;
while (i != pQ->rear)
{
printf("%d ", pQ->pBase[i]);
i = (i + 1) % 6;
}
printf("\n");
return;
}
bool full_queue(QUEUE *pQ)
{
if ((pQ->rear + 1) % 6 == pQ->front)
{
return true;
}
else
{
return false;
}
}
bool out_queue(QUEUE *pQ, int *pVal)
{
if (empty_queue(pQ))
{
return false;
}
else
{
*pVal = pQ->pBase[pQ->front];
pQ->front = (pQ->front + 1) % 6;
}
}
bool empty_queue(QUEUE *pQ)
{
if (pQ->front == pQ->rear)
{
return true;
}
else
{
return false;
}
}
这篇关于郝斌数据结构--栈和队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
