1.栈与队列基本内容
(1).栈:栈是一种线性结构,限定仅在表尾进行插入和删除操作的线性表。
通过学习栈的性质,我们可以将其形象的想成叠盘子,每一个元素压入栈时都会成为栈顶元素,删除时也是从栈顶删除,因此符合“先入后出,后入先出原则”,下面是栈基于c++的实现。
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
#define stack_initsize 100
#define stackincrement 10
#define overflow -1
#define OK 1
#define error 0
typedef int elemtype;
typedef int Status;
typedef struct{
elemtype *base;
elemtype *top;
int stacksize;
}sqstack;
Status initstack(sqstack &s);
Status gettop(sqstack &s,elemtype &e);
Status push(sqstack &s,elemtype e);
Status pop(sqstack &s,elemtype &e);
Status check(char *ch,sqstack &s,elemtype &e);
Status length(sqstack &s);
int main(){
sqstack s; initstack(s);
elemtype e; int n; cin>>n;
for(int i=0;i<n;i++){
cin>>e; push(s,e);
}
cout<<"the stack is:";
for(int i=0;i<n;i++){
cout<<*(s.base++)<<' ';
}
cout<<'\n'<<"the convertion number is:";
convertion();
fflush(stdin);
cout<<'\n'<<"input:";
sqstack s1; initstack(s1);elemtype e1;
char str[100];
gets(str);
int a=check(str,s1,e1);
if(a==1)
cout<<"ok";
else cout<<"false";
fflush(stdin);
char exp[100];
int result;
cout<<"Please Enter Expression:";
gets(exp); result=evaluateexpression(exp);
cout<<'\n';cout<<exp<<result;
}
Status initstack(sqstack &s){
s.base=(elemtype*)malloc(stack_initsize*sizeof(elemtype));
if(!s.base) exit (overflow);
s.top=s.base;
s.stacksize=stack_initsize; return OK;
}
Status gettop(sqstack &s,elemtype &e){
if(s.base==s.top) return error;
e=*(s.top-1); return OK;
}
Status push(sqstack &s,elemtype e){
if(s.top-s.base>=s.stacksize){
s.base=(elemtype*)realloc(s.base,(s.stacksize+stackincrement)*sizeof(elemtype));
s.top=s.base+s.stacksize;
s.stacksize+=stackincrement;
}
*s.top++=e;
return OK;
}
Status pop(sqstack &s,elemtype &e){
if(s.top=s.base) return error;
e=*--s.top;
return OK;
}
Status length(sqstack &s){
elemtype length=s.top-s.base;
return 0;
}
Status stackempty(sqstack &s){
if (s.base==s.top)
return OK;
else return error;
}
void create(sqstack *s){
s->base=(elemtype *)malloc(stack_initsize*sizeof(elemtype));
if(!s->base)
{
printf("Space allocation failed!\n");
return;
}
s->top=s->base;
s->stacksize=stack_initsize;
return;
}
elemtype GetTop(sqstack *s) {
if(s->base==s->top)
{
printf("Stack is empty!\n");
printf("Unable to fetch top stack element!\n");
}
return *(s->top-1);
}
(1).leetcode-225:用队列实现栈 全ac代码如下:
class Mystack{ public: queue<int>q; Mystack(){}//初始化栈 void push(int x){ int len=q.size(); q.push(x); for(int I=0;i<len;i++){ q.push(q.front()); q.pop(); } } int pop(){ int r=q.front(); q.pop(); return r; } int top(){ int r=q.front(); return r; } bool empty(){ return q.empty(); } }
代码分析:当栈和队列放一起时,我们自然会想到如何相互转换。由于栈与队列是进入规则是反的,所以入栈和出栈是难题所在。而我们又想将队首元素成为栈顶,但是当我们将一个元素加入队列时,是处于队尾的,若想将它变成队首元素,所以想到我们先将新元素入队,再将新元素之前的元素依此重新入队,这样新元素的前后都是原来队列中的元素。此时再将新元素前面的元素依此出队。此时就可以实现加入队列的元素成为队首而不是队尾,与栈的性质对应,即新入栈的元素都是栈顶元素。
标签:Status,return,sqstack,队列,elemtype,top,base,数据结构,刷题 From: https://www.cnblogs.com/curtain-cpp/p/16817751.html