栈的顺序存储结构实现
参考代码(使用数组实现)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
typedef int ElemType;
typedef int Status;
typedef struct
{
ElemType data[MAXSIZE];
int top;
}sqStack;
//四个基础操作
Status InitStack(sqStack *s); //初始化操作,建立一个空栈
Status ClearStack(sqStack *s); //将栈清空
Status StackEmpty(sqStack s); //若栈存在,返回true,否则返回false
int StackLength(sqStack s); //返回栈S的元素个数
Status GetTop(sqStack s, ElemType *e); //若是栈存在且非空,用e返回S的栈顶元素
Status Push(sqStack *s, ElemType e); // 若是栈存在,则插入新的元素e到栈S中并成为栈顶元素
Status Pop(sqStack *s, ElemType *e); //若是栈存在且非空,删除栈顶元素,并用e返回其值
Status DestroyStack(sqStack *s); //若是栈存在,则销毁他
int main()
{
sqStack sk;
int i;
ElemType e;
//初始化空栈
printf("1.InitStack\n");
InitStack(&sk);
printf("2.Push 1-5\n");
for (i = 1; i <= 5; i++)
Push(&sk, i);
printf("3.Pop number for three times\n");
for (i = 1; i <= 3;i++)
{
Pop(&sk, &e);
printf("Pop %d: %d\n",i, e);
}
GetTop(sk, &e);
printf("4.Get Top:%d\n",e);
printf("5.Push 6-10\n");
for (i = 6; i <= 10; i++)
Push(&sk, i);
printf("6.Get stack length:%d\n", StackLength(sk));
printf("7.Pop number for six times\n");
for (i = 1; i <= 6; i++)
{
Pop(&sk, &e);
printf("Pop %d: %d\n",i, e);
}
if (!StackEmpty(sk))
{
printf("8.Stack is not Empty\n");
ClearStack(&sk);
printf("9.Stack is Clear\n");
}
printf("10.Stack Empty:%d\n",StackEmpty(sk));
printf("11.destroy Stack");
DestroyStack(&sk);
system("pause");
return 0;
}
//初始化操作,建立一个空栈
Status InitStack(sqStack *s)
{
if (!s)
return ERROR;
memset(s->data, 0, MAXSIZE*sizeof(ElemType));
s->top = -1;
return OK;
}
//将栈清空,将栈顶指针移动到栈底即可,数据不需要清空,数据入栈会覆盖
Status ClearStack(sqStack *s)
{
if (!s)
return ERROR;
s->top = -1;
return OK;
}
//若栈存在,返回true,否则返回false
Status StackEmpty(sqStack s)
{
if (s.top == -1)
return OK;
return FALSE;
}
//返回栈S的元素个数
int StackLength(sqStack s)
{
return s.top+1;
}
//若是栈存在且非空,用e返回S的栈顶元素,注意:只是获取栈顶数据,不出栈
Status GetTop(sqStack s, ElemType *e)
{
if (s.top = -1||!e)
return ERROR;
*e = s.data[s.top];
return OK;
}
//入栈操作:若是栈存在,则插入新的元素e到栈S中并成为栈顶元素
Status Push(sqStack *s, ElemType e)
{
if (s->top + 1 == MAXSIZE||!s)
return ERROR;
s->top++;
s->data[s->top] = e;
return OK;
}
//若是栈存在且非空,删除栈顶元素(只需要将栈顶指针下移即可),并用e返回其值
Status Pop(sqStack *s, ElemType *e)
{
if (s->top == -1||!s||!e)
return ERROR;
*e = s->data[s->top];
s->top--;
return OK;
}
//若是栈存在,则销毁他,数据清空
Status DestroyStack(sqStack *s)
{
if (!s)
return ERROR;
memset(s->data, 0, MAXSIZE*sizeof(ElemType));
s->top = -1;
return OK;
}
队列的顺序存储结构实现
顺序队列:队头指针不变
上面的顺序队列:在出队时需要移动顺序队列中所有的元素,时间复杂度O(n),需要改进。
顺序队列:队头指针移动
缺点:队尾指针逐渐增加,而队头也增加,那么数组的可用空间会减少。前面的红色区域会造成空间浪费。
顺序队列:循环队列
成功解决上面两种情况的缺点,不足之处是对于数组溢出没有办法。
参考代码(使用数组实现)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 10
typedef int ElemType;
typedef int Status;
//设置队列的结构体
typedef struct
{
ElemType data[MAXSIZE];
int front; //队头下标
int rear; //队尾下标,若队列不为空,指向队列元素的下一个位置
}sqQueue;
//四个基础操作
Status InitQueue(sqQueue *Q); //初始化操作,建立一个空队列Q
Status ClearQueue(sqQueue *Q);//将队列清空
Status QueueEmpty(sqQueue Q); //若队列为空,返回true,否则返回false
int QueueLength(sqQueue Q); //返回队列Q的元素个数
Status GetHead(sqQueue Q, ElemType *e); //若是队列存在且非空,用e返回Q的队头元素
Status EnQueue(sqQueue *Q, ElemType e); //若是队列存在,则插入新的元素e入队为队尾
Status DeQueue(sqQueue *Q, ElemType *e); //若是队列存在且非空,进行出队操作,用e接收数据
Status DestroyQueue(sqQueue *Q); //若是队列存在,则销毁他
int main()
{
sqQueue lq;
ElemType e;
int i;
//初始化一个空的队列
InitQueue(&lq);
printf("2.EnQueue 1-5\n");
for (i = 1; i <= 5; i++)
EnQueue(&lq, i);
printf("3.DeQueue number for three times\n");
for (i = 1; i <= 3; i++)
{
DeQueue(&lq, &e);
printf("DeQueue %d: %d\n", i, e);
}
GetHead(lq, &e);
printf("4.Get Head:%d\n", e);
printf("5.EnQueue 6-10\n");
for (i = 6; i <= 10; i++)
EnQueue(&lq, i);
printf("6.Get queue length:%d\n", QueueLength(lq));
printf("7.DeQueue number for six times\n");
for (i = 1; i <= 6; i++)
{
DeQueue(&lq, &e);
printf("DeQueue %d: %d\n", i, e);
}
if (!QueueEmpty(lq))
{
printf("8.Queue is not Empty\n");
ClearQueue(&lq);
printf("9.Queue is Clear\n");
}
printf("10.Queue Empty:%d\n", QueueEmpty(lq));
printf("11.destroy Queue");
DestroyQueue(&lq);
system("pause");
return 0;
}
//初始化操作,建立一个空队列Q
Status InitQueue(sqQueue *Q)
{
if (!Q)
return ERROR;
Q->front = Q->rear = 0; //都指向下标0
return OK;
}
//将队列清空,和初始化一样即可
Status ClearQueue(sqQueue *Q)
{
if (!Q)
return ERROR;
Q->front = Q->rear = 0; //都指向下标0
return OK;
}
//若队列为空,返回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 (!e || QueueEmpty(Q))
return ERROR;
*e = Q.data[Q.front];
return OK;
}
//若是队列存在,且未满,则插入新的元素e入队为队尾
Status EnQueue(sqQueue *Q, ElemType e)
{
if (!Q || (Q->rear + 1) % MAXSIZE == Q->front) //判断队满
return ERROR;
Q->data[Q->rear] = e; //为队尾赋值
Q->rear = (Q->rear + 1) % MAXSIZE; //将队尾下标下移
return OK;
}
//若是队列存在且非空,进行出队操作,用e接收数据
Status DeQueue(sqQueue *Q, ElemType *e)
{
if (!Q || !e || QueueEmpty(*Q))
return ERROR;
*e = Q->data[Q->front];
Q->front = (Q->front + 1) % MAXSIZE;
return OK;
}
//若是队列存在,则销毁他(和初始化一致),要不再加一个将数据清空吧
Status DestroyQueue(sqQueue *Q)
{
if (!Q)
return ERROR;
memset(Q, 0, MAXSIZE*sizeof(ElemType));
Q->front = Q->rear = 0; //都指向下标0
return OK;
}
双端队列
双端队列是与队列类似的项的有序集合。
双端队列有两个端部,首部和尾部,并且项在集合中保持不变。
双端队不同的地方是添加和删除项是非限制性的。可以在前面或后面添加新项;同样,可以从任一端移除现有项。
注意:双端队列也可以是带限制的,比如限制只能从一端入队或者只能从一端出队。
双端队列的应用
使用 deque 数据结构可以容易地解决经典回文问题。回文是一个字符串,读取首尾相同的字符,例如,radar toot madam。 我们想构造一个算法输入一个字符串,并检查它是否是一个回文。
解决方案:
将字符串添加到双端队列中,直接删除并比较收尾字符串,如果可以持续匹配首尾字符,我们最终要么用完字符,要么留出大小为 1 的deque,取决于原始字符串的长度是偶数还是奇数。
课后习题
【2010年真题】某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作。若元素 a、b、c、d、e 依次入此队列后再进行出队操作,则不可能得到的出队序列是()。
A.b a c d e B.d b a c e C.d b c a e D.e c b a d
参考答案:C
答案解析:考查受限的双端队列的出队序列。
A 可由左入,左入,右入,右入,右入得到 B 可由 左入,左入,右入,左入,右入得到。
D 可由左入,左入,左入,右入,左入得到 所以不可能得到 C。
【2009年真题】为解决计算机主机与打印机之间速度不匹配问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是()。
A.栈 B.队列 C.树 D.图
参考答案:B
答案解析:考查栈和队列的特点及应用。
C 和 D 直接排除,缓冲区的特点需要先进先出,若用栈,则先进入缓冲区的数据则要排队到最后才能打印,不符题意,所以只有队列符合题意。
【2014年真题】循环队列放在一维数组 A[0…M-1]中,end1 指向队头元素,end2 指向队尾元素的后 一个位置。假设队列两端均可进行入队和出队操作,队列中最多能容纳 M-1 个元素。初始 时为空。下列判断队空和队满的条件中,正确的是()
A.队空:end1 == end2; 队满:end1 == (end2+1)mod M
B.队空:end1 == end2; 队满:end2 == (end1+1)mod (M-1)
C.队空:end2 == (end1+1)mod M; 队满:end1 == (end2+1)mod M
D.队空:end1 == (end2+1)mod M;队满:end2 == (end1+1)mod (M-1)
参考答案:A
答案解析:end1 指向队头元素,那么可知出队的操作是先从 A[end1]读数,然后 end1 再加 1。 end2 指向队尾元素的后一个位置,那么可知入队操作是先存数到 A[end2],然后 end2 再加 1。若把 A[0]储存第一个元素,当队列初始时,入队操作是先把数据放到 A[0],然后 end2 自增,即可知 end2 初值为 0;而 end1 指向的是队头元素,队头元素的在数组 A 中的下标为 0,所以得知 end1 初值也为 0,可知队空条件为 end1==end2;然后考虑队列满时,因为队列 最多能容纳 M-1 个元素,假设队列存储在下标为 0 到下标为 M-2 的 M-1 个区域,队头为 A[0],队尾为 A[M-2],此时队列满,考虑在这种情况下 end1 和 end2 的状态,end1 指向队 头元素,可知 end1=0,end2 指向队尾元素的后一个位置,可知 end2=M-2+1=M-1,所以可 知队满的条件为 end1==(end2+1)mod M,选 A。
注意:考虑这类具体问题时,用一些特殊情况判断往往比直接思考问题能更快的得到答案,并可以画出简单的草图以方便解题。
【2019年真题】设栈 S 和队列 Q 的初始状态均为空,元素 a,b,c,d,e,f,g 依次进入栈 S。若每个元素出栈后立即进入队列 Q,且 7 个元素出队的顺序是 b,d,c,f,e,a,g,则栈 S 的容量至少是()。
A.1 B.2 C.3 D.4
参考答案:C
答案解析:考查栈的最大递归深度。
时刻注意栈的特点是先进后出。下面是出入栈的详细过程:
序号
说明
栈内
栈外
序号
说明
栈内
栈外
1
a 入栈
a
8
e入栈
ae
bdc
2
b 入栈
ab
9
f 入栈
aef
bdc
3
b 出栈
a
b
10
f 出栈
ae
bdcf
4
c 入栈
ac
b
11
e 出栈
a
bdcfe
5
d 入栈
acd
b
12
a 出栈
bdcfea
6
d 出栈
ac
bd
13
g 入栈
g
bdcfea
7
c 出栈
a
bdc
14
g 出栈
bdcfeag
登录后开始许愿
暂无评论,来抢沙发