下载文档原格式
队和栈的主要区别是
队列和栈是两种不同的数据结构。
它们有以下区别：
（1）操作的名称不同。
队列的插入称为入队，队列的删除称为出队。
栈的插入称为进栈，栈的删除称为出栈。
（2）可操作的方式不同。
队列是在队尾入队，队头出队，即两边都可操作。
而栈的进栈和出栈都是在栈顶进行的，无法对栈底直接进行操作。
（3）操作的方法不同。
队列是先进先出（FIFO），即队列的修改是依先进先出的原则进行的。
新来的成员总是加入队尾（不能从中间插入），每次离开的成员总是队列头上（不允许中途离队）。
而栈为后进先出（LIFO）,即每次删除（出栈）的总是当前栈中最新的元素，即最后插入（进栈）的元素，而最先插入的被放在栈的底部，要到最后才能删除。
数据结构--栈和队列基础知识⼀概述栈和队列，严格意义上来说，也属于线性表，因为它们也都⽤于存储逻辑关系为 "⼀对⼀" 的数据，但由于它们⽐较特殊，因此将其单独作为⼀篇⽂章，做重点讲解。
既然栈和队列都属于线性表，根据线性表分为顺序表和链表的特点，栈也可分为顺序栈和链表，队列也分为顺序队列和链队列，这些内容都会在本章做详细讲解。
使⽤栈结构存储数据，讲究“先进后出”，即最先进栈的数据，最后出栈；使⽤队列存储数据，讲究 "先进先出"，即最先进队列的数据，也最先出队列。
⼆栈2.1 栈的基本概念同顺序表和链表⼀样，栈也是⽤来存储逻辑关系为 "⼀对⼀" 数据的线性存储结构，如下图所⽰。
从上图我们看到，栈存储结构与之前所了解的线性存储结构有所差异，这缘于栈对数据 "存" 和 "取" 的过程有特殊的要求：1. 栈只能从表的⼀端存取数据，另⼀端是封闭的；2. 在栈中，⽆论是存数据还是取数据，都必须遵循"先进后出"的原则，即最先进栈的元素最后出栈。
拿图 1 的栈来说，从图中数据的存储状态可判断出，元素 1 是最先进的栈。
因此，当需要从栈中取出元素 1 时，根据"先进后出"的原则，需提前将元素 3 和元素 2 从栈中取出，然后才能成功取出元素 1。
因此，我们可以给栈下⼀个定义，即栈是⼀种只能从表的⼀端存取数据且遵循 "先进后出" 原则的线性存储结构。
通常，栈的开⼝端被称为栈顶；相应地，封⼝端被称为栈底。
因此，栈顶元素指的就是距离栈顶最近的元素，拿下图中的栈顶元素为元素 4；同理，栈底元素指的是位于栈最底部的元素，下中的栈底元素为元素 1。
2.2 进栈和出栈基于栈结构的特点，在实际应⽤中，通常只会对栈执⾏以下两种操作：向栈中添加元素，此过程被称为"进栈"（⼊栈或压栈）；从栈中提取出指定元素，此过程被称为"出栈"（或弹栈）；2.3 栈的具体实现栈是⼀种 "特殊" 的线性存储结构，因此栈的具体实现有以下两种⽅式：1. 顺序栈：采⽤顺序存储结构可以模拟栈存储数据的特点，从⽽实现栈存储结构。
栈和队列的基本操作是线性表操作的子集，是限定性（操作受限制）的数据结构。
第三章栈和队列数据结构之栈和队列23. 1 栈¾定义：是限定仅在表尾进行插入或删除操作的线性表。
(后进先出线性表LIFO)¾栈底指针(base) :是线性表的基址；¾栈顶指针(top):指向线性表最后一个元素的后面。
¾当top=base 时，为空栈。
¾基本操作：InitStack(&S), DestroyStack(&S),StackEmpty(S) , ClearStack(&S),GetTop(S ,&e), StackLength(S) ,Push(&S, e): 完成在表尾插入一个元素e.Pop(&S,&e): 完成在表尾删除一个元素。
数据结构之栈和队列3¾栈的表示和实现¾顺序栈：是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素；栈满之后，可再追加栈空间即为动态栈。
¾顺序栈的结构类型定义：typedef int SElemType;typedef struct{SElemType *base; /* 栈底指针*/SElemType *top; /* 栈顶指针*/int stacksize; /* 栈空间大小*/ }SqStack;数据结构之栈和队列4¾基本算法描述¾建立能存放50个栈元素的空栈#define STACK_INIT_SIZE 50#define STACKINCREMENT 10Status InitStack_Sq(Stack &S){S.base=(SET*)malloc(STACK_INIT_SIZE *sizeof(SET)); /*为栈分配空间*/if(S.base==NULL)exit(OVERFLOW); /*存储分配失败*/ S.top=S.base;S.stacksize = STACK_INIT_SIZE;return OK; }数据结构之栈和队列5¾出栈操作算法void pop(Sqstack s,SElemType e){if(s.top= = s.base)return ERROR;else{s.top--;e= *s.top;}return OK;}出栈操作topABY topABYbase base数据结构之栈和队列6¾压栈操作算法void Push(SqStack s,SElemType e)if(s.top-s.base>= S.stacksize;) {S.base=(SET*)realloc(S,base,(S.stacksize+STACKINCREMEN T) *sizeof(SET)); /*为栈重新分配空间*/if(！S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top=e;S.top++;}return OK; }topAB压栈操作topABebase base数据结构之栈和队列7¾栈的销毁void DestroyStack_Sq(Stack &S){ if (S.base) free(S.base);S.base=NULL;S.top=NULL;S.stacksize=0;}¾栈的清除void ClearStack_Sq(Stack &S){ S.top = S.base ;}数据结构之栈和队列8¾判断栈是否为空栈Status StackEmpty_Sq(Stack S){ if(S.top==S.base) return TRUE;else return FALSE;}¾获得栈的实际长度int StackLength_Sq(Stack S){return(abs(S.top-S.base));}数据结构之栈和队列9¾多个栈共享邻接空间两个栈共享一空间::::::top1top21m中间可用空间栈1栈2地址Base1Base 2……数据结构之栈和队列103. 3 栈与递归¾递归函数：一个直接调用自己或通过一系列的调用语句间接地调用自己的函数。
栈和队列的操作实验小结一、实验目的本次实验旨在深入理解和掌握栈和队列这两种基本数据结构的基本操作，包括插入、删除、查找等操作，并通过实际操作加深对这两种数据结构特性的理解。
二、实验原理栈（Stack）：栈是一种后进先出（Last In First Out，LIFO）的数据结构，即最后一个进入栈的元素总是第一个出栈。
在计算机程序中，栈常常被用来实现函数调用和递归等操作。
队列（Queue）：队列是一种先进先出（First In First Out，FIFO）的数据结构，即第一个进入队列的元素总是第一个出队。
在计算机程序中，队列常常被用来实现任务的调度和缓冲等操作。
三、实验步骤与结果创建一个空栈和一个空队列。
对栈进行入栈（push）和出栈（pop）操作，观察并记录结果。
可以发现，栈的出栈顺序与入栈顺序相反，体现了后进先出的特性。
对队列进行入队（enqueue）和出队（dequeue）操作，观察并记录结果。
可以发现，队列的出队顺序与入队顺序相同，体现了先进先出的特性。
尝试在栈和队列中查找元素，记录查找效率和准确性。
由于栈和队列的特性，查找操作并不像在其他数据结构（如二叉搜索树或哈希表）中那样高效。
四、实验总结与讨论通过本次实验，我更深入地理解了栈和队列这两种数据结构的基本特性和操作。
在实际编程中，我可以根据需求选择合适的数据结构来提高程序的效率。
我注意到，虽然栈和队列在某些操作上可能不如其他数据结构高效（如查找），但它们在某些特定场景下具有无可替代的优势。
例如，在实现函数调用和递归时，栈的特性使得它成为最自然的选择；在实现任务调度和缓冲时，队列的特性使得它成为最佳选择。
我也认识到，不同的数据结构适用于解决不同的问题。
在选择数据结构时，我需要考虑数据的特性、操作的频率以及对时间和空间复杂度的需求等因素。
通过实际操作，我对栈和队列的实现方式有了更深入的理解。
例如，我了解到栈可以通过数组或链表来实现，而队列则可以通过链表或循环数组来实现。
栈和队列是信息学竞赛中经常涉及的数据结构，它们在算法和程序设计中有着广泛的应用。
掌握栈和队列的基本原理和操作方法，对于参加信息学竞赛的同学来说是非常重要的。
本文将深入探讨栈和队列的相关知识点，帮助大家更好地理解和掌握这两种数据结构。
一、栈的定义与特点栈是一种先进后出（LIFO）的数据结构，它的特点是只允许在栈顶进行插入和删除操作。
栈可以用数组或链表来实现，常见的操作包括压栈（push）、出栈（pop）、获取栈顶元素（top）等。
栈的应用非常广泛，比如在计算机程序中，函数的调用和返回值的存储就是通过栈来实现的。
二、栈的基本操作1. 压栈（push）：将元素压入栈顶2. 出栈（pop）：将栈顶元素弹出3. 获取栈顶元素（top）：返回栈顶元素的值，但不把它从栈中移除4. 判空：判断栈是否为空5. 获取栈的大小：返回栈中元素的个数三、栈的应用1. 括号匹配：利用栈来检查表达式中的括号是否匹配2. 表达式求值：利用栈来实现中缀表达式转换为后缀表达式，并进行求值3. 迷宫求解：利用栈来实现迷宫的路径搜索4. 回溯算法：在深度优先搜索和递归算法中，通常会用到栈来保存状态信息四、队列的定义与特点队列是一种先进先出（FIFO）的数据结构，它的特点是只允许在队尾进行插入操作，在队首进行删除操作。
队列同样可以用数组或链表来实现，常见的操作包括入队（enqueue）、出队（dequeue）、获取队首元素（front）、获取队尾元素（rear）等。
队列在计算机领域也有着广泛的应用，比如线程池、消息队列等都可以用队列来实现。
五、队列的基本操作1. 入队（enqueue）：将元素插入到队列的末尾2. 出队（dequeue）：从队列的头部删除一个元素3. 获取队首元素（front）：返回队列的头部元素的值4. 获取队尾元素（rear）：返回队列的尾部元素的值5. 判空：判断队列是否为空6. 获取队列的大小：返回队列中元素的个数六、队列的应用1. 广度优先搜索算法（BFS）：在图的搜索中，通常会用队列来实现BFS算法2. 线程池：利用队列来实现任务的调度3. 消息队列：在分布式系统中，常常会用队列来进行消息的传递4. 最近最少使用（LRU）缓存算法：利用队列实现LRU缓存淘汰在信息学竞赛中，栈和队列的相关题目经常出现，并且有一定的难度。
栈与队
实验原理：
用栈实现顺序表的操作
实验目的：
1.掌握栈的数据类型描述，栈的特点及栈的存储结构；
2.掌握栈的基本运算及应用.
实验内容：
设车辆厂生产了硬座车厢和软座车厢共N节，混合在一起要求用顺序栈的5种运算使所有的硬座车厢排列到软座车厢前面。
请完善主函数实现上述功能。
实验步骤：
1、输入示例程序
2、构建按序插入函数实现算法
3、用C语言实现该算法
4、与源程序合并，编译，调试
5、测试，查错，修改
6、生成可执行文件，通过综合测试，完成实验
代码区：
#include<iostream>
using namespace std;
const int maxlen=20;
struct seqstack
{
char stack[maxlen];
int top;
};
//栈初始化
void inistack(seqstack &s) {
s.top=0;
}
//进栈
void push(seqstack &s,char x) {
if(s.top==maxlen-1)
cout<<"overflow";
else
{
s.top++;
s.stack[s.top]=x;
}
}
//出栈
void pop(seqstack &s)
{
if(s.top==0)
cout<<"underflow";
else
s.top--;
}
//取栈顶元素
char gettop(seqstack &s)
{
if(s.top==0)
{
cout<<"underflow";
return 0;
}
else
return s.stack[s.top];
}
//判别栈是否为空
int empty(seqstack &s)
{
if(s.top==0)
return 1;
else
return 0;
}
//打印栈内容
void prtstack(seqstack &s)
{
int i;
for(i=0;i<=s.top;i++)
{
cout<<s.stack[i]<<endl;
}
}
int main()
{
int n,i;
char x;
seqstack s1,s2;
inistack(s1);
inistack(s2);
cout<<"请输入车厢数\n";
cin>>n;
cout<<"请输入"<<n<<"节车厢代号(H 硬座车厢 S 软座车厢)";
for(i=0;i<n;i++)
{
cin>>x;
if(x=='H')
push(s1,x);
if(x=='S')
push(s2,x);
}
prtstack(s1);
prtstack(s2);
return 0;
}
实验总结:
本实验的重点在于对栈模式的理解。
栈是元素的插入与删除只能在线性表的同一端进行的一种特殊线性表。
最先放入的元素最先删除，最后放入的元素最后删除。
而对编程的要求较低，只需了解简单的C或C++知识，了解结构体。
所以，难点在于对栈模式的应用，运用它的“先入后出”。
经过一段的实验即可完成。
