c语言堆栈和队列

2025-01-04 08:43:19

推荐回答（4个）

回答1：

　　栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

　　队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

　　以上是从数据结构角度来看，从操作系统角度来看，所有的数据结构都是对虚拟内存的操作，堆是堆，栈是栈，栈指的是C语言函数所使用的自动有函数回收的虚拟内存空间，而堆则有操作系统堆管理器来管理的那部分虚拟内存，从C语言角度来看，使用malloc函数动态分配的内存，就是堆内存。

回答2：

#include
#include
#include /* malloc()等 */
#include /* INT_MAX等 */
#include /* EOF(=^Z或F6),NULL */
#include /* atoi() */
#include /* eof() */
#include /* floor(),ceil(),abs() */
#include /* exit() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */

/* c3-1.h 栈的顺序存储表示 */
#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
#define STACKINCREMENT 2 /* 存储空间分配增量 */
typedef int SElemType;
typedef struct SqStack
{
SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
SElemType *top; /* 栈顶指针 */
int stacksize; /* 当前已分配的存储空间，以元素为单位 */
}SqStack; /* 顺序栈 */

/* bo3-1.c 顺序栈（存储结构由c3-1.h定义）的基本操作（9个） */
Status InitStack(SqStack *S)
{ /* 构造一个空栈S */
(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
return OK;
}

Status DestroyStack(SqStack *S)
{ /* 销毁栈S，S不再存在 */
free((*S).base);
(*S).base=NULL;
(*S).top=NULL;
(*S).stacksize=0;
return OK;
}

Status ClearStack(SqStack *S)
{ /* 把S置为空栈 */
(*S).top=(*S).base;
return OK;
}

Status StackEmpty(SqStack S)
{ /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
if(S.top==S.base)
return TRUE;
else
return FALSE;
}

int StackLength(SqStack S)
{ /* 返回S的元素个数，即栈的长度 */
return S.top-S.base;
}

Status GetTop(SqStack S,SElemType *e)
{ /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
if(S.top>S.base)
{
*e=*(S.top-1);
return OK;
}
else
return ERROR;
}

Status Push(SqStack *S,SElemType e)
{ /* 插入元素e为新的栈顶元素 */
if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */
{
(*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top)++=e;
return OK;
}

Status Pop(SqStack *S,SElemType *e)
{ /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
if((*S).top==(*S).base)
return ERROR;
*e=*--(*S).top;
return OK;
}

Status StackTraverse(SqStack S,Status(*visit)(SElemType))
{ /* 从栈底到栈顶依次对栈中每个元素调用函数visit()。 */
/* 一旦visit()失败，则操作失败 */
while(S.top>S.base)
visit(*S.base++);
printf("\n");
return OK;
}

Status visit(SElemType c)
{
printf("%d ",c);
return OK;
}

void main()
{
int j;
SqStack s;
SElemType e;
if(InitStack(&s)==OK)
for(j=1;j<=12;j++)
Push(&s,j);
printf("栈中元素依次为：");
StackTraverse(s,visit);
Pop(&s,&e);
printf("弹出的栈顶元素 e=%d\n",e);
printf("栈空否：%d(1:空 0:否)\n",StackEmpty(s));
GetTop(s,&e);
printf("栈顶元素 e=%d 栈的长度为%d\n",e,StackLength(s));
ClearStack(&s);
printf("清空栈后，栈空否：%d(1:空 0:否)\n",StackEmpty(s));
DestroyStack(&s);
printf("销毁栈后，s.top=%u s.base=%u s.stacksize=%d\n",s.top,s.base, s.stacksize);
}

堆栈的概念一楼已经解释，我就不再阐述啦！

回答3：

以前写过专门的程序分享下
堆栈的，不过是数组栈的。
/************************************************************************/
/*题目：数组实现栈的初始化，进栈，出栈，取顶数据，栈的状态判断，栈的清空*/
/*时间：2010-2-27 下午7时42分 */
/*coder：huifeng00 */
/************************************************************************/

#include
#include
#define MaxSize 100

int stack[MaxSize];
int top=-1;
//栈的初始化
void InitializeStack()
{
top=-1;
}
//进栈
void push(int data)
{
if(top==MaxSize)
{
printf("栈已满，不能压入数据!\n");
return;
}
stack[++top]=data;
}
//出栈
int pop()
{
if (top==-1)
{
printf("栈已空，不能弹出数据!\n");
return -1;
}
return stack[top--];
}
//取顶部数据
int peek()
{
if (top==-1)
{
printf("栈已空，不能取出数据!\n");
return -1;
}
return stack[top];
}
//判断栈是否为空
int isStackEmpty()
{
return top==-1?1:0;//当然也可以直接写为return top==-1;
}
//判断栈是否满
int isStackFull()
{
return top==MaxSize?1:0;//当然也可以直接写为return top==MaxSize;
}
//清空栈
void clearStack()
{
top=-1;
}

int main()
{
int data;
InitializeStack();
printf("请输入进栈的数据,-1代表数据结束\n");
scanf("%d",&data);
while(data!=-1)
{
push(data);
scanf("%d",&data);
}
printf("栈顶的数据: %d\n",peek());
while(1)
{
data=pop();
if (data==-1)
{
break;
}
printf("%d ",data);
}
return 0;
}
队列的
/************************************************************************/
/*题目：数组实现队列的初始化，进出队列操作，队列状态判断，队列清空 */
/*时间：2010-2-28 上午7时55分 */
/*coder：huifeng00 */
/************************************************************************/

#include
#include
#define MaxSize 100

int queue[MaxSize];//队列最多可以存放MaxSize个数据
int front,rear;//front指向队首数据，rear指向队尾数据后面一个位置。
int tag;//tag用来区别front==rear队列是空还是满
//队列的初始化
void initializeQueue()
{
front=rear=tag=0;
}
//入队
void enQueue(int data)
{
if ((rear==front&&tag))
{
printf("队列已满！无法入队！\n");
return;
}
queue[rear]=data;
rear=(rear+1)%MaxSize;
tag=1;
}
//出队
int deQueue()
{
int temp;
if ((rear==front)&&!tag)
{
printf("队列已空！无法出队！\n");
return -1;//-1代表为空
}
temp=queue[front];
front=(front+1)%MaxSize;
tag=0;
return temp;
}
//取队首数据
int getFront()
{
if ((rear==front)&&!tag)
{
printf("队列已空！无法取队首数据！\n");
return -1;//-1代表为空
}
return queue[front];
}
//队列是否为空
int isQueueEmpty()
{
return rear==front&&!tag;
}
//队列是否为满
int isQueueFull()
{
return rear==front&&tag;
}
//清空队列
void clearQueue()
{
rear=front=tag=0;
}

int main()
{
int data;
printf("请向队列输入数据，-1结束数据输入\n");
scanf("%d",&data);
while(data!=-1)
{
enQueue(data);
scanf("%d",&data);
}
printf("队首数据为：%d\n",getFront());
printf("队列数据出队依次为：\n");
while((data=deQueue())!=-1)
{
printf("%d ",data);
}
return 0;
}
上面都是C语言实现的。以前写的。
至于你说堆栈和栈的区别，这个其实和数据结构没有什么关系，这个是在C的内存管理中有这个概念，
堆：是一个动态分配的内存区域，用malloc申请的，例如，链表就需要动态申请内存区域，这写区域，不能直接访问，通过指针访问。必须用free释放内存空间，这和栈不同，栈自动释放。
栈：它存放的是函数的局部变量，过来作用域会自动释放。
有什么问题可以hi我。

回答4：

队列的代码:

#include "stdio.h"
#include "conio.h"

typedef char TypeData;
struct node
{
TypeData data;
struct node *next;
};

typedef struct Dui
{
struct node *dui_tou;
struct node *dui_wei;
}Dui_link;

void init(Dui_link *dui)
{
dui->dui_tou=dui->dui_wei=(struct node*)malloc(sizeof(struct node));
dui->dui_tou->next=NULL;
}

void jin(Dui_link *dui)
{
struct node *p=(struct node*)malloc(sizeof(struct node));
char ch;
printf("plase Input diu lie data:");
ch=getch();
putc(ch,stdout);
putchar('\n');

p->data=ch;
p->next=NULL;

(dui->dui_wei)->next=p;
dui->dui_wei=p;

}

void du_tou(Dui_link *dui)
{
struct node *p=(dui->dui_tou)->next;
if(dui->dui_tou != dui->dui_wei)
{
printf("du_tou data: %c \n",p->data);
}
else
{
printf("dui wei kong !\n");
}
}

void del(Dui_link *dui)
{
struct node *p=dui->dui_tou;
if(dui->dui_tou != dui->dui_wei)
{
dui->dui_tou=p->next;

if((dui->dui_tou)->next==NULL)
dui->dui_wei=dui->dui_tou=NULL;
p=p->next;
}
else
{
printf("dui wei kong \n");
}
free(p);
}
int main()
{
Dui_link dui;
int i;
init(&dui);

for(i=1;i<=5;i++)
jin(&dui);

du_tou(&dui);

del(&dui);
del(&dui);
del(&dui);
del(&dui);
du_tou(&dui);
getch();
return 0;
}

栈的代码：
#include "stdio.h"
#include "conio.h"

typedef char TypeData;
typedef struct Stack
{
TypeData data;
struct Stack *next;
}Stack_link;

Stack_link* New(Stack_link *Sq)
{
Stack_link *p=(Stack_link *)malloc(sizeof(Stack_link));
char ch;
printf("plase add data:");
ch=getch();
putc(ch,stdout);
putchar('\n');
p->data=ch;
p->next=Sq;
Sq=p;
return Sq;
}
void Stack(Stack_link *Sq)
{
if(Sq!=NULL)
printf("Stack data: %c\n",Sq->data);
else
printf("Stack kong\n");
}
Stack_link* chu_Sq(Stack_link *Sq)
{
if(Sq!=NULL)
{
Sq=Sq->next;
printf("chu Stack cheng gong\n");
}
return Sq;
}
main()
{
Stack_link *Sq=NULL;
int i;
for(i=1;i<=5;i++)
Sq=New(Sq);

Stack(Sq);

Sq=chu_Sq(Sq);

Stack(Sq);
getch();
}