抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

堆栈和队列及 C 语言实现

C/C++

本文发布于：2022年7月11日

字数：1.4k字

时长：6分钟

堆栈（stack）又称为栈或堆叠，是只允许在一端进行插入或删除操作的线性表，遵循先进后出 FILO（First In Last Out）的原则。队列（Queue）简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队，删除元素称为出队或离队。以下为我在学习和实战练习过程中所做的笔记，可供参考。

一、栈的基本操作

栈顶（Top）入栈、出栈：

1
2
3
4
5
6
#define MaxSize 50
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];//数组
    int top;
}SqStack;

实现栈可以用数组，也可以用链表，我们这里使用数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int main()
{
    SqStack S;//先进后出 FILO  LIFO
    bool flag;
    ElemType m;//用来存放拿出的元素
    InitStack(S);//初始化
    flag=StackEmpty(S);
    if(flag)
    {
      	printf("栈是空的\n");
    }
    Push(S,3);//入栈元素3
    Push(S,4);//入栈元素4
    Push(S,5);
    flag=GetTop(S,m);//获取栈顶元素
    if(flag)
    {
      	printf("获取栈顶元素为 %d\n",m);
    }
    flag=Pop(S,m);//弹出栈顶元素
    if(flag)
    {
      	printf("弹出元素为 %d\n",m);
    }
    system("pause");
}

初始化栈：

1
2
3
4
5
6
7
8
9
10
11
12
void InitStack(SqStack &S)
{
		S.top=-1;//代表栈为空
}

bool StackEmpty(SqStack &S)
{
    if(S.top==-1)
      	return true;
    else
      	return false;
}

入栈：

1
2
3
4
5
6
7
8
9
bool Push(SqStack &S,ElemType x)
{
    if(S.top==MaxSize-1)//数组的大小不能改变，避免访问越界
    {
      	return false;
    }
    S.data[++S.top]=x;
    return true;
}

出栈：

1
2
3
4
5
6
7
bool Pop(SqStack &S,ElemType &x)
{
    if(-1==S.top)
      	return false;
    x=S.data[S.top--];//后减减，x=S.data[S.top];S.top=S.top-1;
    return true;
}

读取栈顶元素：

1
2
3
4
5
6
7
bool GetTop(SqStack &S,ElemType &x)
{
    if(-1==S.top)//说明栈为空
      	return false;
    x=S.data[S.top];
    return true;
}

二、循环队列

队列的特性是先进先出（FIFO），队头（Front）是允许删除的一端，又称队首，队尾（Rear）是允许插入的一端。

1
2
3
4
5
6
#define MaxSize 5
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];//数组,存储MaxSize-1个元素
    int front,rear;//队列头 队列尾
}SqQueue;

循环队列的操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
int main()
{
    SqQueue Q;
    bool ret;//存储返回值
    ElemType element;//存储出队元素
    InitQueue(Q);
    ret=isEmpty(Q);
    if(ret)
    {
      	printf("队列为空\n");
    }else{
      	printf("队列不为空\n");
    }
    EnQueue(Q,3);
    EnQueue(Q,4);
    EnQueue(Q,5);
    ret=EnQueue(Q,6);
    ret=EnQueue(Q,7);
    if(ret)
    {
      	printf("入队成功\n");
    }else{
      	printf("入队失败\n");
    }
    ret=DeQueue(Q,element);
    if(ret)
    {
      	printf("出队成功,元素值为 %d\n",element);
    }else{
      	printf("出队失败\n");
    }
    ret=DeQueue(Q,element);
    if(ret)
    {
      	printf("出队成功,元素值为 %d\n",element);
    }else{
      	printf("出队失败\n");
    }
    ret=EnQueue(Q,8);
    if(ret)
    {
      	printf("入队成功\n");
    }else{
      	printf("入队失败\n");
    }
    system("pause");
}

初始化队列：

1
2
3
4
5
6
7
8
9
10
11
12
void InitQueue(SqQueue &Q)
{
		Q.rear=Q.front=0;
}
//判空
bool isEmpty(SqQueue &Q)
{
		if(Q.rear==Q.front)//不需要为零
				return true;
		else
				return false;
}

入队：

1
2
3
4
5
6
7
8
bool EnQueue(SqQueue &Q,ElemType x)
{
    if((Q.rear+1)%MaxSize==Q.front) //判断是否队满
      	return false;
    Q.data[Q.rear]=x;//3 4 5 6
    Q.rear=(Q.rear+1)%MaxSize;
    return true;
}

出队：

1
2
3
4
5
6
7
8
bool DeQueue(SqQueue &Q,ElemType &x)
{
    if(Q.rear==Q.front)
      	return false;
    x=Q.data[Q.front];//先进先出
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

三、队列的链式存储

队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点。

存储结构相对于原有编号的链表增加了尾指针：

1
2
3
4
5
6
7
8
typedef int ElemType;
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct{
		LinkNode *front,*rear;//链表头 链表尾
}LinkQueue;//先进先出

头部删除法，尾部插入法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main()
{
    LinkQueue Q;
    bool ret;
    ElemType element;//存储出队元素
    InitQueue(Q);
    EnQueue(Q,3);
    EnQueue(Q,4);
    EnQueue(Q,5);
    EnQueue(Q,6);
    EnQueue(Q,7);
    ret=DeQueue(Q,element);
    if(ret)
    {
      	printf("出队成功,元素值为 %d\n",element);
    }else{
      	printf("出队失败\n");
    }
    system("pause");
}

初始化队列：

1
2
3
4
5
6
7
8
9
10
11
12
void InitQueue(LinkQueue &Q)
{
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));//头和尾指向同一个结点
    Q.front->next=NULL;
}
bool IsEmpty(LinkQueue Q)
{
    if(Q.front==Q.rear)
      	return true;
    else
      	return false;
}

入队，尾部插入法：

1
2
3
4
5
6
7
void EnQueue(LinkQueue &Q,ElemType x)
{
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=x;s->next=NULL;
    Q.rear->next=s;//rear始终指向尾部
    Q.rear=s;
}

出队，头部删除法：

1
2
3
4
5
6
7
8
9
10
11
bool DeQueue(LinkQueue &Q,ElemType &x)
{
    if(Q.front==Q.rear) return false;//队列为空
    LinkNode *p=Q.front->next;//头结点什么都没存，所以头结点的下一个节点才有数据
    x=p->data;
    Q.front->next=p->next;//断链
    if(Q.rear==p)//删除的是最后一个元素
      	Q.rear=Q.front;//队列置为空
    free(p);
    return true;
}

四、斐波那契数列

题目：n 个台阶，每次只能上 1 个台阶，或者 2 个台阶，n 个台阶，有多少种走法？

题解：Fib 是递归函数，调用自身，$f(n)=f(n-1)+f(n-2)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int Fib(int n)
{
    if(n==0)
      	return 0;
    else if(n==1)
      	return 1;
    else
      	return Fib(n-1)+Fib(n-2);
}
nt main()
{
    int num;
    while(scanf("%d",&num)!=EOF)
    {
      	printf("Fib(%d) = %d\n",num,Fib(num));
    }
    system("pause");
}
参考资料（References）：

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

本文永久地址：http://blog.zhuangzhihao.top/%E6%A0%88%E5%92%8C%E9%98%9F%E5%88%97/

Bezhuang

评论



Copyright © 2020 - 2022 Zhihao Zhuang. All rights reserved

本站访客数： 人，
总访问量： 次