栈和队列——分别用顺序表和链表实现——C语言实现

编程基础 • 2024-12-17 18:46 • 阅读 24

//author hernoforgot

//本次简单模拟栈和队列的操作，其中大多数我以无返回值实现，如果考虑优化和特殊情况，可稍微修改

//建议使用笔画一下操作流程，可以有助于您理解

//如果有错，或者有什么意见，欢迎留言，thanks!

栈和队列（线性结构）可以用链表，也可以用数组实现
区别：栈在一端操作先进后出
队列一端插入，另一端删除
1.栈：插入和删除的一端栈顶
其余一端不能操作称为栈底
是功能受限的线性表，与循序表不同的是不能在中间插入
进程入栈（压栈），出栈（取出数据）
作用：用于求某个进制
《若用链表实现，需要销毁链表》
2.队列：
插入队头删除数据
或者队尾插入数据
数组需要判断队满或者队空链表不需要
应用：先到先得

#include<stdio.h>

#include <stdlib.h>

/* 栈 */

typedef struct stack{
int data[20]; //存放数据
int size; //数组大小
int top; //用下标形式表示栈顶
}STACK;

//初始化栈
void init(STACK *st){
st->top = 0;
st->size = 20; //指针，不能用点运算符
}

//入栈，存储数据
void pushStack(STACK *st, int data){
if (st->top >= st->size){
printf("栈已满不能入栈");
return;
}
st->data[st->top] = data;
st->top++;
}
//出栈删除数据，只能在栈顶实现并得到出栈素
int popStack(STACK *st){
if (st->top <= 0){
printf("栈空的，无法实现出栈");
return -1;
}
st->top--;
return st->data[st->top];
}
int main(){
STACK stack;
init(&stack);
//输入数据
for (int i = 0; i < 10; i++){
pushStack(&stack,i);
}
//可以发现是先进后出
//输出一定个数的数据
for (int i = 0; i < 10; i++){
printf("%d\t",popStack(&stack));

}

getchar();

return 0;
}

/ 队列 /

//写了一个结构体并为之起别名方便使用

typedef struct node{
public:
int data;
struct node *next;
}NODE, *PNODE;
//使用队列头和队列尾
struct list{
PNODE front; //用作队头
PNODE end; //用作队尾
}List; //定义一个结构体变量，注意没有typedef 不是起别名
//先初始化队列链表--队头和队尾
void init(){
List.front = NULL;
List.end = NULL;
}
//压队，即入队
void pushList(int data){
//申请临时节点并且压入节点数据
PNODE temp = (PNODE)malloc(sizeof(NODE));
temp->data = data;
//判断队列是否为空
if (List.front == NULL){
//队列为空利用队头进行数据输入队尾指向该新插入的节点
List.front = temp;
List.front->data = data;
List.end = temp;
List.end->next = NULL;
}
else{
//队列不为空利用队尾插入队尾指向该新插入的节点
List.end->next = temp;
List.end = List.end->next;
List.end->data = data;
List.end->next = NULL;
}
}

//出队
void outList(){
//先判断是否队列为空
if (List.end == NULL){
printf("队列为空，无法出栈");
}
else {
printf("%d ", List.front->data);
PNODE temp; //用临时节点指向当前队头然后释放该内存
temp = List.front;
List.front = List.front->next;
free(temp);
//表明只有一个队素这是特殊情况，需要注意，
//如果不让队尾 List.end指向空，则会变成野指针
if (List.front == NULL)
{
free(List.front); List.end = NULL;
}
}
}
//删除队列与出栈相似
void deleteList(){
outList();
}

int main(){
//测试
init();
int i;
for (i = 0; i < 10; i++)
pushList(i);
for (i = 0; i < 10; i++)
outList();
getchar();
return 0;

}

PS：希望此文章对您有帮助

今天的文章栈和队列——分别用顺序表和链表实现——C语言实现分享到此就结束了，感谢您的阅读。

栈和队列——分别用顺序表和链表实现——C语言实现

相关推荐