1. 簡述棧和隊列的順序存儲結構和鏈式存儲結構的優缺點
順序棧--入棧操作受數組上界的約束有可能發生棧上溢，且需要地址連續的存儲單元。
鏈棧--無須地址連續，便於多個棧共享存儲單元，且不存在棧滿上溢情況。
順序隊列--需地址連續且有假上溢現象（需改為循環隊列才可解決假上溢）
鏈式隊列--特別適合於數據元素變動比較大的情況，且不存在隊列滿而產生的溢出問題。
2. 棧的存儲結構
棧同順序表和鏈表一樣，棧也是用來存儲邏輯關系為 "一對一" 數據的線性存儲結構。
棧的具體實現
棧是一種 "特殊" 的線性存儲結構，因此棧的具體實現有以下兩種方式：
順序棧：採用順序存儲結構可以模擬棧存儲數據的特點，從而實現棧存儲結構；
鏈棧：採用鏈式存儲結構實現棧結構；
棧存儲結構與之前所學的線性存儲結構有所差異，這緣於棧對數據 "存" 和 "取" 的過程有特殊的要求：
棧只能從表的一端存取數據，另一端是封閉的；
在棧中，無論是存數據還是取數據，都必須遵循"先進後出"的原則，即最先進棧的元素最後出棧。
通常，棧的開口端被稱為棧頂；相應地，封口端被稱為棧底。因此，棧頂元素指的就是距離棧頂最近的元素。
3. 急！用c語言實現鏈棧的操作
typedef struct node
{ ElemType data;
struct node *next;
} LinkStack;
⑴置空棧
void InitLinkStack（ LinkStack * & s）
{ s=NULL;
}
⑵判棧空
int IsEmptyLinkStack（LinkStack *s ）
{ if（s==NULL）
return 1;
else
return 0;
}
⑶ 入棧/*將元素x插入鏈棧top的棧頂*/
void PushLinkStack（LinkStack* &s , ElemType x）
{ LinkStack *p;
p=malloc(sizeof(LinkStack)); /*生成新結點*s */
p->data=x;
p->next=s;
s=p;
}
⑷出棧/*刪除鏈棧top的棧頂結點*/
int PopLinkStack (LinkStack* & s, ElemType &x)
{ LinkStack *p;
if（s==NULL） return 0;
x = s->data; /*將棧頂數據存入*x */
p = s; /*保存棧頂結點地址*/
s = s->next; /*刪除原棧頂結點*/
free (p); /*釋放原棧頂結點*/
return 1; /*返回新棧頂指針*/
}
（5） 取棧頂元素
int GetLinkStackTop (LinkStack* s, ElemType &x)
{
if（s==NULL） return 0;
x = s->data; /*將棧頂數據存入*x */
return 1; /*返回新棧頂指針*/
}
主函數怎麼寫吧
4. c語言鏈表問題
鏈式存儲結構就是鏈表。
單鏈表是只有一個方向的鏈式存儲結構。
單鏈表實現棧的意思就是用單向鏈式存儲結構實現棧，但是注意，頭結點作為棧頂，這樣出棧入棧操作的時間復雜度是O(1)，如果頭結點作為棧底則需要遍歷整個鏈表。
鏈式存儲結構有很多種，單鏈表、雙鏈表、十字鏈表等，一般用到的確實就只有兩種，就是單和雙，但是細分又可分為帶或不帶頭結點，是否是循環鏈表等。
棧和隊列是受限的線性表，有其特殊用途，隨著學習的深入你就知道了，比方說計算表達式，就用到了棧（操作符棧和操作數棧），避免了很多誤操作，直接用鏈表當然也可以，但是不保險，可能會誤操作或被別有用心的人利用。
5. C語言棧和隊列問題：停車場停車問題
#ifndef__PLOT_H__#define__PLOT_H__#defineFALSE0#defineTRUE1#defineMONEY1//單價可以自己定義#defineMAX_STOP10#defineMAX_PAVE100//存放汽車牌號typedefstruct{
inttime1;//進入停車場時間
inttime2;//離開停車場時間
charplate[10];
//汽車牌照號碼，定義一個字元指針類型}Car;//停放棧typedefstruct{
CarStop[MAX_STOP-1];//各汽車信息的存儲空間
inttop;//用來指示棧頂位置的靜態指針}Stopping;//等候隊列typedefstruct{intcount;//用來指示隊中的數據個數
CarPave[MAX_PAVE-1];//各汽車信息的存儲空間
intfront,rear;//用來指示隊頭和隊尾位置的靜態指針}Pavement;//讓路棧typedefstruct{
CarHelp[MAX_STOP-1];//各汽車信息的存儲空間
inttop;//用來指示棧頂位置的靜態指針}Buffer;
Stoppings;
Pavementp;
Bufferb;
Carc;charC[10];voidstop_pave();//車停入便道voidcar_come();//車停入停車位voidstop_to_buff();//車進入讓路棧voidcar_leave();//車離開voidwelcome();//主界面函數voidDisplay();//顯示車輛信息#
源文件PLot.c
#include"PLot.h"#include<stdio.h>#include<time.h>//包含時間函數的頭文件#include<string.h>#include<stdlib.h>voidstop_to_pave()//車停入便道{//判斷隊滿
if(p.count>0&&(p.front==(p.rear+1)%MAX_PAVE))
{printf("便道已滿，請下次再來
");
}else
{strcpy(p.Pave[p.rear].plate,C);
p.rear=(p.rear+1)%MAX_PAVE;//隊尾指示器加1
p.count++;//計數器加1
printf("牌照為%s的汽車停入便道上的%d的位置
",C,p.rear);
}
}voidcar_come()//車停入停車位{printf("請輸入即將停車的車牌號:");//輸入車牌號
scanf("%s",&C);if(s.top>=MAX_STOP-1)//如果停車位已滿，停入便道
{
stop_to_pave();//停車位->便道函數
}else
{
s.top++;//停車位棧頂指針加1
time_tt1;longintt=time(&t1);//標記進入停車場的時間
char*t2;
t2=ctime(&t1);//獲取當前時間
c.time1=t;strcpy(s.Stop[s.top].plate,C);//將車牌號登記
printf("牌照為%s的汽車停入停車位的%d車位,當前時間:%s
",C,s.top+1,t2);
}return;
}voidstop_to_buff()//車進入讓路棧{//停車位棧壓入臨時棧，為需要出棧的車輛讓出道
while(s.top>=0)
{
if(0==strcmp(s.Stop[s.top--].plate,C))
{break;
}//讓出的車進入讓路棧
strcpy(b.Help[b.top++].plate,s.Stop[s.top+1].plate);printf("牌照為%s的汽車暫時退出停車位
",s.Stop[s.top+1].plate);
}
b.top--;//如果停車位中的車都讓了道，說明停車位中無車輛需要出行
if(s.top<-1)
{printf("停車位上無此車消息
");
}else
{printf("牌照為%s的汽車從停車場開走
",s.Stop[s.top+1].plate);
}//將讓路棧中的車輛信息壓入停車位棧
while(b.top>=0)
{strcpy(s.Stop[++s.top].plate,b.Help[b.top--].plate);printf("牌照為%s的汽車停回停車位%d車位
",b.Help[b.top+1].plate,s.top+1);
}//從便道中->停車位
while(s.top<MAX_STOP-1)
{if(0==p.count)//判斷隊列是否為空
{break;
}//不為空，將便道中優先順序高的車停入停車位
else
{strcpy(s.Stop[++s.top].plate,p.Pave[p.front].plate);printf("牌照為%s的汽車從便道中進入停車位的%d車位
",p.Pave[p.front].plate,s.top+1);
p.front=(p.front+1)%MAX_PAVE;
p.count--;
}
}
}voidcar_leave()//車離開{printf("請輸入即將離開的車牌號:
");scanf("%s",&C);if(s.top<0)//判斷停車位是否有車輛信息
{printf("車位已空，無車輛信息！
");
}else
{
stop_to_buff();
}
time_tt1;
longintt=time(&t1);
c.time2=t;//標記離開停車場的時間
char*t2;
t2=ctime(&t1);//獲取當前時間
printf("離開時間%s
需付%ld元
",t2,MONEY*(c.time2-c.time1)/10);
}voidDisplay()
{inti=s.top;if(-1==i)
{printf("停車場為空
");
}
time_tt1;longintt=time(&t1);//標記顯示時的時間
printf(" 車牌號 停放時間 當前所需支付金額
");while(i!=-1)
{
printf(" %s %d秒 %d元
",s.Stop[i].plate,t-c.time1,MONEY*(t-c.time1)/10);
i--;
}
}voidwelcome()
{printf(" *******************目前停車場狀況***********************
");printf(" 停車場共有%d個車位,當前停車場共有%d輛車,等候區共有%d輛車
",MAX_STOP,s.top+1,(p.rear+MAX_PAVE-p.front)
%MAX_PAVE);printf(" ********************************************************
");printf(" ---------------WelcometoourCarParking---------------
");
printf(" *1.Parking*
");
printf(" *2.leaving*
");
printf(" *3.situation*
");
printf(" *4.exit*
");
printf(" --------------------------------------------------------
");
}
主函數main.c
/**********************************************************
問題描述：停車場是一個能放n輛車的狹長通道，只有一個大門，
汽車按到達的先後次序停放。若車場滿了，車要在門外的便道上等候
，一旦有車走，則便道上第一輛車進入。當停車場中的車離開時，由
於通道窄，在它後面的車要先退出，待它走後依次進入。汽車離開
時按停放時間收費。
基本功能要求：
1）建立三個數據結構分別是：停放隊列，讓路棧，等候隊列
2）輸入數據模擬管理過程，數據（入或出，車號）。
***********************************************************/#include"PLot.h"intmain()
{//初始化
s.top=-1;
b.top=0;
p.rear=0;
p.count=0;
p.front=0;while(1)
{
system("clear");
welcome();inti,cho;
scanf("%d",&i);if(1==i)car_come();
if(2==i)car_leave();if(3==i)Display();if(4==i)break;
printf("返回請輸入1
");
scanf("%d",&cho);if(1==cho)
{continue;
}else
{
printf("您的輸入有誤，請重新輸入
");
scanf("%d",&cho);continue;
}
}return0;
}
6. 棧的鏈式存儲結構
int initstack(stack &s) 建堆棧
{
s.base=(char *)malloc(100*sizeof(char));
if(!s.base) exit(0);
s.top=s.base;
s.stacksize=100;
return 1;
}
int push(stack &s,char e)
{
if(s.top-s.base>=s.stacksize)
{
s.base=(char *)realloc(s.base,(s.stacksize+10)*sizeof(char));
if(!s.base) exit(0);
s.top=s.base+s.stacksize;
s.stacksize+=10;
}
*s.top++=e;
}
int pop(stack &s,char &e)
{
if(s.top==s.base) exit(0);
e=*--s.top;
return 1;
}
參考下
7. 棧的鏈式存儲結構--出棧操作
#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);
}