栈
栈(stack)是限定仅在表尾进行插入或删除操作的线性表。因此,对栈来说,表尾端有其特殊含义,称为栈顶,相应地,表头端称为栈底。 栈又称为后进先出的线性表(简称LIFO结构)。
栈的基本操作包含建栈、入栈、出栈…
以下是栈的实现方式:
//栈的顺序存储表示
#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量
typedef struct {
SElemType * base; //在栈构造之前和销毁之后,base的值为null
SElemType * top; //栈顶指针
int stacksize; //当前已分配的存储空间,以元素为单位
}SqStack;
//基本操作的算法描述(部分)
Status InitStack (SqStack &S) {
//构造一个空栈S
S.base = (SElemType * ) malloc (STACK_INIT_SIZE * sizeof(SElemType));
if (!S.base) exit (overflow); //存储分配失败
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}//InitStack
Status GetTop (SqStack S, SElemType &e) {
//若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR
if (S.top == S.base) return ERROR;
e = * (S.top - 1);
return OK;
}//GetTop
Status Push (SqStack &S, SElemType e) {
//插入元素e为新的栈顶元素
if (S.top - S.base >= S.stacksize) { //栈满,追加存储空间
S.base = (SElemType * ) realloc (S.base, (S.stacksize + STACKINCREMENT) * sizeof (SElemType));
if (!S.base) exit (OVERFLOW); //存储分配失败
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
* S.top++ = e;
return OK;
}//Push
Status Pop (SqStack &S, SelemType &e) {
//若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
if (S.top == S.base) return ERROR;
e = * --S.top;
return OK;
}//Pop
队列
和栈相反,队列(queue)是一种先进先出(FIFO)的线性表。它只允许在表的一端进行插入,而在另一端删除元素。在队列中,允许插入的一端叫做队尾,允许删除的一端叫做队头。
队列的基本操作包括:构造队列、销毁队列、插入元素、删除元素…
以下是队列的实现方式:
单链队列–链式存储
//单链队列的链式存储结构
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 = (QueuePtr) malloc (sizeof(QNode));
if (!Q.front) exit (OVERFLOW); //存储分配失败
Q.front -> next = NULL;
return OK;
}
Status DestroyQueue (LinkQueue &Q) {
//销毁队列Q
while (Q.front) {
Q.rear = Q.front -> next;
free (Q.front);
Q.front = Q.rear;
}
return OK;
}
Status EnQueue (LinkQueue &Q, QElemType e) {
//插入元素e 为Q的队尾元素
p = (QueuePtr) malloc (sizeof(QNode));
if(!p) exit (OVERFLOW); //存储分配失败
p -> data = e; p -> next = NULL;
Q.rear -> next = p;
Q.rear = p;
return OK;
}
Status DeQueue (LinkQueue &Q, QElemType &e) {
//若队列不空,则删除Q的队头元素,用e返回其值,并返回OK 否则返回ERROR
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; //一般情况下,删除队列头元素时仅需修改头结点中的指针
free (p); //但当队列中最后一个元素被删除后,队列尾指针也丢失了,因此需要对队尾指针重新赋值(指向头结点)
return OK;
}
循环队列–顺序存储
//循环队列 顺序存储结构
#define MAXQSIZE 100 //最大队列长度
typedef struct {
QElemType * base; //初始化的动态分配存储空间
int front; //头指针,若队列不空,指向队列头元素
int rear; //尾指针,若队列不空,指向队列尾元素的下一个位置
}SqQueue;
//循环队列的基本操作的算法描述
Status InitQueue (SqQueue &Q) {
//构造一个空队列Q
Q.base = (QElemType * ) malloc (MAXQSIZE * sizeof (QElemType));
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) return ERROR; //队列满
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MAXQSIZE;
return OK;
}
Status DeQueue (SqQueue &Q, QElemType &e) {
//若队列不空,则删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR
if(Q.front == Q.rear) return ERROR;
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;
return OK;
}
题集经典例题:
3.15 假设以顺序存储结构实现一个双向栈,即在一维数组的存储空间中存在着两个栈,它们的栈底分别设在数组的两个端点。 试编写实现这个双向栈 tws 的三个操作: 初始化 inistack(tws) 、 入栈 push(tws,i,x) 和出栈 pop(tws,i) 的算法,其中 i 为 0 或 1,用以分别指示设在数组两端的 两个栈
typedef struct {
Elemtype * base[2];
Elemtype * top[2];
}BDStacktype; //双向栈类型
Status Init_Stack (BDStacktype &tws, int m) //初始化一个大小为m的双向栈tws
{
tws.base[0] = (Elemtype * ) malloc (sizeof(Elemtype));
tws.base[1] = tws.base[0] + m;
tws.top[0] = tws.base[0];
tws.top[1] = tws.base[1];
return OK;
}
Status push (BDStscktype &tws, int i, Elemtype x) //x入栈,i=0表示低端栈,i=1表示高端栈
{
if (tws.top[0] > tws.top[1])
return OVERFLOW;
if (i == 0)
* tws.top[0]++ = x;
else if (i == 1)
* tws.top[1]-- = x;
else return ERROR;
return OK;
}
Status pop (BDStacktype &tws, int i, Elemtype &x)
{
if (i == 0)
{
if (tws[0] == tws.base[0])
return OVERFLOW;
x = * --tws.top[0];
}
else if (i == 1)
{
if (tws.top[1] == tws.base[1])
return OVERFLOW;
x = * ++tws.top[1];
}
else
return ERROR;
return OK;
}
3.16 假设如题 3.1 所属火车调度站的入口处有 n 节硬席或软席车厢(分别以 H和 S 表示)等待 调度,试编写算法,输出对这 n 节车厢进行调度的操作(即入栈或出栈操作)序列,以使所有的 软席车厢都被调整到硬席车厢之前。
void Train_arrange (char * train) //字符串train表示火车 H表示硬席 S表示软席
{
p = q = train;
InitStack (s);
while ( * p)
{
if ( * p == 'H' )
push (s, *p);
else
* (q++) = * p; //把S调到前部
p++;
}
while (!StackEmpty(s))
{
pop (s,c);
* (q++) = c; //把H接到后部
}
}
3.17 试写一个算法,识别一次读入的一个以 @为结束符的字符序列是否为形如‘序列 1&序列 2’ 模式的字符序列。其中序列 1 和序列 2 中都不含字符‘ &’,且序列 2 是序列 1 的逆序列。例如, ‘a+b&b+a’是属该模式的字符序列,而‘ 1+3&3-1 ’则不是。
int IsReverse () //判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0
{
InitStack (s);
while ((e = getchar()) != '&' )
push (s,e);
while ((e = getchar()) != '@' )
{
if (StackEmpty(s))
return 0;
pop (s,c);
if (e != c)
return 0;
}
if (!StackEmpty(s))
return 0;
return 1;
}
3.18 试写一个判别表达式中开、闭括号是否配对出现的算法。
Status Bracket_Test (char * str) //判别表达式中小括号是否匹配
{
count = 0;
for (p = str; * p; p++)
{
if ( * p == '(' )
count++;
if ( * p == ')' )
count--;
if (count < 0)
return ERROR;
}
if (count) //注意括号不匹配的两种情况
return ERROE;
return OK;
}
3.19 假设一个算术表达式中可以包括三种括号:圆括号“(”和“)”、方括号“ [ ”和“ ] ” 和花括号“{ ”和“} ”,且这三种括号可按任意的次序嵌套使用 (如:, [ , { , } , [ , ] , ] , [ , ] , ( , ) , ) 。编写判别给定表达式中所含括号是否正确配对出现的算法 (已知表达式已存入数据元 素为字符的顺序表中)。
Status AllBrackets_Test (char * str)
{
InitStack (s);
for (p = str; * p; p++)
{
if ( * p == '(' || * p == '[' || * p == '{' )
push ( s, * p);
else if ( * p == ')' || * p == ']' || * p == '}' )
{
if (StackEmpty(s))
return ERROR;
pop (s,c);
if ( * p == ')' && c != '(' )
return ERROR;
if ( * p == ']' && c != '[' )
return ERROR;
if ( *p == '}' && c != '{' )
return ERROR;
}
}
if (!StackEmpty(s))
return ERROR;
}
3.28 假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针),试编写相应的队列初始化、入队列和出队列的算法。
void InitCiQueue (CiQueue &Q) //初始化循环链表表示的队列Q
{
Q = (CiLNode * ) malloc (sizeof(CiLNode));
Q -> next = Q;
}
void EnCiQueue (CiQueue &Q, int x) //把元素x插入循环链表表示的队列Q,Q指向队尾元素,Q->next指向头结点,Q->next->next指向队头元素
{
p = (CiLNode * ) malloc (sizeof(CiLNode));
p -> data = x;
p -> next = Q -> next; //直接把p加在Q的后面
Q -> next = p;
Q = p; //修改尾指针
}
Status DeCiQueue (CiQueue &Q, int x) //从循环链表表示的队列Q头部删除元素x
{
if (Q == Q -> next)
return INFEASIBLE; //队列已空
p = Q -> next -> next;
x = p -> data;
Q -> next - next = p -> next;
free (p);
return OK;
}
3.30 假设将循环队列定义为 : 以域变量 rear 和 length 分别指示循环队列中队尾元素的位置和内 含元素的个数。 试给出此循环队列的队满条件, 并写出相应的入队列和出队列的算法 (在出队列 的算法中要返回队头元素)。
Status EnCyQueue (CyQueue &Q, int x) //带length域的循环队列入队算法
{
if (Q.length == MAXSIZE) return OVERFLOW;
Q.rear = (Q.rear + 1) % MAXSIZE;
Q.base[Q.rear] = x;
Q.length++;
return OK;
}
Status DeCyQueue (CyQueue &Q, int x) //带length域的循环队列出队算法
{
if (Q.length == 0) return ERROR;
front = (Q.rear - Q.length + 1) % MAXSIZE;
x = Q.base[front];
Q.length--;
}
3.31 假设称正读和反读都相同的字符序列为“回文”,例如,‘ abba’和‘ abcba’是回文, ‘abcde’和‘ ababab’则不是回文。 试写一个算法判别读入的一个以‘ @’为结束符的字符序列 是否是“回文” 。
int Palindrome_Test () //判别输入的字符串是否回文序列,是则返回1,否则返回0
{
InitStack (S);
InitQueue (Q); //同时使用栈和队列两种结构
while ((c = getchar()) != '@' )
{
Push (S,c);
EnQueue (Q,c);
}
while (!StackEmpty(S))
{
Pop (S,a);
DeQueue (Q,b);
if (a != b)
return ERROR;
}
return OK;
}