C++数据结构与算法（栈和队列）

柔光的暖阳◎ 2021-11-09 23:10 360阅读 0赞

**目录**

1栈

1.1栈定义

1.2栈的表示和实现

1.2.1顺序栈

1.1.2链栈

1.3栈的应用——括号匹配问题

2队列

2.1队列的定义

2.2队列的表示和实现

2.2.1链队列

2.2.2循环队列

2.3队列的应用——约瑟夫环问题

--------------------

# 1栈 #

## 1.1栈定义 ##

> **栈（stack）**作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行，通常将表中允许进行插入、删除操作的一端称为栈顶（Top），因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。同时表的另一端被称为栈底（Bottom）。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。

> 栈有时叫做LIFO（后进先出）表。一般的模型是，存在某个元素位于栈顶，而该元素是唯一的可见元素。

![20190801201540797.png][]

## 1.2栈的表示和实现 ##

> 栈作为一种特殊的线性表，在计算机中主要有两种基本的存储结构：**顺序存储结构**和**链式存储结构**。我们称顺序存储的栈为**顺序栈**，链式存储的栈为**链栈**。

### 1.2.1顺序栈 ###

> 顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈操作的特殊性，还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置。通常以top=-1表示空栈。顺序栈的存储结构的进栈和出栈过程如下图：

![20190801203355364.png][]

/*顺序栈实现*/
    #include<iostream>
    using namespace std;
    
    //元素elem进栈
    int push(int* a, int top, int elem){
    	a[++top] = elem;
    	cout << "入栈元素：" << a[top] << endl;
    	return top;
    }
    //数据元素出栈
    int pop(int * a, int top){
    	if (top == -1) {
    		printf("空栈\n");
    		return -1;
    	}
    	printf("弹栈元素：%d\n", a[top]);
    	top--;
    	return top;
    }
    int main() {
    	int a[100];
    	int top = -1;
    	top = push(a, top, 1);
    	top = push(a, top, 2);
    	top = push(a, top, 3);
    	top = push(a, top, 4);
    	top = pop(a, top);
    	top = pop(a, top);
    	top = pop(a, top);
    	top = pop(a, top);
    	top = pop(a, top);
    	system("pause");
    	return 0;
    }

结果：

![20190801213946499.png][]

### 1.1.2链栈 ###

> 链栈即采用链表作为存储结构实现的栈。由于栈的插入和删除操作仅限在表头仅限，所以链表的表头指针就作为栈顶指针。

链栈示意图：

![20190801213333266.png][]

链栈的实现：

#include<iostream>
    using namespace std;
    
    typedef struct lineStack{
    	int data;
    	struct lineStack * next;
    }lineStack;
    
    lineStack* push(lineStack * stack, int a){
    	lineStack * line = (lineStack*)malloc(sizeof(lineStack));
    	line->data = a;
    	line->next = stack;
    	stack = line;
    	cout << "入栈元素：" << line->data << endl;
    	return stack;
    }
    
    lineStack * pop(lineStack * stack){
    	if (stack) {
    		lineStack * p = stack;
    		stack = stack->next;
    		printf("弹栈元素：%d ", p->data);
    		if (stack) {
    			printf("栈顶元素：%d\n", stack->data);
    		}
    		else{
    			printf("栈已空\n");
    		}
    		free(p);
    	}
    	else{
    		printf("栈内没有元素\n");
    		return stack;
    	}
    	return stack;
    }
    
    /*求栈长*/
    int lengthStack_L(lineStack *S)
    
    {
    	lineStack *q;
    	int count;
    	q = S;
    	count = 0;
    	while (q)
    	{
    		++count;
    		q = q->next;
    	}
    	return count;
    }
    
    int main() {
    	int len;
    	lineStack * stack = NULL;
    	stack = push(stack, 1);
    	stack = push(stack, 2);
    	stack = push(stack, 3);
    	stack = push(stack, 4);
    	len = lengthStack_L(stack);
    	cout << "栈链长度为：" << len << endl;
    	stack = pop(stack);
    	stack = pop(stack);
    	stack = pop(stack);
    	stack = pop(stack);
    	stack = pop(stack);
    	system("pause");
    	return 0;
    }

结果：

![20190801214045989.png][]

## 1.3栈的应用——括号匹配问题 ##

#include <iostream>
    #include <stack>
    #include <string>
    using namespace std;
    
    bool paren(const std::string &str)
    {
    	std::stack<char> s;
    	for (auto i = 0; i < str.size(); i++)
    	{
    		switch (str[i])
    		{
    		case '(':s.push(str[i]); break;
    		case '[':s.push(str[i]); break;
    		case '{':s.push(str[i]); break;
    		case ')':
    			if (s.top() != '(')
    				return false;
    			else
    				s.pop(); break;
    		case ']':
    			if (s.top() != '[')
    				return false;
    			else
    				s.pop(); break;
    		case '}':
    			if (s.top() != '{')
    				return false;
    			else
    				s.pop(); break;
    
    		default:
    			break;
    		}
    	}
    	return s.empty();
    }
    
    int main()
    {
    	//string strBuf = "()[]{}[()]";
    	char strBuf[50];
    	cin >> strBuf;
    	cout << endl;
    	cout << "The string is : " << strBuf << " ";
    	if (paren(strBuf))
    		cout << "括号匹配";
    	else
    		cout << "括号不匹配";
    	cout << endl;
    	system("pause");
    	return 0;
    }

结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70][]

![20190801220404580.png][]

# 2队列 #

## 2.1队列的定义 ##

> **队列（Queue）**是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出（FIFO）的特性。

## 2.2队列的表示和实现 ##

> 与线性表类似，队列也可以有两种存储表示，即**顺序表示**和**链式表示**。

### 2.2.1链队列 ###

> 用链表表示的队列简称为链队列。如下图所示，**队头指针始终指向头节点，队尾指针指向当前最后一个元素。**空的链队列的队头指针和队尾指针均指向头节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 1][]

>  *  初始化队列时，令front=rear=0；
>  *  入队时，直接将新元素送入尾指针rear，所指的单元，然后尾指针增加1；
>  *  出队时，直接取出队头指针front所指的元素，然后头指针增加1.

> 显然，在非空顺序队列中，队头指针始终指向当前的队头元素，而队尾指针始终指向真正队尾元素后面的单元。当rear== MAXSIZE时，认为队满，因为随着部分元素的出队，数组前面会出现一些空单元。由于只能在队尾入队，使得这些空单元无法使用。这种现象被称为**假溢出**，真正队满的条件时rear-front=MAXSIZE.

顺序队列的实现：

#include<iostream>
    using namespace std;
    #define N 4
    
    int in(int *s, int rear, int x)
    {
    	rear = (rear + 1) % (N + 1);
    	s[rear] = x;
    	return rear;
    }
    
    int out(int front)
    {
    	front = (front + 1) % (N + 1);
    	return front;
    
    }
    
    int main()
    {
    	int i;
    	int Q[N + 1] = { 10, 20, 30, 40, 50 };
    	int front, rear;
    	int *s;
    	s = (int *)malloc((N)*sizeof(int));
    	front = 0;
    	rear = 0;
    	cout << "此时的front值为：" << front << ",rear的值为：" << rear << endl;
    	for (i = 0; i<N + 1; i++)
    	{
    		//Q[i]入队
    		if ((rear + 1) % (N + 1) == front)
    		{
    			printf("队已满,%d已出队\n", Q[front]);
    			front = out(front);
    			printf("此时的front和rear值为：%d,%d\n", front, rear);
    		}
    		rear = in(s, rear, Q[i]);
    		printf("%d已入队\n", Q[i]);
    		printf("此时的front和rear值为：%d,%d\n", front, rear);
    	}
    	//Q[i]出队
    	while (front != rear)
    	{
    		front = out(front);
    		printf("%d已出队\n", s[front]);
    		printf("此时的front和rear值为：%d,%d\n", front, rear);
    	}
    	system("pause");
    	return 0;
    }

链队列的实现：

# include <iostream>
    using namespace std;
    
    typedef int ElemType;
    
    typedef struct QNode
    {
    	ElemType data;
    	QNode *next;
    
    }QNode, *QueuePtr;      //节点
    
    //单链队列
    typedef struct
    {
    	QueuePtr front;     //队头指针
    	QueuePtr rear;		//队尾指针
    }LinkQueue;
    
    
    class MyLinkQueue
    {
    public:
    	void InitQueue();		//初始化队列
    	void DestroyQueue();		//销毁队列
    	void ClearQueue();		//清空队列
    	bool QueueEmpty();		//队列是否为空
    	int QueueLength();		//队列长度
    	void Enqueue(ElemType val);	//在队尾插入数据
    	void DeQueue(ElemType & val);	//删除队头
    	void Print();			//从头到尾打印
    
    private:
    	LinkQueue q;
    };
    
    //初始化队列
    void MyLinkQueue::InitQueue()
    {
    	q.front = q.rear = (QueuePtr)malloc(sizeof(QNode));
    	if (!q.front)
    	{
    		//如果分配失败
    		cout << "初始化失败" << endl;
    		return;
    	}
    	q.front->next = NULL;
    }
    
    //销毁队列
    void MyLinkQueue::DestroyQueue()
    {
    	while (q.front)
    	{
    		q.rear = q.front->next;
    		free(q.front);
    		q.front = q.rear;
    	}
    }
    //在队尾插入数据
    void MyLinkQueue::Enqueue(ElemType val)
    {
    	QueuePtr ptr = (QueuePtr)malloc(sizeof(QNode));
    	if (!ptr)
    	{
    		//如果分配失败
    		cout << "节点分配失败" << endl;
    		return;
    	}
    	ptr->data = val;
    	ptr->next = NULL;
    	q.rear->next = ptr;
    	q.rear = ptr;
    }
    //删除队头，并返回当前队头的值
    void MyLinkQueue::DeQueue(ElemType & val)
    {
    	if (q.front == q.rear)
    	{
    		val = -1;
    		return;
    	}
    	QueuePtr p;
    	val = q.front->next->data;
    	if (q.front->next == q.rear){//队列只有一个元素
    		p = q.rear;
    		q.rear = q.front;
    		q.front->next = NULL;
    	}
    	else{
    		p = q.front->next;
    		q.front->next = p->next;
    		p->next = NULL;
    	}
    	free(p);
    }
    
    //打印
    void MyLinkQueue::Print()
    {
    	if (q.front == q.rear)
    	{
    		cout << "队列为空" << endl;
    		return;
    	}
    	QueuePtr ptr = q.front->next;
    	while (ptr != q.rear)
    	{
    		cout << ptr->data << endl;
    		ptr = ptr->next;
    	}
    	cout << ptr->data << endl;
    }
    
    //清空队列
    void MyLinkQueue::ClearQueue()
    {
    	DestroyQueue();
    	InitQueue();
    }
    
    
    //队列是否为空
    bool MyLinkQueue::QueueEmpty()
    {
    	if (q.front == q.rear)
    		return true;
    	else
    		return false;
    }
    //队列长度
    int MyLinkQueue::QueueLength()
    {
    	if (q.front == q.rear)
    		return 0;
    	QueuePtr ptr = q.front;
    	int index = 0;
    	do
    	{
    		index++;
    		ptr = ptr->next;
    	} while (ptr != q.rear);
    	return index;
    }
    
    int main()
    {
    	MyLinkQueue q;
    	bool flag = q.QueueEmpty();
    	q.InitQueue();
    	q.Enqueue(1);
    	q.Enqueue(2);
    	q.Enqueue(3);
    	q.Enqueue(4);
    	q.Enqueue(5);
    	q.Enqueue(6);
    	q.Enqueue(7);
    	int len = q.QueueLength();
    	q.Print();
    	int val;
    	q.DeQueue(val);
    	q.DeQueue(val);
    	cout << "取出两个队头后打印" << endl;
    	q.Print();
    	q.ClearQueue();
    	q.Print();
    	cout << "入队：" << endl;
    	q.Enqueue(1);
    	q.Enqueue(2);
    	q.Enqueue(3);
    	q.Enqueue(4);
    	q.Print();
    	system("pause");
    	return 0;
    }

![20190802102200667.png][]

### 2.2.2循环队列 ###

**为了解决假溢出现象并使得队列空间得到充分利用，引出循环队列。**

> 循环队列是队列的一种顺序表示和实现方法：将顺序队列的数组看成是一个环状的空间，即规定最后一个单元的后继为第一个单元。如下图所示，**队头指针始终指向当前的队头元素，而队尾指针始终指向真正队尾元素后面的单元。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 2][]

> 借助于取模（求余）运算，可以自动实现队尾指针、队头指针的循环变化。
> 
>  *  进队操作时，队尾指针的变化是：rear=(rear+1) mod MAXSIZE；
>  *  出队操作时，队头指针的变化是：front=(front+1) mod MAXSIZE.
> 
> **循环队列“满”的条件为：（rear+1）mod MAXSIZE = front.**
> 
> **判队空的条件依旧是：rear=front.**

循环队列的实现：

# include <iostream>
    using namespace std;
    
    #define MAX_QUEUE_SIZE 100
    typedef int ElemType;
    
    typedef struct QNode
    {
    	ElemType data;
    	QNode *next;
    
    }QNode, *QueuePtr;      //节点
    
    //循环队列
    typedef struct{
    	ElemType *base;
    	int front;
    	int rear;
    }SqQueue;
    
    class CircularQueue
    {
    public:
    	void InitQueue();			//初始化队列
    	void DestroyQueue();		//销毁队列
    	void ClearQueue();			//清空队列
    	bool QueueEmpty();			//队列是否为空
    	int QueueLength();			//队列长度
    	void Enqueue(ElemType val);	//在队尾插入数据
    	void DeQueue(ElemType & val);	//删除队头
    	void Print();					//从头到尾打印
    
    private:
    	SqQueue q;
    };
    
    //初始化队列
    void CircularQueue::InitQueue()
    {
    	q.base = (ElemType *)malloc(sizeof(ElemType)* MAX_QUEUE_SIZE);
    	if (!q.base)
    	{
    		//如果分配失败
    		cout << "初始化失败" << endl;
    		return;
    	}
    	q.front = q.rear = 0;
    }
    
    //销毁队列
    void CircularQueue::DestroyQueue()
    {
    	free(q.base);
    	q.front = q.rear = 0;
    }
    //在队尾插入数据
    void CircularQueue::Enqueue(ElemType val)
    {
    	if ((q.rear + 1) % MAX_QUEUE_SIZE == q.front)
    	{
    		cout << "队列已满！" << endl;
    		return;
    	}
    	q.base[q.rear] = val;
    	q.rear = (q.rear + 1) % MAX_QUEUE_SIZE;
    	return;
    }
    //删除队头，并返回当前队头的值
    void CircularQueue::DeQueue(ElemType & val)
    {
    	if (q.front == q.rear)
    	{
    		cout << "队列为空！" << endl;
    		return;
    	}
    	val = q.base[q.front];
    	q.front = (q.front + 1) % MAX_QUEUE_SIZE;
    	return;
    }
    
    //打印
    void CircularQueue::Print()
    {
    	if (q.front == q.rear)
    	{
    		cout << "队列为空" << endl;
    		return;
    	}
    	for (int i = q.front; i < q.rear; i++)
    		cout << q.base[i] << endl;
    	return;
    }
    
    //清空队列
    void CircularQueue::ClearQueue()
    {
    	DestroyQueue();
    	InitQueue();
    }
    
    
    //队列是否为空
    bool CircularQueue::QueueEmpty()
    {
    	if (q.front == q.rear)
    		return true;
    	else
    		return false;
    }
    //队列长度
    int CircularQueue::QueueLength()
    {
    	return (q.rear - q.front + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
    }
    
    int main()
    {
    	CircularQueue q;
    	bool flag = q.QueueEmpty();
    	q.InitQueue();
    	q.Enqueue(1);
    	q.Enqueue(2);
    	q.Enqueue(3);
    	q.Enqueue(4);
    	q.Enqueue(5);
    	q.Enqueue(6);
    	q.Enqueue(7);
    	int len = q.QueueLength();
    	q.Print();
    	int val;
    	q.DeQueue(val);
    	q.DeQueue(val);
    	cout << "取出两个队头后打印" << endl;
    	q.Print();
    	q.ClearQueue();
    	q.Print();
    	cout << "入队：" << endl;
    	q.Enqueue(1);
    	q.Enqueue(2);
    	q.Enqueue(3);
    	q.Enqueue(4);
    	q.Print();
    	system("pause");
    	return 0;
    }

## 2.3队列的应用——约瑟夫环问题 ##

#include<iostream>
    using namespace std;
    
    #define N 10
    void JonesPlus(int Q[], int key)
    {
    	int front, rear;
    	int i;
    	front = 0;
    	rear = N;
    	while (front - rear)
    	{
    		for (i = 0; i<key - 1; i++)
    		{
    			front = (front + 1) % (N + 1);
    			rear = (rear + 1) % (N + 1);
    			Q[rear] = Q[front];
    		}
    		front = (front + 1) % (N + 1);
    		printf("%d已出队\n", Q[front]);
    	}
    }
    
    int main()
    {
    	int i;
    	int Q[N + 1];
    	for (i = 1; i<N + 1; i++)
    		Q[i] = i;
    	JonesPlus(Q, 3);
    	system("pause");
    	return 0;
    }

![2019080210511675.png][]

[20190801201540797.png]: /images/20211109/fa05d4d7b1e849daa62ddec917e7310e.png
[20190801203355364.png]: /images/20211109/648cd3c218564ffb956140560c366f70.png
[20190801213946499.png]: /images/20211109/036e5165ce494bb3bb5ea32548a5e092.png
[20190801213333266.png]: /images/20211109/c62d689cc57c40389a7d1f39dc065ef8.png
[20190801214045989.png]: /images/20211109/3a6ae2ca34f0406886194f69cca5829a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70]: /images/20211109/f13447fe80ce44fc8012b90c1bc327fd.png
[20190801220404580.png]: /images/20211109/49eb40279e4c4fe8ab692613e95ca3c6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 1]: /images/20211109/f365fa1f0a224fa4b7f5453a10d5c5a5.png
[20190802102200667.png]: /images/20211109/1a3caf609e1448999daec181b79ffa39.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 2]: /images/20211109/6e3443a4fe894f8a8e392fbc4207b8eb.png
[2019080210511675.png]: /images/20211109/5ebc4a0bda054ef394159936d19b02d8.png