栈与队列，各有异同。
⾸先是两者的定义：
栈也称为堆栈，是⼀种线性表。
栈的特性：最先放⼊栈中的内容最后被拿出来，最后放⼊栈中的内容最先被拿出来，被称为先进后出、后进先出。队列也是⼀种特殊的线性表。不同于栈所服从的先进后出的原则，队列的原则是先进先出。
队列在队头做删除操作，在队尾做插⼊操作。
然后是两者的异同点
不同点：
1.删除数据元素的位置不同，栈的删除操作在表尾进⾏，队列的删除操作在表头进⾏。
2.队列先进先出，栈先进后出。
3.顺序栈能够实现多栈空间共享，⽽顺序队列不能。
4.遍历数据速度不同。
栈只能从头部取数据，也就最先放⼊的需要遍历整个栈最后才能取出来。
队列则不同，它基于地址指针进⾏遍历，⽽且可以从头或尾部开始遍历⽆需开辟临时空间，速度要快的多。
相同点：
1.都是。
2.插⼊操作都是限定在表尾进⾏。
3.都可以通过顺序结构和链式结构实现。
4.插⼊与删除的时间复杂度与空间复杂度上两者均相同。
再然后便是两者的表⽰和操作的实现
栈表⽰和操作的实现：
#include <iostream>
#define MAXSIZE 100//基础容量
using namespace std;
typedef struct
{
SElemType *top;//栈顶指针
SElemType *base;//栈底指针
int stacksize;//栈可⽤最⼤容量
}SqStack;
Status InitStack(SqStack &S)//初始化栈
{
S.base=new SElemType[MAXSIZE];
if(!s.base) exit(OVERFLOW);//内存分配失败
S.stacksize=MAXSIZE;
}
Status Push(SqStack &S,SElemType e)//把元素e压⼊栈顶
{
p-S.base==S.stacksize) return ERROR;//栈满
*S.top++=e;//栈顶指针+1
return OK;
}
Status Pop(SqStack &s,SElemType &e)//取出栈顶元素，并删除栈顶
{
p==S.base)//top与base重合时，栈为空
return ERROR;
e=*--S.top;
return OK;
}
SElemType GetTop(SqStack S)
{
p!=S.base)
return *(S.top-1);
}
队列表⽰和操作的实现：
#ifndef STATICQUEUE_H_INCLUDED
#define STATICQUEUE_H_INCLUDED
template<class T>
class StaticQueue
{
public:
StaticQueue();
StaticQueue(int size);
~StaticQueue();
void enqueue(T data);
T dequeue();
bool isEmpty();
bool isFull();
int count();
void display();
private:
int rear;
int front;
int size;
const static int DEFAULT;
T* queue;
};
这些在课本上都有，下⾯说说遇到的问题：
对于作业3，可以说是屡战屡败，屡败屡战了，先是⼀点思路都没有，再到后来⽼师提⽰后有⼀点思路，但还是错误百出，再到后来参照书上的⽅法，还是错误，最后终于发现问题。话不多说，直接上代码：
#include <iostream>
#define MAXSIZE 100//基础容量
using namespace std;
typedef struct
{
SElemType *top;//栈顶指针
SElemType *base;//栈底指针
int stacksize;//栈可⽤最⼤容量
}SqStack;
Status InitStack(SqStack &S)//初始化栈
{
S.base=new SElemType[MAXSIZE];
if(!s.base) exit(OVERFLOW);//内存分配失败
S.stacksize=MAXSIZE;
}
Status Push(SqStack &S,SElemType e)//把元素e压⼊栈顶
{
p-S.base==S.stacksize) return ERROR;//栈满
*S.top++=e;//栈顶指针+1
return OK;
}
Status Pop(SqStack &s,SElemType &e)//取出栈顶元素，并删除栈顶{
p==S.base)//top与base重合时，栈为空
return ERROR;
e=*--S.top;
return OK;
}
SElemType GetTop(SqStack S)
{
p!=S.base)
return *(S.top-1);
}
Status Matching()
{
InitStack(s);
flag=1;
cin>>ch;
while(ch!='#'&&flag)
{
switch(ch)
{
case'{':
case'[':
case'(':
Push(S,ch);
break;
case')':
if(!StackEmpty(S)&& GetTop(s)=='（')
Pop(S,e);
else flog=0;
break;
case']':
if(!StackEmpty(S)&& GetTop(S)=='[')
Pop(S,e);
else flog=0;
break;
case'}':
if(!StackEmpty(S)&& GetTop(S)=='{')
Pop(S,e);
else flog=0;
break;
}
cin>>ch;
}
if(StackEmpty()&&flag)
cout<<"yes";
else cout<<"no";
}
这是错误的，⽆法输⼊空格，虽然与书本上的⼀致，但并不完善
#include<iostream>
#include<string>
#include <stdio.h>
using namespace std;
struct initstack {
char *top = NULL;//定义栈底指针
char*base = NULL;//定义栈顶指针
int stacksize;//定义栈空间长度
}S;//创建top指针和base指针
void Initinitstack(initstack &S) {
S.base = new char [101];//为栈创建空间
S.stacksize = 101;//定义顺序栈长度
}//创建顺序栈
void push(initstack &S,char str){
*S.top = str;//将字符存⼊栈中
++S.top;//栈顶指针地址加⼀
}//⼊栈函数
char pop(initstack &S) {
--S.top;//栈顶指针下移⼀位
char str = *S.top;//取栈顶字符
*S.top = 0;//删除栈顶字符
return str;
}//出栈函数
bool matching() {
int flag = 1;string str;
getline(cin, str);//输⼊字符串
if (str.size()> 100) return 0;//字符串长度不得超过100
namespace是干嘛的int count = 0;//定义基数
while (str[count] != '\0'&&flag) {//若出现左括号，则⼊栈
if (str[count] == '(' || str[count] == '[' || str[count] == '{'){
if (S.top - S.base != S.stacksize) {//判断栈满
push(S, (char)str[count]);//进⾏⼊栈
}
}
if (str[count] == ')' || str[count] == ']' || str[count] == '}') {//若出现右括号，则取栈顶字符char temp = 0;
if (S.base == S.top) flag = 0;//若出现右括号并且栈空的情况，说明不匹配
else temp = pop(S);//栈顶元素进⾏出栈
switch (temp){//利⽤switch语句进⾏判断
case'(':
if (str[count] != ')') flag = 0;//匹配不成功
break;
case'[':
if (str[count] != ']') flag = 0;//匹配不成功
break;
case'{':
if (str[count] != '}') flag = 0;//匹配不成功
break;
default:
break;
}
}
++count;
}
if (S.top!=S.base) flag = 0;//最后判断栈空
return flag;//返回flag的情况
}
int main(){
Initinitstack(S);//创建顺序栈
if (matching()) cout << "yes";//调⽤匹配函数
else cout << "no";
return 0;
}
这个达到了题⽬要求，利⽤string函数代替了直接输⼊，解决了⽆法输⼊空格问题。总之，第三章⽐起前⾯的内容，明显更难，但我们不能放弃，⼀定要坚持！加油！

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。