連接存儲的棧
Ⅰ 麻煩高手幫寫一個C語言連接存儲一個是棧一個是隊列
棧
#include<iostream.h>
#include<malloc.h>
#include<conio.h>
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status ;
typedef int ElemType;
struct STACK
{
ElemType *base;
ElemType *top;
int stacksize;
};
typedef struct STACK SqStack;
//typedef struct STACK *pSqstack;
//函數聲明
Status InitStack(SqStack &S);
void DestroyStack(SqStack &S);
void ClearStack(SqStack &S);
Status StackEmpty(SqStack S);
int StackLength(SqStack S);
Status GetTop(SqStack S,ElemType &e);
Status Push(SqStack &S,ElemType e);
Status Pop(SqStack &S,ElemType &e);
//初始化
Status InitStack(SqStack &S)
{
S.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S.base) return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
//銷毀棧
void DestroyStack(SqStack &S)
{
free(S.base);
}
//清空棧
void ClearStack(SqStack &S)
{
S.top=S.base;
}
//判棧空
Status StackEmpty(SqStack S)
{
if(S.top==S.base) return TRUE;
else
return FALSE;
}
//求棧中元素個數
int StackLength(SqStack S)
{
int i;
ElemType *p;
i=0;
p=S.top;
while(p!=S.base)
{p--;
i++;
}
return i;
}
//獲取棧頂元素值
Status GetTop(SqStack S,ElemType &e)
{
if(S.top==S.base) 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));
if(!S.base) return ERROR;
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;
}
//逆序列印棧中元素
void PrintElem(SqStack S)
{
ElemType e;
if(S.top==S.base) cout<<"該棧為空棧.";
else
while(S.top!=S.base)
{
Pop(S,e);cout<<e<<ends;
}
cout<<endl;
}
//進制轉換函數
void conversion()
{
SqStack S;
ElemType e;
char b[17]="0123456789ABCDEF";
int n,r;
InitStack(S);
cout<<"Input a number to convert to :\n";
cin>>n;
cout<<"請輸入要轉換的進制：";
cin>>r;
if(n<0)
{
cout<<"\nThe number must be over 0.";
return;
}
if(!n) Push(S,0);
while(n){
Push(S,n%r);
n=n/r;
}
cout<<"the result is: ";
while(!StackEmpty(S)){
Pop(S,e);
cout<<b[e];
}
cout<<endl;
}
void main()
{
ElemType e;
SqStack Sa;
cout<<"\n\n-------------------SqStack Demo is running...----------------\n\n";
cout<<"First is Push function.\n";
InitStack(Sa);
cout<<" Now Stack is Empty.\n";
cout<<"請輸入第一個要入棧的元素值：";
cin>>e;
Push(Sa,e);
cout<<"\n Now Stack has one element.\n";
PrintElem(Sa);
cout<<"請輸入第二個要入棧的元素值：";
cin>>e;
Push(Sa,e);
cout<<"\n Now Stack has another element.\n";
PrintElem(Sa);
int n;
cout<<"請輸入還要入棧的元素個數:";
cin>>n;
for(int i=1;i<=n;i++)
{
cout<<"\n請輸入第"<<i+2<<"個元素：";
cin>>e;
Push(Sa,e);
}
cout<<"\n Now Pop Stack,the top elem put into variable e.\n";
Pop(Sa,e);
cout<<e<<endl;
cout<<" Let's see the left of Stack's elem:\n";
PrintElem(Sa);
cout<<"現在棧中元素個數為："<<StackLength(Sa);
cout<<endl;
getch();
cout<<"進制轉換演示：\n";
conversion();
}
隊列
#include <iostream.h>
#include <malloc.h>
typedef int QElemType;
typedef int Status;
#define OK 1
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define MaxQsize 100 /*最大隊列長度*/
typedef struct {
QElemType *base; /*初始化的動態分配存儲空間*/
int front; /*頭指針，若隊列不空，指向隊列頭元素*/
int rear; /*尾指針，若隊列不空，指向隊列尾元素的下一個位置*/
}SqQueue;
Status InitQueue(SqQueue &Q){
/*構造一個空隊列Q*/
Q.base=(QElemType *)malloc(MaxQsize*sizeof(QElemType));
if(!Q.base) return ERROR;/*存儲分配失敗*/
Q.front=Q.rear=0;
return OK;
}
Status QueueEmpty(SqQueue Q){
/*若隊列Q為空隊列，則返回TRUE，否則返回FALSE*/
if(Q.front==Q.rear) return TRUE;
else return FALSE;
}
int QueueLength(SqQueue Q){
/*返回Q的元素個數，即為隊列的長度*/
return(Q.rear-Q.front+MaxQsize)% MaxQsize;
}
Status GetHead(SqQueue Q,QElemType &e){
/*若隊列不為空，則用e返回Q的隊頭元素，並返回OK；否則返回ERROR*/
if(Q.front==Q.rear) return ERROR;
e=Q.base[Q.front];
return OK;
}
Status EnQueue(SqQueue &Q,QElemType e){
/*插入元素e為Q的新的隊尾元素*/
if((Q.rear+1)%MaxQsize==Q.front) return ERROR;/*隊列滿*/
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MaxQsize;
return OK;
}
Status DeQueue(SqQueue &Q,QElemType &e){
/*若隊列不空，則刪除Q的隊頭元素，用e返回其值，並返回OK,否則返回ERROR*/
if(Q.rear==Q.front) return ERROR;/*隊列空*/
e=Q.base[Q.front];
Q.front=(Q.front+1)%MaxQsize;
return OK;
}
void main(){
SqQueue Q;
int select;
QElemType e;
if (InitQueue(Q)==ERROR)
cout<<"分配失敗，即將退出程序！\n";
else/*否則顯示隊列操作的菜單，並選擇相應的基本操作*/
do {
cout<<"1：判斷隊列是否為空\n";
cout<<"2：測試隊列的長度\n" ;
cout<<"3：取隊頭元素值\n";
cout<<"4：向隊列中插入一新元素\n";
cout<<"5：刪除隊列中一元素\n";
cout<<"0：結束\n";
cout<<"\n請輸入您的選擇：";
cin>>select;
cout<<endl;
switch (select) {
case 1:
if (QueueEmpty(Q)==TRUE) cout<<"隊列為空\n";
else cout<<"隊列不為空\n";break;
case 2:
cout<<"隊列長度為："<<QueueLength(Q)<<endl;break;
case 3:
if(GetHead(Q,e)==ERROR) cout<<"隊列為空\n";
else cout<<"隊首元素為："<<e<<endl;break;
case 4:
cout<<"請輸入要插入的元素值：";
cin>>e;
if(EnQueue(Q,e)==ERROR) cout<<"\n隊列滿\n";
else cout<<"\n元素成功插入\n";break;
case 5:
if(DeQueue(Q,e)==ERROR) cout<<"隊列空,無數據可刪\n";
else cout<<"刪除元素為："<<e;break;
case 0:
cout<<"操作結束\n";break;
default:
cout<<"輸入選擇出錯！\n";
}/*switch*/
cout<<endl<<endl;
}while (select);
}/*main_end*/
Ⅱ 棧的鏈式存儲
#include<stdio.h>
#include<stdlib.h>
#define
elemtype
int
#define
MAXSIZE
100
typedef
struct
stack{
elemtype
elem;
struct
stack
*next;
}STACK;
//鏈式存儲的棧結構，及其相應演算法
void
InitStack(STACK
*top)
{//初始化空棧
top->next=NULL;
}
void
DestroyStack(STACK
*top)
{//銷毀棧，將棧所佔內存空間釋放
STACK
*p;
p=top->next;
while(p!=NULL){
top->next=p->next;
free(p);
p=top->next;
}
}
int
EmptyStack(STACK
*top)
{//判斷是否棧空，為空則返回1，否則返回0
if(top->next==NULL){
return
1;
}
else{
return
0;
}
}
int
push(STACK
*top,
elemtype
x)
{//元素x進棧操作，成功返回1，否則返回0
STACK
*p;
p=(STACK
*)malloc(sizeof(STACK));
p->elem=x;
p->next=top->next;
top->next=p;
return
1;
}
elemtype
pop(STACK
*top)
{//出棧操作，返回出棧元素
if(EmptyStack(top)){
printf("棧為空");
return
0;
}
else{
elemtype
x;
STACK
*p;
p=top->next;
x=p->elem;
top->next=p->next;
free(p);
p=top->next;
return
x;
}
}
void
Print(STACK
*top)
{//依次輸出棧頂到棧底的所有元素
STACK
*h;
h=top->next;
while(h!=NULL){
printf("%4d",h->elem);
h=h->next;
}
}
int
main(void)
{
STACK
*top=NULL;
top=(STACK
*)malloc(sizeof(STACK));
InitStack(top);
push(top,1);
push(top,2);
push(top,4);
Print(top);
push(top,5);
Print(top);
pop(top);
Print(top);
DestroyStack(top);
}
Ⅲ 分別就棧的順序存儲結構和鏈式存儲結構實現棧的各種基本操作。
順序存儲結構
#include<iostream>
typedef char ElemType;
#define MaxSize 100
using namespace std;
typedef struct
{
ElemType data[MaxSize];
int top;
}sqStack;
void InitStack(sqStack *&s);//初始化棧
void ClearStack(sqStack *&s);//摧毀棧
int StackLength(sqStack *s);//返回棧的長度
bool StackEmpty(sqStack *s);//判斷棧是否為空
int Push(sqStack *&s,ElemType e);//進棧
int Pop(sqStack *&s,ElemType &e);//出棧
int GetTop(sqStack *s,ElemType &e);//取棧頂元素
void DispStack(sqStack *s);//顯示棧中元素值
int main()
{
return 0;
}
void InitStack(sqStack *&s)//初始化棧
{
s=new sqStack;
s->top=-1;
}
void ClearStack(sqStack *&s)//摧毀棧
{
delete s;
}
int StackLength(sqStack *s)//返回棧的長度
{
return (s->top+1);
}
bool StackEmpty(sqStack *s)//判斷棧是否為空
{
return (s->top==-1);
}
int Push(sqStack *&s,ElemType e)//進棧
{
if(s->top==MaxSize-1)
return 0;
s->top++;
s->data[s->top]=e;
return 1;
}
int Pop(sqStack *&s,ElemType &e)//出棧
{
if(s->top==-1)
return 0;
e=s->data[s->top];
s->top--;
return 1;
}
int GetTop(sqStack *s,ElemType &e)//取棧頂元素
{
if(s->top==-1)
return 0;
e=s->data[s->top];
return 1;
}
void DispStack(sqStack *s)//顯示棧中元素值
{
for(int i=s->top;i>=0;i--)
cout<<s->data[i]<<" ";
cout<<endl;
}
鏈式存儲結構
typedef char ElemType;
typedef struct linknode
{
ElemType data;
struct linknode *next;
}LiStack;
void InitStack(LiStack *&s);//初始化棧
void ClearStack(LiStack *&s);//摧毀棧
int StackLength(LiStack *s);//返回棧的長度
bool StackEmpty(LiStack *s);//判斷棧是否為空
void Push(LiStack *&s,ElemType e);//進棧
int Pop(LiStack *&s,ElemType &e);//出棧
int GetTop(LiStack *s,ElemType &e);//取棧頂元素
void DispStack(LiStack *s);//顯示棧中元素值
int main()
{
return 0;
}
void InitStack(LiStack *&s)//初始化棧
{
s=new LiStack;
s->next=NULL;
}
void ClearStack(LiStack *&s)//摧毀棧
{
for(LiStack *p=s->next;p;p=p->next)
{
delete s;
s=p;
p=p->next;
}
delete s;
}
int StackLength(LiStack *s)//返回棧的長度
{
int i=0;
for(LiStack *p=s->next;p;p=p->next)
i++;
return i;
}
bool StackEmpty(LiStack *s)//判斷棧是否為空
{
return (s->next==NULL);
}
void Push(LiStack *&s,ElemType e)//進棧
{
LiStack *p=new LiStack;
p->data=e;
p->next=s->next;
s->next=p;
}
int Pop(LiStack *&s,ElemType &e)//出棧
{
LiStack *p;
if(s->next==NULL)
return 0;
p=s->next;
e=p->data;
s->next=p->next;
delete p;
return 1;
}
int GetTop(LiStack *s,ElemType &e)//取棧頂元素
{
if(s->next==NULL)
return 0;
e=s->next->data;
return 1;
}
void DispStack(LiStack *s)//顯示棧中元素值
{
LiStack *p=s->next;
for(;p;p=p->next)
cout<<p->data<<" ";
cout<<endl;
}
Ⅳ 什麼叫存棧
關棧是海關的一種保稅制度，通常是指經海關准予注冊用以存儲保稅貨物的倉版庫或場所。在清季，保稅關權棧是由商人自立棧房（碼頭倉棧）改設的。關棧與商棧同是存儲貨物之所，其不同之處在於：關棧所存為未經通關的保稅待納貨物，而商棧所存則為業經通關的已稅貨物。關棧保稅，本是中國所無，亦不載於不平等條約。其請設和開辦經歷了長期抗爭與驟然讓與的矛盾過程，斗爭焦點是外國棧房准作關棧抑或中國自辦關棧。
Ⅳ 鏈棧和順序棧兩種存儲結構有什麼不同
存儲結構不同：來
鏈棧動自態分配內存存儲數據，不浪費內存，存儲的數據不連續。
順序棧使用固定大小數組保存數據，數據量小時浪費內存，過多時出問題，存儲數據連續。
它們的具體區別如下：
順序棧的實現在於使用了數組這個基本數據結構，數組中的元素在內存中的存儲位置是連續的，且編譯器要求我們在編譯期就要確定數組的大小，這樣對內存的使用效率並不高，一來無法避免因數組空間用光而引起的溢出問題。在系統將內存分配給數組後，則這些內存對於其他任務就不可用。而對於鏈棧而言，使用了鏈表來實現棧，鏈表中的元素存儲在不連續的地址，由於是動態申請內存，所以我們可以以非常小的內存空間開始，另外當某個項不使用時也可將內存返還給系統。
Ⅵ C語言鏈式存儲棧的建棧、入棧、出棧、列印
你在main里調用InitStack初始化棧，後面就可以Push Pop進出了
Ⅶ 棧的鏈式存儲結構--出棧操作
#include
#include
#define
elemtype
int
#define
maxsize
100
typedef
struct
stack{
elemtype
elem;
struct
stack
*next;
}stack;
//鏈式存儲的棧結構，及其相應演算法
void
initstack(stack
*top)
{//初始化空棧
top->next=null;
}
void
destroystack(stack
*top)
{//銷毀棧，將棧所佔內存空間釋放
stack
*p;
p=top->next;
while(p!=null){
top->next=p->next;
free(p);
p=top->next;
}
}
int
emptystack(stack
*top)
{//判斷是否棧空，為空則返回1，否則返回0
if(top->next==null){
return
1;
}
else{
return
0;
}
}
int
push(stack
*top,
elemtype
x)
{//元素x進棧操作，成功返回1，否則返回0
stack
*p;
p=(stack
*)malloc(sizeof(stack));
p->elem=x;
p->next=top->next;
top->next=p;
return
1;
}
elemtype
pop(stack
*top)
{//出棧操作，返回出棧元素
if(emptystack(top)){
printf("棧為空");
return
0;
}
else{
elemtype
x;
stack
*p;
p=top->next;
x=p->elem;
top->next=p->next;
free(p);
p=top->next;
return
x;
}
}
void
print(stack
*top)
{//依次輸出棧頂到棧底的所有元素
stack
*h;
h=top->next;
while(h!=null){
printf("%4d",h->elem);
h=h->next;
}
}
int
main(void)
{
stack
*top=null;
top=(stack
*)malloc(sizeof(stack));
initstack(top);
push(top,1);
push(top,2);
push(top,4);
print(top);
push(top,5);
print(top);
pop(top);
print(top);
destroystack(top);
}
Ⅷ 棧的鏈式存儲結構是什麼
若是棧中元素的數目變化范圍較大或不清楚棧元素的數目，就應該考慮使用鏈式存專儲結構。人們將用鏈式屬存儲結構表示的棧稱作「鏈棧」。鏈棧通常用一個無頭結點的單鏈表表示。由於棧的插入、刪除操作只能在一端進行，而對於單鏈表來說，在首端插入、刪除結點要比在尾端進行相對容易一些，所以將單鏈表的首端作為棧的頂端，即將單鏈表的頭指針作為棧頂指針。鏈棧如圖1所示。
圖1鏈棧的存儲示意
Ⅸ 棧的兩種存儲表示方法
棧的存儲結構
順序棧
和線性表類似，堆棧也有兩種基本的存儲結構：版順序存儲結構和鏈權式存儲結構。
順序棧是使用順序存儲結構實現的堆棧，即利用一組地址連續的存儲單元依次存放堆棧中的數據元素。
由於堆棧是一種特殊的線性表，因此在線性表的順序存儲結構的基礎上，選擇線性表的一端作為棧頂即可。
根據數組操作的特性，選擇數組下標大的一端，即線性表順序存儲的表尾來作為棧頂，此時入棧、出棧等操作可以在Ο(1)時間完成。
由於堆棧的操作都在棧頂完成，因此在順序棧的實現中需要附設一個指針 top 來動態的指示棧頂元素在數組中的位置。
通常 top 可以用棧頂元素所在數組下標來表示，top= -1 時表示空棧。
鏈棧
鏈棧即採用鏈表作為存儲結構實現的棧。
當採用單鏈表存儲線性表後，根據單鏈表的操作特性選擇單鏈表的頭部作為棧頂，此時，入棧、出棧等操作可以在Ο(1)內完成。
由於堆棧的操作只在線性表的一端進行，在這里使用帶頭結點的單鏈表或不帶頭結點的單鏈表都可以。
使用帶頭結點的單鏈表時，結點的插入和刪除都在頭結點之後進行；
使用不帶頭結點的單鏈表時，結點的插入和刪除都在鏈表的首結點上進行。
Ⅹ 棧的順序存儲和鏈表存儲的差異
順序存儲： 線性表的順序表：指的是用一組地址連續的存儲單元，依次存儲線性表的數據元素。
線性表的順序存儲結構具備如下兩個基本特徵： 1、線性表中的所有元素所佔的存儲空間是連續的（即要求內存中可用存儲單元的地址必須是連續的）。 2、線性表中各數據元素在存儲空間中是按邏輯順序依次存放的。 即：線性表邏輯上相鄰、物理也相鄰（邏輯與物理統一：相鄰數據元素的存放地址也相鄰），則已知第一個元素首地址和每個元素所佔位元組數，則可求出任一個元素首地址。 優點： 1、
無須為表示結點間的邏輯關系而增加額外的存儲空間。
2、
可以方便的隨機存取表中的任一結點。
3、
存儲密度大（＝1），存儲空間利用率高。 缺點： 1、
插入和刪除運算不方便，需移動大量元素。 2、
由於要求佔用連續的存儲空間，存儲分配只能按最大存儲空間預先進行，致使存儲空間不能得到充分利用。
3、
表的容量難以擴充。 鏈表存儲： 線性表的鏈式存儲：指用一組任意的存儲單元存儲線性表中的數據元素。
線性表的鏈式存儲結構具備的基本特徵： 鏈式存儲時，相鄰數據元素可隨意存放，但所佔存儲空間分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針。 優點： 1、
插入、刪除操作很方便，可通過修改結點的指針實現，無須移動元素。
2、
方便擴充存儲空間。
缺點： 1、
不能隨機存取元素。
2、
存儲密度小（<1），存儲空間利用率低。 總結： 1、
順序表適宜於做查找這樣的靜態操作；
鏈表宜於做插入、刪除這樣的動態操作。 2、若線性表的長度變化不大，且其主要操作是查找，則採用順序表； 若線性表的長度變化較大，且其主要操作是插入、刪除操作，則採用鏈表。