devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构（栈和队列）_程序设计的数据结构 队列

作者：笔触狂放9 | 2024-05-15 12:18:46

赞

踩

程序设计的数据结构 队列

栈和队列

1、栈和队列的定义和特点

①.栈的定义和特点

栈( stack）是限定仅在表尾进行插人或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶( top )，相应地，表头端称为栈底（ bottom )。不含元素的空表称为空栈。后进先出( Last In First Out，LIFO）

在这里插入图片描述

在日常生活中，有很多类似栈的例子。例如，洗干净的盘子总是逐个往上叠放在已经洗好的盘子上面，而用时从上往下逐个取用。栈的操作特点正是上述实际应用的抽象。

在这里插入图片描述

②.队列的定义和特点

和栈相反，队列( queue)是一种 先进先出(First In First Out，FIFO) 的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这和日常生活中的排队是一致的，最早进人队列的元素最早离开。在队列中，允许插入的一端称为队尾( rear )，允许删除的一端则称为队头(front )。

在这里插入图片描述

队列在程序设计中也经常出现,一个最典型的例子就是操作系统中的作业排队。在允许多道程序运行的计算机系统中，同时有几个作业运行。如果运行的结果都需要通过通道输出，那就要按请求输入的先后次序排队。每当通道传输完毕可以接受新的输出任务时，队头的作业先从队列中退出做输出操作。凡是申请输出的作业都从队尾进入队列。

2、栈的表示和操作的实现

①.栈的类型定义

栈的抽象数据类型定义：

在这里插入图片描述

②.顺序栈的表示和实现

顺序栈是指利用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针 top指示栈顶元素在顺序栈中的位置。base为栈底指针，stacksize指示栈可使用的最大容量。若base = NULL,表示栈结构不存在，base = = top是栈空标志，top-base = = stacksize是栈满标志

//顺序栈的存储结构
#define MAXSIZE 100
typedef struct
{
    SElemType *base; //栈底指针
    SElemType *top;  //栈顶指针
    int stacksize;   //可使用的最大容量
} SqStack;


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

顺序栈中数据元素和栈指针之间的对应关系：

在这里插入图片描述

顺序栈的初始化

  1. 为顺序栈动态分配-个最大容量为MAXSIZE的数组空间，使base指向这段空间的基地址，即栈底。
  2. 栈顶指针top初始为base,表示栈为空。
  3. stacksize置为栈的最大容量MAXSIZE
Status InitStack(SqStack &S)
{
    S.base = new SElemType[MAXSIZE];
    if (!S.base)
        exit(OVERFLOW);
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return OK;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

顺序栈的入栈

  1. 判断栈是否满,若满则返回ERROR。
  2. 将新元素压入栈顶,栈顶指针加 1。

在这里插入图片描述

Status Push(SqStack &S, SElemType e)
{ // 插入元素e为新的栈顶元素
    if (S.top - S.base == S.stacksize)
        return ERROR; //栈满
    *S.top++ = e;     // 新元素e压入栈顶，然后栈顶指针加1(*S.top=e;S.top++;)
    return OK;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

顺序栈的出栈

  1. 判断栈是否空,若空则返回 ERROR。
  2. 栈顶指针减1，栈顶元素出栈。

在这里插入图片描述

Status Pop(SqStack &S, SElemType &e)
{ // 删除S的栈顶元素，用e返回其值
    if (S.top == S.base)
        return ERROR; //栈空报错
    e = *--S.top;     //栈顶指针减1，然后获取栈顶元素e(--S.top;e=*S.top;)
    return OK;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

顺序栈的实现

测试样例：SqStack.txt
测试内容：
A
B
C
D

/***顺序栈的实现***/

#include<iostream>
#include<fstream>
using namespace std;

//顺序栈定义
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE  100//顺序栈存储空间的初始分配量
typedef int Status;
typedef char SElemType;

typedef struct {
	SElemType *base;//栈底指针
	SElemType *top;//栈顶指针
	int stacksize;//栈可用的最大容量
} SqStack;

//顺序栈的初始化
Status InitStack(SqStack &S) {
	//构造一个空栈S
	S.base = new SElemType[MAXSIZE];//为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
	if (!S.base)
		exit(OVERFLOW); //存储分配失败
	S.top = S.base; //top初始为base，空栈
	S.stacksize = MAXSIZE; //stacksize置为栈的最大容量MAXSIZE
	return OK;
}
//顺序栈的入栈
Status Push(SqStack &S, SElemType e) {
	// 插入元素e为新的栈顶元素
	if (S.top - S.base == S.stacksize)
		return ERROR; //栈满
	*(S.top++) = e; //元素e压入栈顶，栈顶指针加1
	return OK;
}
//顺序栈的出栈
Status Pop(SqStack &S, SElemType &e) {
	//删除S的栈顶元素，用e返回其值	
	if (S.base == S.top)
		return ERROR;//栈空
	e = *(--S.top); //栈顶指针减1，将栈顶元素赋给e
	return OK;
}
//取顺序栈的栈顶元素
char GetTop(SqStack S) {//返回S的栈顶元素，不修改栈顶指针
	if (S.top != S.base) //栈非空
		return *(S.top - 1); //返回栈顶元素的值，栈顶指针不变
}

int main() {
	SqStack s;
	int choose, flag = 0;
	SElemType j, e, t;
	cout << "1.初始化\n";
	cout << "2.入栈\n";
	cout << "3.读栈顶元素\n";
	cout << "4.出栈\n";
	cout << "0.退出\n\n";

	choose = -1;
	while (choose != 0) {
		cout << "请选择:";
		cin >> choose;
		switch (choose) {
		case 1://顺序栈的初始化
			if (InitStack(s)) {
				flag = 1;
				cout << "成功对栈进行初始化\n\n";
			} else
				cout << "初始化栈失败\n\n";
			break;
		case 2: {//顺序栈的入栈
			fstream file;
			file.open("SqStack.txt");//
			if (!file) {
				cout << "错误！未找到文件！\n\n" << endl;
				exit(ERROR);
			}
			if (flag) {
				flag = 1;
				cout << "进栈元素依次为：\n";
				while (!file.eof()) {
					file >> j;
					if (file.fail())
						break;
					else {
						Push(s, j);
						cout << j << "  ";
					}
				}
				cout << endl << endl;
			} else
				cout << "栈未建立，请重新选择\n\n";
			file.close();
		}
			break;
		case 3://顺序栈的出栈
			if(flag != -1 && flag != 0)
				cout << "栈顶元素为：\n" << GetTop(s) << endl << endl;
			else
				cout << "栈中无元素，请重新选择\n" << endl;
			break;
		case 4://取顺序栈的栈顶元素
			cout << "依次弹出的栈顶元素为:\n";
			while (Pop(s, t)){
				flag = -1;
				cout << t << "  ";
			}
			cout << endl << endl;
			break;
		}
	}
	return 0;
}

  • 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
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117

②.链栈的表示和实现

链栈是指采用链式存储结构实现的栈，通常链栈用单链表来表示，链栈的结点结构与单链表的结构相同。

在这里插入图片描述

//链栈的存储结构
typedef struct StackNode
{
    ElemType data;
    struct StackNode *next;
} StackNode, *LinkStack;

LinkStack S;


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

由于栈的主要操作是在栈顶插人和删除，显然以链表的头部作为栈顶是最方便的，而且没必要像单链表那样为了操作方便附加一个头结点。

链栈的初始化

链栈的初始化操作就是构造一个空栈，因为没必要设头结点，所以直接将栈顶指针置空即可。

Status InitStack(LinkStack &S)
{ // 构造一个空栈 S，栈顶指针置空
    S = NULL;
    return OK;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

链栈的入栈

  1. 为入栈元素e分配空间，用指针p指向。
  2. 将新结点数据域置为e。
  3. 将新结点插人栈顶。
  4. 修改栈顶指针为p。

在这里插入图片描述

Status Push(LinkStack &S, SElemType e)
{                      //在栈顶插入元素e
    p = new StackNode; //生成新结点
    p->data = e;       //将新结点数据域置为e
    p->next = S;       //将新结点插入栈顶
    S = p;             //修改栈顶指针为p
    return OK;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

链栈的出栈

  1. 判断栈是否为空，若空则返回ERROR。
  2. 将栈顶元素赋给e。
  3. 临时保存栈顶元素的空间，以备释放。
  4. 修改栈顶指针,指向新的栈顶元素。
  5. 释放原栈顶元素的空间。

在这里插入图片描述

Status Pop(LinkStack &S, SElemType &e)
{ //删除S的栈顶元素，用e返回其值
    if (S == NULL)
        return ERROR; //栈空
    e = S->data;      //将栈顶元素赋给e
    p = S;            //用p临时保存栈顶元素空间，以备释放
    S = S->next;      //修改栈顶指针
    delete p;         //释放原栈顶元素的空间
    return OK;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

取链栈的栈顶元素

与顺序栈—样，当栈非空时，此操作返回当前栈顶元素的值，栈顶指针S保持不变。

在这里插入图片描述

SElemType GetTop(LinkStack S)
{
    if (S != NULL)
        return S–> data;
}

  • 1
  • 2
  • 3
  • 4
  • 5

链栈的实现

测试样例：SqStack.txt
测试内容：
A
B
C
D

/***链栈的实现***/
#include <bits/stdc++.h>
using namespace std;

#define OK 1
#define ERROR 0
typedef int Status;
typedef int SElemType;
//链栈定义
typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
} StackNode, *LinkStack;
//链栈的初始化
Status InitStack(LinkStack &S)
{ // 构造一个空栈 S，栈顶指针置空
    S = NULL;
    return OK;
}
//链栈的入栈
Status Push(LinkStack &S, SElemType e)
{ //在栈顶插入元素e
    LinkStack p;
    p = new StackNode; //生成新结点
    p->data = e;       //将新结点数据域置为e
    p->next = S;       //将新结点插入栈顶
    S = p;             //修改栈顶指针为p
    return OK;
}
//链栈的出栈
Status Pop(LinkStack &S, SElemType &e)
{ //删除S的栈顶元素，用e返回其值
    LinkStack p;
    if (S == NULL)
        return ERROR; //栈空
    e = S->data;      //将栈顶元素赋给e
    p = S;            //用p临时保存栈顶元素空间，以备释放
    S = S->next;      //修改栈顶指针
    delete p;         //释放原栈顶元素的空间
    return OK;
}
//取链栈的栈顶元素
SElemType GetTop(LinkStack S)
{                       //返回S的栈顶元素，不修改栈顶指针
    if (S != NULL)      //栈非空
        return S->data; //返回栈顶元素的值，栈顶指针不变
}
int main()
{
    LinkStack s;
    int select, flag = 0, i,j,n, t;
    cout << "1.初始化链栈\n";
    cout << "2.链栈的入栈\n";
    cout << "3.读栈顶元素\n";
    cout << "4.链栈的出栈\n";
    cout << "0.退出\n\n";

    while (1)
    {
        cout << "请选择:";
        cin >> select;
        switch (select)
        {
        case 1: //链栈的初始化
            if (InitStack(s))
            {
                flag = 1;
                cout << "成功对栈进行初始化\n\n";
            }
            else
                cout << "初始化栈失败\n\n";
            break;
        case 2:
         //链栈的入栈
            cout << "请输入元素个数：";
            cin >> n;
            cout << "请输入" << n << "个元素：";
            for (j = 1; j <= n; ++j)
            {
                cin >> i;
                if (Push(s, i))
                {
                    flag = 1;
                }
            }
            if (flag = 1)
            {
                cout << "入栈操作成功！\n\n";
            }
            break;
        case 3: //取链栈的栈顶元素
            if (flag != -1 && flag != 0)
                cout << "栈顶元素为：\n"
                     << GetTop(s) << endl
                     << endl;
            else
                cout << "栈中无元素，请重新选择\n"
                     << endl;
            break;
        case 4: //链栈的出栈
            if (flag)
            {
                cout << "依次弹出的栈顶元素为:\n";
                while (Pop(s, t))
                    cout << t << "  ";
                cout << endl
                     << endl;
            }
            else
                cout << "栈未建立，请重新选择\n\n";
            break;
        case 0:
            return 0;
        default:
            cout << "请重新输入！\n\n";
            break;
        }
        }
        return 0;
    }

  • 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
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121

④.栈与递归

递归的定义

若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的;
若一个过程直接或间接地调用自己，则称这个过程是递归的。

递归实例

在这里插入图片描述
过程的嵌套定义

在这里插入图片描述
分治法

long Fact(long n)
{
    if (n == 1)
        return 1; //基本项
    else
        temp = n * Fact(n - 1); //归纳项
    return temp;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

在这里插入图片描述

⑤.思考

问：根据栈的特性，如果进栈序列为A,B,C,D,E，能否得到D,C,E,A,B和A,C,E,D,B的出栈序列，如果不能得到请说明原因，如果可以得到请写出入栈、出栈的过程。

答：出栈序列D,C,E,A,B不可能，因为D先出栈，表明这时A、B已经入栈，A为栈底，出栈时A肯定在B之后。出栈序列A,C,E,D,B可能，入栈、出栈的过程:PUSH(S,A);POP(S);PUSH(S,B);PUSH(S,C);POP(S);PUSH(S,D);PUSH(S,E);POP(S);POP(S); POP(S)。

3、队列的表示和操作的实现

①.队列的类型定义

队列的抽象数据类型定义：

在这里插入图片描述

②.队列的顺序表示和实现

和顺序栈相类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外,尚需附设两个整型变量 front和rear分别指示队列头元素及队列尾元素的位置（后面分别称为头指针和尾指针)。队列的顺序存储结构表示如下:

#define MAXQSIZE 100 //最大队列长度
Typedef struct
{
    QElemType *base; //存储空间的基地址
    int front;       //头指针
    int rear;        //尾指针
} SqQueue;


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

顺序分配的队列中头、尾指针和元素之间的关系：

在这里插入图片描述

假设当前队列分配的最大空间为6，则当队列处于上图（d）所示的状态时不可再继续插入新的队尾元素，否则会出现溢出现象，即因数组越界而导致程序的非法操作错误。事实上，此时队列的实际可用空间并未占满，所以这种现象称为==“假溢出”==。这是由“队尾入队，队头出队”这种受限制的操作造成的。解决这种“假溢出”问题一个较巧妙的办法是将顺序队列变为一个环状的空间，如下图所示，称之为循环队列。

在这里插入图片描述
头、尾指针以及队列元素之间的关系不变，只是在循环队列中，头、尾指针“依环状增1”的操作可用“模”运算来实现。通过取模,头指针和尾指针就可以在顺序表空间内以头尾衔接的方式“循环”移动。循环队列中队空和队满的条件是：

队空的条件:Q.front = = Q.rear
队满的条件:(Qrear + 1)%MAXQSIZE = = Q.front

循环队列的初始化

为队列分配一个最大容量为MAXSIZE的数组空间，base指向数组空间的首地址。头指针和尾指针置为零，表示队列为空。

Status InitQueue(SqQueue &Q)
{
    Q.base = new QElemType[MAXQSIZE];
    if (!Q.base)
        exit(OVERFLOW);
    Q.front = Q.rear = 0;
    return OK;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

求循环队列的长度

对于非循环队列，尾指针和头指针的差值便是队列长度，而对于循环队列,差值可能为负数所以需要将差值加上MAXQSIZE，然后与MAXQSIZE求余。

int QueueLength(SqQueue Q)
{
    return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE
}

  • 1
  • 2
  • 3
  • 4

循环队列的入队

  1. 判断队列是否满，若满则返回ERROR。
  2. 将新元素插入队尾。
  3. 队尾指针加1。
Status EnQueue(SqQueue &Q，QElemType e)
{
    if ((Q.rear + 1) % MAXQSIZE == Q.front)
        return ERROR; //队满
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXQSIZE;
    return OK;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

循环队列的出队

  1. 判断队列是否为空，若空则返回ERROR。
  2. 保存队头元素。
  3. 队头指针加1。
Status DeQueue(LinkQueue &Q，QElemType &e)
{
    if (Q.front == Q.rear)
        return ERROR; //队空
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXQSIZE;
    return OK;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

取循环队列的队头元素

当队列非空时，此操作返回当前队头元素的值，队头指针保持不变。

SElemType GetHead(SqQueue Q)
{
    if (Q.front != Q.rear)     //队列非空
        return Q.base[Q.front] //返回队头元素的值，队头指针不变
}

  • 1
  • 2
  • 3
  • 4
  • 5

循环队列的实现：

测试样例：QNode.txt
测试内容：
A
B
C
D

/***循环队列基本操作***/

#include<iostream>
#include<fstream>
using namespace std;

#define MAXQSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef char QElemType;
typedef char SElemType;
typedef int Status;

typedef struct {
	QElemType *base;//初始化时动态分配存储空间
	int front;//头指针
	int rear;//尾指针
} SqQueue;

//循环队列的初始化
Status InitQueue(SqQueue &Q) {//构造一个空队列Q
	Q.base = new QElemType[MAXQSIZE]; //为队列分配一个最大容量为MAXSIZE的数组空间
	if (!Q.base)
		exit(OVERFLOW); //存储分配失败
	Q.front = Q.rear = 0; //头指针和尾指针置为零，队列为空
	return OK;
}

//求循环队列的长度
int QueueLength(SqQueue Q) {//返回Q的元素个数，即队列的长度
	return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

//循环队列的入队
Status EnQueue(SqQueue &Q, QElemType e) {//插入元素e为Q的新的队尾元素
	if ((Q.rear + 1) % MAXQSIZE == Q.front) //尾指针在循环意义上加1后等于头指针，表明队满
		return ERROR;
	Q.base[Q.rear] = e; //新元素插入队尾
	Q.rear = (Q.rear + 1) % MAXQSIZE; //队尾指针加1
	return OK;
}

//循环队列的出队
Status DeQueue(SqQueue &Q, QElemType &e) {//删除Q的队头元素，用e返回其值
	if (Q.front == Q.rear)
		return ERROR; //队空
	e = Q.base[Q.front]; //保存队头元素
	Q.front = (Q.front + 1) % MAXQSIZE; //队头指针加1
	return OK;
}

//取循环队列的队头元素
SElemType GetHead(SqQueue Q) {//返回Q的队头元素，不修改队头指针
	if (Q.front != Q.rear) //队列非空
		return Q.base[Q.front]; //返回队头元素的值，队头指针不变
}

int main() {
	int choose, flag = 0;
	SqQueue Q;
	QElemType e, j;
	cout << "1.初始化\n";
	cout << "2.入队\n";
	cout << "3.读队头元素\n";
	cout << "4.出队\n";
	cout << "0.退出\n\n";

	choose = -1;
	while (choose != 0) {
		cout << "请选择:";
		cin >> choose;
		switch (choose) {
		case 1://链队的初始化
			if (InitQueue(Q)) {
				flag = 1;
				cout << "成功对队列进行初始化\n\n";
			} else
				cout << "初始化队列失败\n\n";
			break;
		case 2: {//链队的入队
			fstream file;
			file.open("QNode.txt");
			if (!file) {
				cout << "错误！未找到文件！\n\n" << endl;
				exit(ERROR);
			}
			if (flag) {
				flag = 1;
				cout << "入队的元素依次为：\n";
				while (!file.eof()) {
					file >> j;
					if (file.fail())
						break;
					else {
						EnQueue(Q, j);
						cout << j << "  ";
					}
				}
				cout << endl << endl;
			} else
				cout << "队列未建立，请重新选择\n\n";
			file.close();
		}
			break;
		case 3://取链队的队头元素
			if (flag != -1 && flag != 0)
				cout << "队头元素为：\n" << GetHead(Q) << endl << endl;
			else
				cout << "队列中无元素，请重新选择\n" << endl;
			break;
		case 4://链队的出队
			cout << "依次弹出的队头元素为:\n";
			while (DeQueue(Q, e)) {
				flag = -1;
				cout << e << "  ";
			}
			cout << endl << endl;
			break;
		}
	}
	return 0;
}

  • 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
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123

③.队列的链式表示和实现

链队是指采用链式存储结构实现的队列。通常链队用单链表来表示，一个链队显然需要两个分别指示队头和队尾的指针(分别称为头指针和尾指针)才能唯一确定。这里和线性表的单链表一样，为了操作方便起见，给链队添加一个头结点，并令头指针始终指向头结点。
在这里插入图片描述

typedef struct Qnode
{
    QElemType data;
    struct Qnode *next;
} Qnode, *QueuePtr;
typedef struct
{
    QueuePtr front; //队头指针
    QueuePtr rear;  //队尾指针
} LinkQueue;


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

链队的初始化

  1. 生成新结点作为头结点，队头和队尾指针指向此结点。
  2. 头结点的指针域置空。
Status InitQueue(LinkQueue &Q)
{
    Q.front = Q.rear = new QNode;
    Q.front->next = NULL;
    return OK;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

链队的入队

  1. 为入队元素分配结点空间，用指针p指向。
  2. 将新结点数据域置为e。
  3. 将新结点插入到队尾。
  4. 修改队尾指针为p。
Status EnQueue(LinkQueue &Q, QElemType e)
{
    p = new QNode;
    if (!p)
        exit(OVERFLOW);
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

链队的出队

  1. 判断队列是否为空，若空则返回ERROR。
  2. 临时保存队头元素的空间，以备释放。
  3. 修改队头指针，指向下一个结点。
  4. 判断出队元素是否为最后一个元素，若是，则将队尾指针重新赋值，指向头结点。
  5. 释放原队头元素的空间。
Status DeQueue(LinkQueue &Q，QElemType &e)
{
    if (Q.front == Q.rear)
        return ERROR;        //若队列空，则返回ERROR
    p = Q.front->next;       // p指向队头元素
    e = p->data;             // e保存队头元素的值
    Q.front->next = p->next; //修改头指针
    if (Q.rear == p)
        Q.rear = Q.front; //如果最后一个元素被删，则
                          //队尾指针指向头结点
    delete p;             //释放原队头元素的空间
    return OK;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

取链队的队头元素

与循环队列一样，当队列非空时，此操作返回当前队头元素的值，队头指针保持不变。

SElemType GetHead(LinkQueue Q)
{
    if (Q.front != Q.rear)
        return Q.front->next->data; //返回队头元素的值，队头指针不变
}

  • 1
  • 2
  • 3
  • 4
  • 5

链队的实现：

测试样例：QNode.txt
测试内容：
A
B
C
D

/***链队的基本操作***/

#include<iostream>
#include<fstream>
using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef char QElemType;
typedef int Status;
typedef char SElemType;

//- - - - - 队列的链式存储结构- - - - - 
typedef struct QNode {
	QElemType data;
	struct QNode *next;
} QNode, *QueuePtr;
typedef struct {
	QueuePtr front; //队头指针
	QueuePtr rear; //队尾指针
} LinkQueue;

//链队的初始化
Status InitQueue(LinkQueue &Q) {//构造一个空队列Q
	Q.front = Q.rear = new QNode; //生成新结点作为头结点，队头和队尾指针指向此结点
	Q.front->next = NULL; //头结点的指针域置空
	return OK;
}

//链队的入队
Status EnQueue(LinkQueue &Q, QElemType e) {//插入元素e为Q的新的队尾元素
	QueuePtr p;
	p = new QNode; //为入队元素分配结点空间，用指针p指向
	p->data = e; //将新结点数据域置为e
	p->next = NULL;
	Q.rear->next = p; //将新结点插入到队尾
	Q.rear = p; //修改队尾指针
	return OK;
}

//链队的出队
Status DeQueue(LinkQueue &Q, QElemType &e) {//删除Q的队头元素，用e返回其值 
	QueuePtr p;
	if (Q.front == Q.rear)
		return ERROR; //若队列空，则返回ERROR
	p = Q.front->next; //p指向队头元素
	e = p->data; //e保存队头元素的值
	Q.front->next = p->next; //修改头指针
	if (Q.rear == p)
		Q.rear = Q.front; //最后一个元素被删，队尾指针指向头结点
	delete p; //释放原队头元素的空间
	return OK;
}

//取链队的队头元素
SElemType GetHead(LinkQueue Q) {//返回Q的队头元素，不修改队头指针
	if (Q.front != Q.rear) //队列非空
		return Q.front->next->data; //返回队头元素的值，队头指针不变
}

int main() {
	int choose, flag = 0;
	LinkQueue Q;
	QElemType e, j;
	cout << "1.初始化\n";
	cout << "2.入队\n";
	cout << "3.读队头元素\n";
	cout << "4.出队\n";
	cout << "0.退出\n\n";

	choose = -1;
	while (choose != 0) {
		cout << "请选择:";
		cin >> choose;
		switch (choose) {
		case 1://链队的初始化
			if (InitQueue(Q)) {
				flag = 1;
				cout << "成功对队列进行初始化\n\n";
			} else
				cout << "初始化队列失败\n\n";
			break;
		case 2: {//链队的入队
			fstream file;
			file.open("QNode.txt");
			if (!file) {
				cout << "错误！未找到文件！\n\n" << endl;
				exit(ERROR);
			}
			if (flag) {
				flag = 1;
				cout << "入队的元素依次为：\n";
				while (!file.eof()) {
					file >> j;
					if (file.fail())
						break;
					else {
						EnQueue(Q, j);
						cout << j << "  ";
					}
				}
				cout << endl << endl;
			} else
				cout << "队列未建立，请重新选择\n\n";
			file.close();
		}
			break;
		case 3://取链队的队头元素
			if (flag != -1 && flag != 0)
				cout << "队头元素为：\n" << GetHead(Q) << endl << endl;
			else
				cout << "队列中无元素，请重新选择\n" << endl;
			break;
		case 4://链队的出队
			cout << "依次弹出的队头元素为:\n";
			while (DeQueue(Q, e)) {
				flag = -1;
				cout << e << "  ";
			}
			cout << endl << endl;
			break;
		}
	}
	return 0;
}

  • 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
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126

4、栈和队列总结

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

5、例题与应用

在这里插入图片描述
在这里插入图片描述

  1. 编程实现栈的如下功能：
    （1）根据输入的栈中元素个数n和各元素值建立一个顺序栈，并输出栈中各元素值。
    （2）将数据元素e入栈，并输出入栈后的顺序栈中各元素值。
    （3）将顺序栈中的栈顶元素出栈，并输出出栈元素的值和出栈后顺序栈中各元素值。

在这里插入图片描述
在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;

#define OK 1
#define ERROR 0
#define MAXSIZE 100
typedef int Status;
typedef int SElemType;
//顺序栈定义
typedef struct
{
    SElemType *base;
    SElemType *top;
    int stacksize;
} SqStack;
//顺序栈的初始化
Status InitStack(SqStack &S)
{
    S.base = new SElemType[MAXSIZE];
    if (!S.base)
        exit(OVERFLOW);
    S.top = S.base;        //top初始为base，空栈
    S.stacksize = MAXSIZE; //stacksize置为栈的最大容量MAXSIZE
    return OK;
}
//顺序栈的遍历
Status StackTraverse(SqStack S)
{
    cout << "顺序栈中元素如下：\n";
    if (S.top == S.base)
    {
        return false;
    }
    while (S.top != S.base)
    {
        cout << *S.base++ << " ";
    }
    cout << endl;
    return OK;
}
//顺序栈的入栈
Status Push(SqStack &S, SElemType e)
{
    if (S.top - S.base == S.stacksize)
        return ERROR;
    *(S.top++) = e; //元素e压入栈顶，栈顶指针加1
    return OK;
}
//顺序栈的出栈
Status Pop(SqStack &S, SElemType &e)
{
    if (S.base == S.top)
        return ERROR;
    e = *(--S.top); //栈顶指针减1，将栈顶元素赋给e
    return OK;
}
int main()
{
    SqStack s;
    int select, flag = 0, i, j, n, e, t;

    cout << "1.初始化顺序栈\n";
    cout << "2.顺序栈的入栈\n";
    cout << "3.取出栈顶元素\n";
    cout << "4.顺序栈的出栈\n";
    cout << "0.退出\n\n";

    while (1)
    {
        cout << "\n请选择:";
        cin >> select;
        switch (select)
        {
        case 1:
            if (InitStack(s))
            {
                flag = 1;
                cout << "初始化栈成功\n\n";
            }
            else
            {
                cout << "初始化栈失败\n\n";
            }
            StackTraverse(s);
            break;
        case 2:
            cout << "请输入元素个数：";
            cin >> n;
            cout << "请输入" << n << "个元素：";
            for (j = 1; j <= n; ++j)
            {
                cin >> i;
                if (Push(s, i))
                {
                    flag = 1;
                }
            }
            if (flag = 1)
            {
                cout << "入栈操作成功！\n\n";
            }
            StackTraverse(s);
            break;
        case 3:
            cout << "取出的栈顶元素为：\n";
            if (Pop(s, t))
            {
                cout << t << endl;
            }
            StackTraverse(s);
            break;
        case 4:
            cout << "依次弹出的栈顶元素为:\n";
            while (Pop(s, t))
            {
                flag = -1;
                cout << t << "  ";
            }
            cout << endl
                 << endl;
            StackTraverse(s);
            break;
        case 0:
            return 0;
        default:
            cout << "请重新输入！\n\n";
            break;
        }
    }
    return 0;
}


  • 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
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  1. 编程实现队列的如下功能：
    （1）根据输入的队列长度n和各元素值建立一个循环顺序表表示的队列（循环队列），并输出队列中各元素值。
    （2）将数据元素e入队，并输出入队后的队列中各元素值。
    （3）将循环队列的队首元素出队，并输出出队元素的值和出队后队列中各元素值
#include <bits/stdc++.h>
using namespace std;

#define OK 1
#define ERROR 0
#define MAXQSIZE 100
typedef int QElemType;
typedef int SElemType;
typedef int Status;
//顺序队列定义
typedef struct
{
    QElemType *base;
    int front;
    int rear;
} SqQueue;
//循环队列的初始化
Status InitQueue(SqQueue &Q)
{
    Q.base = new QElemType[MAXQSIZE];
    if (!Q.base)
        exit(OVERFLOW);
    Q.front = Q.rear = 0; //头指针和尾指针置为零，队列为空
    return OK;
}
//顺序队列遍历队列
Status TarverseQueue(SqQueue Q)
{
    int cur = Q.front;
    cout << "顺序队列中元素如下：\n";
    while (cur != Q.rear)
    {
        cout << Q.base[cur] << " ";
        cur = (cur + 1) % MAXQSIZE; // 当前指针向后推移
    }
    cout << endl;
    return OK;
}
//求循环队列的长度
int QueueLength(SqQueue Q)
{
    return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}
//循环队列的入队
Status EnQueue(SqQueue &Q, QElemType e)
{
    if ((Q.rear + 1) % MAXQSIZE == Q.front)
        return ERROR;
    Q.base[Q.rear] = e;               //新元素插入队尾
    Q.rear = (Q.rear + 1) % MAXQSIZE; //队尾指针加1
    return OK;
}
//循环队列的出队
Status DeQueue(SqQueue &Q, QElemType &e)
{
    if (Q.front == Q.rear)
        return ERROR;
    e = Q.base[Q.front];                //保存队头元素
    Q.front = (Q.front + 1) % MAXQSIZE; //队头指针加1
    return OK;
}
int main()
{
    SqQueue Q;
    int select, flag = 0, i, n, j, e;
    cout << "1.初始化顺序队列\n";
    cout << "2.顺序队列的入队\n";
    cout << "3.取出队头的元素\n";
    cout << "4.顺序队列的出队\n";
    cout << "0.退出\n\n";

    while (1)
    {
        cout << "\n请选择:";
        cin >> select;
        switch (select)
        {
        case 1: //链队的初始化
            if (InitQueue(Q))
            {
                flag = 1;
                cout << "初始化对列成功\n\n";
            }
            else
                cout << "初始化队列失败\n\n";
            TarverseQueue(Q);
            break;
        case 2:
            cout << "请输入元素个数：";
            cin >> n;
            cout << "请输入" << n << "个元素：";
            for (j = 1; j <= n; j++)
            {
                cin >> i;
                if (EnQueue(Q, i))
                {
                    flag = 1;
                }
            }
            if (flag = 1)
            {
                cout << "入队操作成功！\n\n";
            }
            TarverseQueue(Q);
            break;
        case 3: //取出链队的队头元素
            cout << "取出的队头元素为：\n";
            if (DeQueue(Q, e))
            {
                cout << e << endl;
            }
            TarverseQueue(Q);
            break;
        case 4: //链队的出队
            cout << "依次弹出的队头元素为:\n";
            while (DeQueue(Q, e))
            {
                flag = -1;
                cout << e << "  ";
            }
            cout << endl
                 << endl;
            TarverseQueue(Q);
            break;
        case 0:
            return 0;
        default:
            cout << "请重新输入！\n\n";
            break;
        }
    }
    return 0;
}

  • 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
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/572813
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号