文章目录
- 前言
- 一、栈和队列的实现
- 1.栈的具体实现
- 2.循环顺序队列的具体实现
- 二、栈和队列总结
- 总结
前言
T_T此专栏用于记录数据结构及算法的（痛苦）学习历程，便于日后复习（这种事情不要啊）。所用教材为《数据结构 C语言版 第2版》严蔚敏。
一、栈和队列的实现
在栈和队列中我们学习了栈和队列的概念和定义（学废了），下面给出其具体实现。
1.栈的具体实现
#include <iostream>
#include <string.h>
using namespace std;
#define maxsize 10
#define ok 1
#define fail 0
#define true 1
#define false 0
#define Not_Exist -1
#define overflow -2
typedef int Status;
typedef int Elemtype;
typedef struct {
Elemtype* bottom;
Elemtype* top;
int Stacksize;
}SqStack;
//初始化，创建顺序栈
Status CreatStack(SqStack& s)
{
s.bottom = new Elemtype[maxsize];
if (!s.bottom)return fail;
s.top = s.bottom;
s.Stacksize = maxsize;
return ok;
}
//入栈
Status Push(SqStack& s,Elemtype e)
{
if (s.top - s.bottom == s.Stacksize)return overflow;
*s.top = e;
s.top++;
return ok;
}
//出栈
Status Pop(SqStack& s, Elemtype& e)
{
if (s.top == s.bottom)return overflow;
s.top--;
e = *s.top;
return ok;
}
//得到栈顶元素
Status Gettop(SqStack s, Elemtype& e)
{
if (s.top == s.bottom)return overflow;
e = *(s.top-1);
return ok;
}
//销毁顺序栈
Status Destorystack(SqStack& s)
{
delete[] s.bottom;
return ok;
}
//清空顺序栈，逻辑上，实际空间中仍然存储着之前的元素
Status Clearstack(SqStack& s)
{
s.top = s.bottom;
return ok;
}
//检测顺序栈是否空
Status Stackempty(SqStack s)
{
if (s.bottom == s.top)
return true;
return false;
}
//检测顺序栈是否满
Status Stackfull(SqStack s)
{
if (s.top - s.bottom == s.Stacksize)
return true;
return false;
}
//返回顺序栈已用长度，即入栈元素个数
Status Stacklength(SqStack s)
{
return s.top-s.bottom;
}
SqStack s;
Elemtype e;
int n;
int main()
{
CreatStack(s);
Push(s, 'A');
Push(s, 'b');
Push(s, 'C');
Gettop(s, e); cout << e << endl;
Pop(s, e); cout << e << endl;
cout << Stacklength(s) << endl;
cout << Stackfull(s) << endl;
cout << Clearstack(s) << endl;
cout << Stackempty(s) << endl;
return 0;
}
测试现象：
2.循环顺序队列的具体实现
#include <iostream>
#include <string.h>
using namespace std;
#define maxsize 10
#define ok 1
#define fail 0
#define true 1
#define false 0
#define Not_Exist -1
#define overflow -2
typedef int Status;
typedef int Elemtype;
typedef struct {
Elemtype* base;
int front;
int rear;
int Queuesize;
}SqQueue;
//初始化，创建循环顺序队列
Status CreatQueue(SqQueue& q)
{
q.base = new Elemtype[maxsize];
if (!q.base)return fail;
q.rear = q.front = 0;
q.Queuesize = maxsize;
return ok;
}
//入队
Status EntryQ(SqQueue& q, Elemtype e)
{
if ((q.rear + 1) % q.Queuesize == q.front)return overflow;
q.base[q.rear] = e;
q.rear++;
q.rear %= q.Queuesize;
return ok;
}
//出队
Status OutQ(SqQueue& q, Elemtype& e)
{
if (q.front == q.rear)return overflow;
e = q.base[q.front];
q.front++;
q.front %= q.Queuesize;
return ok;
}
//得到循环顺序队列队头元素
Status Getfront(SqQueue q, Elemtype& e)
{
if (q.front == q.rear)return overflow;
e = q.base[q.front];
return ok;
}
//销毁循环顺序队列
Status DestoryQueue(SqQueue& q)
{
delete[] q.base;
return ok;
}
//清空循环顺序队列，逻辑上，实际空间中仍然存储着之前的元素
Status ClearQueue(SqQueue& q)
{
q.front = q.rear = 0;
return ok;
}
//检测循环顺序队列是否空
Status Queueempty(SqQueue q)
{
if (q.front == q.rear)
return true;
return false;
}
//检测循环顺序队列是否满
Status Queuefull(SqQueue q)
{
if ((q.rear + 1) % q.Queuesize == q.front)
return true;
return false;
}
//返回循环顺序队列已用长度，即入队元素个数
Status Queuelength(SqQueue q)
{
return (q.rear - q.front + q.Queuesize) % q.Queuesize;
}
SqQueue q;
Elemtype e;
int main()
{
CreatQueue(q);
EntryQ(q, 'A');
EntryQ(q, 'b');
EntryQ(q, 'C');
Getfront(q, e); cout << e << endl;
OutQ(q, e); cout << e << endl;
cout << Queuelength(q) << endl;
cout << Queuefull(q) << endl;
cout << ClearQueue(q) << endl;
cout << Queueempty(q) << endl;
return 0;
}
测试现象：
二、栈和队列总结
(1)栈是限定仅在表尾进行插入或删除的线性表，又称为后进先出（LIFO）的线性表。栈有两种存储表示，顺序表示（顺序栈）和链式表示（链栈）。栈的主要操作是进栈和出栈，对于顺序栈的进栈和出栈操作要注意判断栈满或栈空。
(2) 队列是一种先进先出（FIFO）的线性表。它只允许在表的一端进行插入， 而在另一端删除元素。队列也有两种存储表示，顺序表示（循环队列）和链式表示（链队）。队列的主要操作是进队和出队，对于顺序的循环队列的进队和出队操作要注意判断队满或队空。凡是涉及队头或队尾指针的修改都要将其对队列最大容量求模。
总结
路漫漫其修远兮，吾将上下而摆烂。
有任何疑问和补充，欢迎交流。（但我显然不会）
