引言:算法操作的集合可以随着时间的改变而增大,减小,或者产生其他变化,我们称这种集合是动态的。接下来的五章,我们将研究计算机上表示和操作有穷动态集合的一些基本技术。本文主要为你讲解栈与队列的操作和实现,建议将这些操作制作成库,方便以后的引用,避免重复编码。系列文章为算法导论的笔记和相关习题解答。
本文来源:栈与队列
动态集合的元素
元素包括两个部分:关键字+卫星数据
动态集合上的操作
主要包括两个大的方面:查询
我们约定:集合为S,关键字为k,指向元素的指针为x
Search(S,k)
Inserrt(S,x)
Delete(S,x)
Minimum(S)
Maximum( S )
Successor (S,x)
Predecessor(S,x)
栈和队列
一、栈
实现了一种先进先出的策略。通常情况下我们采用数组加栈顶指示top来实现,约定top==0(或者-1)的时候表示栈为空;同时如果stack的长度是m,那么要考虑元素个数超过m以后产生的溢出问题。栈的一些定义和基本操作如下:
#ifndef MAXSTACKSIZE
#define MAXSTACKSIZE 200
#endif
typedef int StackDataType;
typedef struct mystack{
int top;
StackDataType data[MAXSTACKSIZE];
}Stack,*StackPointer;
extern int IsEmpty(Stack s);
extern int Push(StackPointer s, StackDataType element);
extern StackDataType Pop(StackPointer s);
注明:stack的数据结构还可以定义一个指针和大小,来取代数组。这些操作的实现方式如下:
#include"stack.h"
#include<stdlib.h>
#include<stdio.h>
StackDataType Pop(StackPointer s){
if(s->top==-1){
printf("the stack is already empty!\n");
exit(1);
}
--(s->top);
return s->data[s->top+1];
}
int IsEmpty(Stack s){
if(s.top==-1){
return 1;
}
else{
return 0;
}
}
int Push(StackPointer s,StackDataType element){
if(s->top >= MAXSTACKSIZE-1){
printf("the stack is over flow!\n");
return 0;
}
++(s->top);
s->data[s->top]=element;
return 1;
}
二、队列
我们可以把队列想象成排队等待服务的人群,同样也可以用 数组+对头指针+对尾指针 来实现队列这个数据结构;其中,head表示下一个要出列的元素,tail表示刚刚进入队列的元素。另外,为了实现环绕,我们需要把队列实现成为循环数组的模式,这个可以通过取模运算来实现。这样,head==tail+1表示队列已经满了;但是,此时我们会发现,如果我们让元素逐个出列,那么当最后一个元素出列的时候,同样满足head=tail+1;也就是说,队列在空和满的情况下具有相同的抽象条件。为了对此进行区分,我们用tail表示下一个进入队列的元素将要进入队列的位置,那么,初始化情况下,所以head=tail表示队列为空,初始情况下,head=tail=0;如果我们用head=tail+1表示队列为满的情况,意味着这个情况下,队列中有一个位置处于没有利用的状态,如果要利用这个元素,又会出现head=tail表示空和满两种情况。
关于队列的一些操作实例可以看下图,从而理解上面一段中的相关情况:
队列的一些定义的基本的操作如下:
#ifndef MAXQUEUESIZE
#define MAXQUEUESIZE 200
#endif
typedef int QueueDataType;
typedef struct myqueue{
int tail;
int head;
QueueDataType data[MAXQUEUESIZE];
}Queue,*QueuePointer;
extern int IsEmpty(Queue queue);
extern int IsFull(Queue queue);
extern int EnQueue(QueuePointer queuep, QueueDataType element);
extern QueueDataType DeQueue(QueuePointer queuep);
操作实现:
#include"queue.h"
#include<stdlib.h>
#include<stdio.h>
/*make sure the queue is not empty when you delete element from it*/
QueueDataType DeQueue(QueuePointer queue){
if(queue->head==queue->tail){
printf("the queue is already empty!\n");
exit(1);
}
QueueDataType temp;
temp=queue->data[queue->head];
++(queue->head);
if(queue->head==MAXQUEUESIZE)//
queue->head=0;
return temp;
}
int IsEmpty(Queue queue){
if(queue.head==queue.tail){
return 1;
}
else{
return 0;
}
}
int IsFull(Queue queue){
if(queue.head==(queue.tail+1)%MAXQUEUESIZE){
return 1;
}
else
return 0;
}
int EnQueue(QueuePointer queue,QueueDataType element){
if(IsFull((*queue))){
printf("the queue is over flow!\n");
return 0;
}
queue->data[queue->tail]=element;
++(queue->tail);
if(queue->tail==MAXQUEUESIZE)
queue->tail=0;
return 1;
}
心得:栈与队列,分别是两种FIFO和FILO的数据结构,至于具体实现,栈的增长和队列进出的方向完全可以由用户定义。另外,在实际的编程中,以循环队列的实现为例,容易出现逻辑错误的地方在于条件判断和边界条件的设定。其中条件判断要是充要条件,也就是说,你的代码需要能准确反应你的文字表述的意图,虽然我们设定的条件是队列满,但是如果用head=tail,虽然表示了队列满的情况,但是它也表示队列是空的情况,所以是不正确的。比如判断队列是满还是空,如果我们想要将数组的每个元素都利用,这时就会发现队列在满和空的时候满足同样的条件head=tail,显然,这是应该避免的;所以浪费了一个空间,来区分队列是满还是空这个情况。经验:行动前周密的思考能大量节省时间。
练习:编程实现2,4,5,6,7:
2,一个栈stack1从低地址到高地址,另外一个栈stack2从高地址到低地址:当top1>=top2时,栈溢出。
4,解答:参见本文中的代码,里面有对溢出情况的处理
5,解答:参见代码biqueue.c
6,解答:两个栈,栈底相连就是一个队列,但是要注意这两个栈为空的边界条件。
7,解答:两个队列,参考下图
分享到:
相关推荐
3.掌握栈和队列的逻辑结构特点、顺序存储结构、链式存储结构、顺序栈和链栈的结构体类型定义、循环队列和链队列的结构体类型定义、栈和队列在两种存储结构上的各种基本操作的实现算法。 4.将任意十进制数转换为三种...
数据结构与算法:栈队列的题库
计算机系的教材,算法导论————————————————————————————————
能用代码表示的都用代码表示,不能表示的写出思路,思路都没写的就是我也做不出来
实验一:栈和队列 一、实验题目 1.数制转换问题 2.求后缀表达式 3.舞会 4.连通块 二、实验目的 1.掌握算法设计中的递归结构; 2.掌握栈的顺序表示、链表表示以及相应操作的实现。(特别注意栈空和栈满 的条件); 3....
数据结构中 栈 队列 算法 得讲解。欢迎大家下载,学习。
实验报告学院(系)名称:计算机与通信工程学院姓名王帆学号20152180专业计算机科学与技术班级2015级1班实验项目实验二:栈与队列应用课程名称数据结构与算法
编写程序,建立容量为n(建议n=8)的循环队列,完成以下程序功能。输入字符#,执行一次出队操作,屏幕上显示出队字符;输入字符@,队列中所有字符依次出队并按出队次序在屏幕上显示各字符;输入其它字符,则输入的字符...
本章的基本内容是: 两种特殊的线性表——栈和队列 从数据结构角度看,栈和队列是操作受限的线性表,他们的逻辑结构相同。 从抽象数据类型角度看,栈和队列是两种重要的抽象数据类型。
所有代码都是在我学习这本书时亲手敲出来的,并且调试正确了,包括:第三部分到第六部分(即10-26章),外加第七部分31和32章所有的算法和数据结构以及编程习题还有思考题的C++实现源代码; 第一、二部分学习的较早...
这本书是南京大学翻译的! 里面涵盖丰富的算法思想和算法设计技巧同时还有算法优化! 比较适合初学者!
(1) 熟悉栈的特点(先进后出)及栈的基本操作,如入栈、出栈等,掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现; (2) 熟悉队列的特点(先进先出)及队列的基本操作,如入队、出队等,掌握队列的...
算法与数据结构:5-栈和队列2.pdf
数据结构与算法 中国矿业大学出版社 主编 张小燕 第三章 栈和队列
计算机算法——设计与分析导论(第三版).pdf 英文版
算法与数据结构:第三章 栈和队列.ppt
算法学习必看之作。。。经典之中的经典。。。。。。。。。。。。。。。。。。。。。。。。。。
算法与数据结构:6-栈和队列3.pdf