栈
栈的定义
栈(stack)是限定仅在表尾进行插入和删除操作的线性表。
允许插入和删除的一端为栈顶(top),另一端为栈底(bottom),不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表,简称 LIFO 结构。
栈的顺序存储结构
顺序栈:线性表顺序存储的简化
结构代码
typedef int ElemType; struct SqStack { ElemType data[MAXSIZE]; int top; // 栈顶指针 };
顺序栈代码实现
#include <iostream> using namespace std; #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 20 // 存储空间初始分配量 typedef int Status; typedef int ElemType; struct SqStack { ElemType data[MAXSIZE]; int top; // 栈顶指针 }; // 构造一个空栈S Status InitStack(SqStack* S) { S->top = -1; return OK; } // 把S置为空栈 Status ClearStack(SqStack* S) { S->top = -1; return OK; } // 栈S为空栈,则返回TRUE,否则返回FALSE Status StackEmpty(SqStack S) { if (S.top == -1) { return TRUE; } else { return FALSE; } } // 返回S的元素个数,即栈的长度 int StackLength(SqStack S) { return S.top + 1; } // 若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR Status GetTop(SqStack S, ElemType* e) { if (S.top == -1) { return ERROR; } *e = S.data[S.top]; return OK; } // 插入元素e为新的栈顶元素 Status Push(SqStack* S, ElemType e) { if (S->top == MAXSIZE - 1) { return ERROR; // 栈满 } S->top++; S->data[S->top] = e; return OK; } // 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR Status Pop(SqStack* S, ElemType* e) { if (S->top == -1) { return ERROR; } *e = S->data[S->top]; S->top--; return OK; } // 从栈底到栈顶依次对栈中每个元素显示 Status StackTraverse(SqStack S) { for (int i = 0; i < S.top; i++) { cout << S.data[i] << " "; } cout << endl; return OK; } int main() { SqStack s; int e; if (InitStack(&s) == OK) { for (int i = 1; i <= 10; i++) { Push(&s, i); } } cout << "栈中元素依次为:"; StackTraverse(s); Pop(&s, &e); cout << "弹出的栈顶元素:" << e << endl; cout << "栈空否(1:空 0:否):" << StackEmpty(s) << endl; GetTop(s, &e); cout << "栈顶元素:" << e << " 栈的长度为:" << StackLength(s) << endl; ClearStack(&s); cout<<"清空栈后,栈空否(1:空 0:否):"<< StackEmpty(s) << endl; system("pause"); return 0; }
两栈共享空间
数组有两个端点,两个栈有两个栈底,让一个栈的栈底为数组的始端,另一个栈为栈的末端。两个栈如果增加元素,就是两端点向中间延申。
结构代码
typedef int ElemType; struct SqDoubleStack { ElemType data[MAXSIZE]; int top1; // 栈1栈顶指针 int top2; // 栈2栈顶指针 };
两栈共享空间代码实现
#include <iostream> using namespace std; #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 20 typedef int Status; typedef int ElemType; struct SqDoubleStack { ElemType data[MAXSIZE]; int top1; // 栈1栈顶指针 int top2; // 栈2栈顶指针 }; // 构造一个空栈S Status InitStack(SqDoubleStack* S) { S->top1 = -1; S->top2 = MAXSIZE; return OK; } // 把S置为空栈 Status ClearStack(SqDoubleStack* S) { S->top1 = -1; S->top2 = MAXSIZE; return OK; } // 若栈S为空栈,则返回TRUE,否则返回FALSE Status StackEmpty(SqDoubleStack S) { if (S.top1 == -1 && S.top2 == MAXSIZE) { return TRUE; } return FALSE; } // 返回S的元素个数,即栈的长度 int StackLength(SqDoubleStack S) { return (S.top1 + 1) + (MAXSIZE - S.top2); } // 插入元素e为新的栈顶元素 Status Push(SqDoubleStack* S, ElemType e, int stackNumber) { if (S->top1 + 1 == S->top2) { return ERROR; // 满栈 } else { if (stackNumber == 1) { S->data[++S->top1] = e; } else { S->data[--S->top2] = e; } } } // 栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR Status Pop(SqDoubleStack* S, ElemType* e, int stackNumber) { if (stackNumber == 1) { if (S->top1 == -1) { return ERROR; } *e = S->data[S->top1--]; } else { if (S->top2 == MAXSIZE) { return ERROR; } *e = S->data[S->top2++]; } return OK; } Status StackTraverse(SqDoubleStack S) { for (int i = 0; i <= S.top1; i++) { cout<<S.data[i]<<" "; } for (int i = S.top2; i < MAXSIZE; i++) { cout<<S.data[i]<<" "; } cout << endl; return OK; } int main() { SqDoubleStack s; int e; if (InitStack(&s) == OK) { for (int i = 1; i <= 5; i++) { Push(&s, i, 1); } for (int i = MAXSIZE; i >= MAXSIZE - 2; i--) { Push(&s, i, 2); } } cout << "栈中元素依次为:"; StackTraverse(s); cout << "当前栈中元素有:" << StackLength(s) << endl; Pop(&s, &e, 2); cout << "弹出的栈顶元素 e = " << e << endl; cout << "栈空否(1:空 0:否):" << StackEmpty(s) << endl; for (int i = 6; i <= MAXSIZE - 2; i++) { Push(&s, i, 1); } cout << "栈中元素依次为:"; StackTraverse(s); cout << "栈满否(1:否 0:满):" << Push(&s, 1, 1) << endl; ClearStack(&s); cout << "清空栈后,栈空否(1:空 0:否):" << StackEmpty(s) << endl; system("pause"); return 0; }
栈的链式存储结构
把栈顶放在单链表的头部。
结构代码
typedef int ElemType; // 链栈结构 struct StackNode { ElemType data; struct StackNode* next; }; struct LinkStack { StackNode* top; int count; };
链栈代码实现
#include <iostream> using namespace std; #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 20 typedef int Status; typedef int ElemType; // 链栈结构 struct StackNode { ElemType data; struct StackNode* next; }; struct LinkStack { StackNode* top; int count; }; // 构造一个空栈S Status InitStack(LinkStack* S) { S->top = new StackNode(); S->top->next = NULL; S->count = 0; return OK; } // 把S置为空栈 Status ClearStack(LinkStack* S) { StackNode *p, *q; p = S->top; while (p) { q = p; p = p->next; delete q; } S->count = 0; return OK; } // 若栈S为空栈,则返回TRUE,否则返回FALSE Status StackEmpty(LinkStack S) { if (S.count == 0) { return TRUE; } return FALSE; } // 返回S的元素个数,即栈的长度 int StackLength(LinkStack S) { return S.count; } // 若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR Status GetTop(LinkStack S, ElemType* e) { if (S.count == 0) { return ERROR; } *e = S.top->data; return OK; } // 插入元素e为新的栈顶元素 Status Push(LinkStack* S, ElemType e) { StackNode* s = new StackNode(); s->data = e; s->next = S->top; S->top = s; S->count++; return OK; } // 栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR Status Pop(LinkStack* S, ElemType* e) { StackNode* p; if (StackEmpty(*S)) { return ERROR; } *e = S->top->data; p = S->top; S->top = S->top->next; delete p; S->count--; return OK; } Status StackTraverse(LinkStack S) { StackNode* p; p = S.top; while (p) { cout << p->data << " "; p = p->next; } cout << endl; return OK; } int main() { LinkStack s; int e; if (InitStack(&s) == OK) { for (int i = 1; i <= 10; i++) { Push(&s, i); } } cout << "栈中元素依次为:"; StackTraverse(s); Pop(&s, &e); cout << "弹出的栈顶元素 e = " << e << endl; cout << "栈空否(1:空 0:否):" << StackEmpty(s) << endl; GetTop(s, &e); cout << "栈顶元素: " << e << " 栈的长度为: " << StackLength(s) << endl; ClearStack(&s); cout << "清空栈后,栈空否(1:空 0:否):" << StackEmpty(s) << endl; system("pause"); return 0; }
队列
队列的定义
队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。
队列是一种先进先出的线性表,简称FIFO。允许插入的一端称为队尾,允许删除的一端称为队头。
队列的顺序存储结构:循环队列
队列顺序存储结构的缺点:元素出队列时的时间复杂度为 O(n)。
引入两个指针:front 指针指向对头元素,rear 指针指向队尾元素的下一个位置。
假溢出问题:数组存在空闲位置但发生了数组越界
所以引入了循环队列解决假溢出问题:把队列的头尾相接的顺序存储结构称为循环队列。
问题:front == rear 时队列可能为满也可能为空。
解决方法:当队列为空时,条件为:front = rear。当队列为满时,修改其条件,保留一个元素空间。
此时队列满的条件是:(rear + 1) % QueueSize == front。
计算队列长度的公式为:(rear - front + QueueSize) % QueueSize。
结构代码
typedef int ElemType; struct SqQueue { ElemType data[MAXSIZE]; int front; //头指针 int rear; //尾指针,若队列不为空,指向队列元素的下一个位置 };
循环队列的代码实现
#include <iostream> using namespace std; #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 20 typedef int Status; typedef int ElemType; //循环队列的顺序存储结构 struct SqQueue { ElemType data[MAXSIZE]; int front; //头指针 int rear; //尾指针 }; //初始化一个空队列Q Status InitQueue(SqQueue* Q) { Q->front = Q->rear = 0; return OK; } //将Q清为空队列 Status ClearQueue(SqQueue* Q) { Q->front = Q->rear = 0; return OK; } //若队列Q为空队列,则返回TRUE,否则返回FALSE Status QueueEmpty(SqQueue Q) { if (Q.front == Q.rear) { return TRUE; } return FALSE; } //返回Q的元素个数,也就是队列的当前长度 int QueueLength(SqQueue Q) { return (Q.rear - Q.front + MAXSIZE) % MAXSIZE; } //若队列不空,则用e返回Q的队头元素 Status GetHead(SqQueue Q, ElemType* e) { if (Q.front == Q.rear) { return ERROR; } *e = Q.data[Q.front]; return OK; } //若队列未满,则插入元素e为Q新的队尾元素 Status EnQueue(SqQueue* Q, ElemType e) { if ((Q->rear + 1) % MAXSIZE == Q->front) { return ERROR; } Q->data[Q->rear] = e; //元素e赋值给队尾 Q->rear = (Q->rear + 1) % MAXSIZE; //若到最后则转到数组头部 return OK; } //若队列不空,则删除Q中队头元素,用e返回其值 Status DeQueue(SqQueue* Q, ElemType* e) { if (Q->front == Q->rear) { return ERROR; } *e = Q->data[Q->front]; Q->front = (Q->front + 1) % MAXSIZE; return OK; } //从队头到队尾依次对队列Q中每个元素输出 Status QueueTraverse(SqQueue Q) { int i = Q.front; while ((i + Q.front) != Q.rear) { cout << Q.data[i] << " "; i = (i + 1) % MAXSIZE; } cout << endl; return OK; } int main() { Status j; int l; ElemType d; SqQueue Q; InitQueue(&Q); cout << "初始化队列后,队列空否?(1:空 0:否): " << QueueEmpty(Q) << endl; for (int i = 0; i < MAXSIZE - 1; i++) { EnQueue(&Q, i); } cout << "队列长度为: " << QueueLength(Q) << endl; cout << "现在队列空否?(1:空 0:否): " << QueueEmpty(Q) << endl; cout << "连续" << MAXSIZE << "次由队头删除元素,队尾插入元素: " << endl; for (int i = 1; i <= MAXSIZE; i++) { DeQueue(&Q, &d); cout << "删除的元素是: " << d << " 插入的元素: " << i + 100 << endl; d = i + 100; EnQueue(&Q, d); } l = QueueLength(Q); cout << "现在队列中的元素为: " << endl; QueueTraverse(Q); if (l - 2 > 0) { cout << "现在由队头删除" << l - 2 << "个元素" << endl; } while (QueueLength(Q) > 2) { DeQueue(&Q, &d); cout << "删除的元素值为" << d << endl; } j = GetHead(Q, &d); if (j) { cout << "现在队头元素为: " << d << endl; } ClearQueue(&Q); cout << "清空队列后, 队列空否?(1:空 0:否): " << QueueEmpty(Q) << endl; }
队列的链式存储结构
只允许尾进头出的线性表的单链表,简称链队列。
结构代码
typedef int ElemType; struct QNode { //结点结构 ElemType data; QNode* next; }; struct LinkQueue { QNode* front; //队头指针 QNode* rear; //队尾指针 };
链队列的代码实现
#include <iostream> using namespace std; #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 20 typedef int Status; typedef int ElemType; struct QNode { //结点结构 ElemType data; QNode* next; }; struct LinkQueue { QNode* front; //队头指针 QNode* rear; //队尾指针 }; //构造一个空队列Q Status InitQueue(LinkQueue* Q) { Q->front = Q->rear = new QNode(); Q->front->next = NULL; return OK; } //销毁队列Q Status DestroyQueue(LinkQueue* Q) { while (Q->front) { Q->rear = Q->front->next; delete Q->front; Q->front = Q->rear; } return OK; } //将Q清为空队列 Status ClearQueue(LinkQueue* Q) { QNode* p, * q; Q->rear = Q->front; p = Q->front->next; Q->front->next = NULL; while (p) { q = p; p = p->next; delete q; } return OK; } //若Q为空队列,则返回TRUE,否则返回FALSE Status QueueEmpty(LinkQueue Q) { if (Q.front == Q.rear) { return TRUE; } return FALSE; } //求队列的长度 int QueueLength(LinkQueue Q) { int i = 0; QNode* p = Q.front; while (p != Q.rear) { i++; p = p->next; } return i; } //队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR Status GetHead(LinkQueue Q, ElemType* e) { if (Q.front == Q.rear) { return ERROR; } *e = Q.front->next->data; return OK; } //插入元素e为Q的新的队尾元素 Status EnQueue(LinkQueue* Q, ElemType e) { QNode* p = new QNode(); p->data = e; p->next = NULL; Q->rear->next = p; Q->rear = p; return OK; } //队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR Status DeQueue(LinkQueue* Q, ElemType* e) { QNode* p; if (Q->front == Q->rear) { return ERROR; } p = Q->front->next; *e = p->data; Q->front->next = p->next; if (Q->rear == p) { Q->rear = Q->front; //若队头就是队尾,则删除后将rear指向头结点 } delete p; return OK; } //将队列元素从头到尾输出 Status QueueTraverse(LinkQueue Q) { QNode* p = Q.front->next; while (p) { cout << p->data << " "; p = p->next; } cout << endl; return OK; } int main() { int i; ElemType d; LinkQueue q; i = InitQueue(&q); if (i) { cout << "成功地构造了一个空队列!" << endl; } cout << "是否空队列?(1:空 0:否): " << QueueEmpty(q) << endl; cout << "队列的长度为: " << QueueLength(q) << endl; EnQueue(&q, 1); EnQueue(&q, 2); EnQueue(&q, 3); cout << "插入3个元素(1,2,3)后,队列的长度为: " << QueueLength(q) << endl; cout << "是否空队列?(1:空 0:否): " << QueueEmpty(q) << endl; cout << "队列的元素依次为:"; QueueTraverse(q); i = GetHead(q, &d); if (i == OK) { cout << "队头元素是:" << d << endl; } DeQueue(&q, &d); cout << "删除了队头元素: " << d << endl; i = GetHead(q, &d); if (i == OK) { cout << "新的队头元素是:" << d << endl; } ClearQueue(&q); cout << "清空队列后, q.front = " << q.front << " q.rear = " << q.rear << " q.front->next = " << q.front->next << endl; DestroyQueue(&q); cout << "销毁队列后, q.front = " << q.front << " q.rear = " << q.rear << endl; system("pause"); return 0; }
标签:Status,OK,队列,ElemType,int,front,return From: https://www.cnblogs.com/kyzh-lhl/p/16711769.html