Question

一个C/C++ 栈和队列的小问题

For questions 1-4, assume that an array stores integers and has a maximum size of 100.
The array is used to store two distinct data structures, BOTH a queue and a stack. The
answer should be written in C or C++ and should not use any existing data structure
libraries.

1. Write a function that pushes an integer into the stack.

2. Write a function that pops an integer from the stack.

3. Write a function that enqueues an integer into the queue.

4. Write a function that dequeues an integer from the queue.

我不会写，麻烦提供程序，谢谢~

Answer 1

自己写的代码，比较简单
顺序栈：
#include<iostream>
#include <stdio.h>
#include <stdlib.h>
#include<string>
using namespace std;

#define STACK_INIT_SIZE 100//栈存储空间的初始分配量
#define STACKINCREMENT 10//栈存储空间的分配增量

typedef struct
{
int *base;//存储空间基地址
int *top;//存储空间尾地址,即栈顶
int stacksize;////当前分配的存储容量
}SqStack;

int InitStack(SqStack &s)
{
s.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));
if(!s.base)
exit(OVERFLOW);
s.top=s.base;//空栈
s.stacksize=STACK_INIT_SIZE;

return true;
}

int GetTop(SqStack s)
{
if(s.top==s.base)
{
printf("栈顶元素不存在,空栈!\n");
return false;
}
printf("栈顶元素为:%d\n",*(s.top-1));

return true;
}

int Push(SqStack &s,int e)
{
if(s.top-s.base>=s.stacksize)
{
s.base=(int *)realloc(s.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(int));
if(!s.base)
exit(OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize +=STACKINCREMENT;
}
*s.top++=e;//将e加入栈顶,栈顶指针+1

return true;
}

int Pop(SqStack &s)
{
if(s.top==s.base)
return false;
s.top--;//栈顶指针-1

return true;
}

void print(SqStack s)
{
while(s.base<s.top)//不能取等,因为s.top始终为空
{
printf("%d ", *s.base);
s.base++;
}
printf("\n");
}

int main()
{
SqStack stack;
InitStack(stack);
int a[STACK_INIT_SIZE];
string str;
printf("初始化栈：");
getline(cin, str,'\n');
for(int i=0;i<str.size();i++)
{
a[i]=str[i]-'0';
Push(stack,a[i]);
}
a[str.size()]='\0';
print(stack);
while(true)
{
printf("菜单\n");
printf("1.读取栈顶元素\n");
printf("2.栈顶插入元素\n");
printf("3.删除栈顶元素\n");
int choice;
int cc;
printf("选择:");
scanf("%d",&choice);
switch(choice)
{
case 1:
GetTop(stack);
break;
case 2:
printf("输入要插入的数值:");
scanf("%d",&cc);
Push(stack,cc);
print(stack);
break;
case 3:
Pop(stack);
print(stack);
break;
}
}

return 0;
}
链队列：
#include<iostream>
#include <stdio.h>
#include <stdlib.h>
#include<string>
using namespace std;

typedef struct QNode
{
int data;
struct QNode *next;
}QNode, *QueuePtr;

typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;

int InitQueue(LinkQueue &Q)
{
Q.front=(QueuePtr)malloc(sizeof(int));
if(!Q.front)
exit(OVERFLOW);
Q.front->next=NULL;
Q.rear=Q.front;//空队列

return true;
}

int DestroyQueue(LinkQueue &Q)
{
while(Q.front)//从队头逐个销毁
{
Q.rear=Q.front->next;
Q.front=Q.rear;
}
printf("队列已经销毁!\n");

return true;
}

int EnQueue(LinkQueue &Q,int e)
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(int));
if(!p)
exit(OVERFLOW);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;//向队尾插入元素

return true;
}

int DeQueue(LinkQueue &Q)
{
if(Q.rear==Q.front)
return false;
QueuePtr p;
p=Q.front->next;
Q.front->next=p->next;//删除队头元素
if(Q.rear==p)
Q.rear=Q.front;//已经删空

return true;
}

int print(LinkQueue Q)
{
if(Q.front==Q.rear)
{
printf("队列为空!\n");
return false;
}
QueuePtr p;
p=Q.front->next;
while(p)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");

return true;
}

int main()
{
LinkQueue Q1;
InitQueue(Q1);
int a[100];
string str;
printf("初始化队列：");
getline(cin, str,'\n');
for(int i=0;i<str.size();i++)
{
a[i]=str[i]-'0';
EnQueue(Q1,a[i]);
}
a[str.size()]='\0';
print(Q1);
char is_stop='0';
while(is_stop!='#')
{
printf("菜单\n");
printf("1.元素入列队尾\n");
printf("2.元素队头出列\n");
printf("3.销毁全部队列\n");
int choice;
int cc;
printf("选择:");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("输入要入列的数值:");
scanf("%d",&cc);
EnQueue(Q1,cc);
print(Q1);
break;
case 2:
DeQueue(Q1);
print(Q1);
break;
case 3:
DestroyQueue(Q1);
print(Q1);
is_stop='#';
break;
}
}

return 0;
}

Answer 2

//---------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#define STACK 0
#define QUEUE 1

typedef int data_type;

typedef struct node
{
data_type data;
struct node *next;
} node;

typedef struct
{
node *head;
unsigned int size;
} stack;

typedef struct
{
node *front;
node *end;
unsigned int size;
} queue;

node *new_node(void)
{
node *t=malloc(sizeof(node));
if (t==NULL) {
fprintf(stderr,"new_node():\tmalloc() failed!\n");
exit(-1);
}
return t;
}
void push(stack *st,data_type dd)
{
node *t=new_node();
t->data=dd;
t->next=st->head;
st->head=t;
++st->size;
}
int stack_empty(const stack * const st)
{
return !st->size;
}
data_type pop(stack *const st)
{
data_type dd;
node *t;
if (stack_empty(st)) {
fprintf(stderr,"Stack is empty!\n");
exit(-1);
}

dd=st->head->data;
t=st->head->next;
free(st->head);
st->head=t;
--st->size;
return dd;

}

int queue_empty(const queue * const qe)
{
return !qe->size;
}
void enqueues(queue * const qe,data_type dd)
{
node *t=new_node();
t->data=dd;
t->next=NULL;
if (queue_empty(qe)) qe->front=qe->end=t;
else qe->end=qe->end->next=t;

++qe->size;
}

data_type dequeues(queue * const qe)
{
node *t;
data_type dd;
if (queue_empty(qe)) {
fprintf(stderr,"Queue is empty!\n");
exit(-1);
}
t=qe->front;
qe->front=t->next;
--qe->size;

dd=t->data;
free(t);

return dd;
}
void free_stru(void *fs,int stru_type)
{
node *t,*y;

switch (stru_type) {
case STACK:
t=((stack *)fs)->head;
break;
case QUEUE:
t=((queue *)fs)->front;
break;
}
while (t!=NULL)
{
y=t->next;
free(t);
t=y;
}
free(fs);
}

int main(void)
{
stack stk={0};
queue qe={0};
int i;
for (i=0; i < 10; i++) {
push(&stk,i);
enqueues(&qe,i);
}
puts("Stack:\n\n");
while (!stack_empty(&stk))
printf("%d ",pop(&stk));
putchar('\n');

puts("\n\nQueue:\n\n");
while(!queue_empty(&qe))
printf("%d ",dequeues(&qe));
putchar('\n');

free_stru(&stk,STACK);
free_stru(&qe,QUEUE);

return 0;
}
//---------------------------------------------------------------------------

Answer 3

楼上的大概没看清题目要求。。。

下面是程序代码，包括main()中的测试程序，
参考main()中的使用方法来使用class ArrayStackQueue

#include <iostream>
using namespace std;
class ArrayStackQueue
{
int data[100];
int top;
public:
ArrayStackQueue():top(0){};
int pop(int &i);
int push(int i);
int enqueue(int i);
int dequeue(int &i);
};
int ArrayStackQueue::push(int i)
{
if(top<100)
{
data[top++]=i;
return 0;
}
return -1;
}
int ArrayStackQueue::pop(int &i)
{
if(top==0)
return -1;
i=data[--top];
return 0;
}
int ArrayStackQueue::enqueue(int i)
{
return push(i);
}
int ArrayStackQueue::dequeue(int& i)
{
if(top==0)
return -1;
i = data[0];
top--;
for(int ii=0; ii<top; ii++)
data[ii]=data[ii+1];
return 0;
}

int main()
{
int i , j ;
ArrayStackQueue q;
for (j = 0 ;j < 102; j ++)
{
i = q.push(j);
if(i!=0)
cout<<"push/enqueue error "<<j<<endl;
}
cout<<endl<<"dequeue ";
for(j=0;j<50;j++)
{
q.dequeue(i);
cout<<i<<ends;
}
cout<<endl<<endl<<"pop ";
for(j=0;j<51;j++)
{
int k = q.pop(i);
if(k==0)
cout<<i<<ends;
else
cout<<"pop zero ";
}
cout<<endl<<endl;
if(0!=q.dequeue(i))
cout<<"dequeue zero "<<endl;
system ("pause") ;
return 0 ;
}