棧 定義棧和隊列都是重要的線性結構，即在使用層面上收到限制而發(fā)揮特殊作用的線性表。掌握這兩種結構在不同情景下亦會發(fā)揮重要作用。
成都創(chuàng)新互聯(lián)公司主要從事網站設計制作、成都做網站、網頁設計、企業(yè)做網站、公司建網站等業(yè)務。立足成都服務平頂山,十載網站建設經驗,價格優(yōu)惠、服務專業(yè),歡迎來電咨詢建站服務:18980820575
棧保持著后進先出的原則，正因如此在插入數據的時候要求只能從一段插入，稱為棧頂；相反另一端就被稱為棧底。而插入數據叫做進棧，刪除數據叫做出棧，并且都只能在棧頂進行操作。
了解了棧的定義，現在就應著手于如何實現。應考慮清楚根據其性質我們要構造出一個怎樣的結構來實現棧。
我們需要在一端插入或刪除數據并及時對其訪問，因此我們這里使用動態(tài)順序表來實現。在這個結構中?top?由于初始值設定為?0?所以代表的是棧頂下一位的下標，也可以設置為-1，則代表的是棧頂的下標。使用capacity是為了時刻檢測內存的大小便于及時開辟。
這次要實現的就是下面幾個函數，對應了該數據結構時經常使用的操作。
初始化首先為內部儲存的數據開辟一段空間，(這里我設置的初始值是4根據需要可以進行調整)，開辟成功后，用結構體內的指針指向這片空間，同時為?top?與?capacity?賦上初始值。這樣便完成了棧的初始化。
入棧
一切開始前首先應該判斷傳入的指針是否為空指針，避免出現對空指針解引用的情況。后判斷這個空間是否已滿，不然增大空間的容量。之前說過?top?指向的是棧頂的下一位，因此直接賦值后再對?top ++?就可以了。
這里對容量的判定是分解到另一個函數內去的，其實直接寫這個函數里面也是可以的畢竟只有這里需要判斷容量是否滿了。
從下標的角度上來說，top?是比棧頂多?1?的，由于下標的從?0?開始因此?top?正好可以表達此刻數據的數量。當?top 與?capacity?相等時，即開辟的空間已滿。所以使用?realloc?調整新空間的大小(我把默認設為每次增加都是原來的兩倍)。開辟成功后把新的地址給?data?，調整?capacity?為新容量的大小。
出棧
出棧的操作相當的簡便，只要?top--?這樣未來訪問的時候就不會再訪問到，也沒有必要再對其進行賦值，因為下次插入的時候就會用新值覆蓋原來的值。但是斷言還是要記得斷言的。
獲取棧頂元素
這里我們通過top訪問到棧頂的元素之后并將其返回，就完成了棧頂元素的獲取。
這里使用了?bool?值要引用頭文件?stdboo.h?，前面講到?top?在棧中的意義就相當于內置數據的數量，即?top?不等于?0?則棧里就是還有數據的，所以返回false。
棧結束使用后，要進行銷毀避免內存泄漏。斷言后釋放data 后再將top跟capacity賦值為初始值，由于前面沒有對結構體進行動態(tài)開辟，所以這里就不用釋放。
隊列與棧相反，棧是先進后出，而隊列是先進先出，即從隊頭入隊(插入數據)到隊尾出隊(刪除數據)，這個規(guī)則無法改變。
在這里關于結構的選擇就不是雙選題了，因為無論選左邊還是右邊作為隊尾，數組總是逃不過需要挪動數據的結果。反觀鏈表就顯得相對自由。
但只使用鏈表結構也不夠完善，對于鏈表來說最痛苦的莫非是尾結點的訪問了，但這里要頻繁地對尾節(jié)點進行訪問，不妨再使用一個結構體存儲頭尾結點，來表示一整個隊列。這樣處理后，若我們要對頭結點進行更改也不需要使用到二級指針了，因為只是對結構體內的數據進行更改因此只需要結構體指針。為了統(tǒng)計大小更加方便也需要一個?size?表示大小。
如下為要實現的函數。
一開始的隊列本為空，只需要將頭尾結點制空，?size?歸零。就完成了插入數據前的準備。
為空的判定就相對簡單，頭尾結點正常情況下是同時為空的，也為了避免特殊情況即二者其中一個為空就可以判斷整個隊列是空的。
入隊
傳入數值前先斷言(養(yǎng)成好習慣)，之后像鏈表那樣開辟一個新節(jié)點并對其賦值。之后就要面臨一個分岔口，隊列是否為空，貿然地對頭結點解引用就會出現錯誤，若為空則新節(jié)點就變成頭結點，非空就鏈接在尾結點后，這之后自身成為尾結點。
出隊
斷言后出隊需要做到的是：事先將下一結點保存起來，不然當前頭結點釋放后便無法訪問到下一結點了。之后釋放頭結點，下一結點就變成了頭結點，同時?size--?，保證空間數量的準確避免越界訪問。
訪問隊頭隊尾
直接訪問頭(尾)結點便是隊頭(尾)。
這里需要感謝我們在前面在結構內就存儲了大小，不然還需要遍歷鏈表才能得到隊列的大小。
同樣有?malloc?就有?free ，在這里我們每個結點都是動態(tài)開辟出來的，所以都需要釋放。就像鏈表釋放那樣，一邊遍歷一邊釋放。最后再把隊列的結構體初始化就完成了。
好了，這次棧和隊列的實現到這里就告一段落了。后面是這次的源碼
源碼stack.h
重慶分公司
重慶分公司
#pragma once
#include#include#include
#includetypedef int STdatatype;
typedef struct Stack
{
STdatatype* data;
int top;
int capacity;
}Stack;
//初始化
void StackInit(Stack* p);
//入棧
void StackPush(Stack* p, STdatatype data);
//依次出棧打印
void Stackprint(Stack* p);
//出棧
void StackPop(Stack* p);
//獲取頂端元素
STdatatype StackTop(Stack* p);
//有效數據的個數
int StackSize(Stack* p);
//檢測棧是否為空，不為空則返回0
bool StackEmpty(Stack* p);
//銷毀棧
void StackDestroy(Stack* p); stack.c
#include"stack.h"
void checkcapacity(Stack* p)
{
STdatatype* newp;
if (p->top == p->capacity)
{
newp = (STdatatype*)realloc(p->data, sizeof(Stack) * p->capacity * 2);
if (newp == NULL) //開辟失敗返回
{
perror(realloc);
exit(-1);
}
p->data = newp; //把新開辟的空間給data
p->capacity *= 2; //調整capacity為新值
}
}
void StackInit(Stack* p)
{
STdatatype* np = (STdatatype*)malloc(sizeof(STdatatype) * 4); //開辟空間初始值為4
if (np)
{
p->data = np; //不為空賦值
}
p->top = 0; //賦初值
p->capacity = 4;
}
void StackPush(Stack* p, STdatatype x)
{
assert(p); //斷言不為空
checkcapacity(p); //判斷空間是否滿了
(p->data)[p->top] = x; //賦值
p->top++;
}
void Stackprint(Stack* p)
{
int i = p->top - 1;
while (i >= 0)
{
printf("%d ", (p->data)[i--]);
}
printf("\n");
}
void StackPop(Stack* p)
{
assert(p); //斷言p不為空指針
assert(p->top); //斷言棧內數據不為空
p->top--;
}
STdatatype StackTop(Stack* p)
{
assert(p); //斷言
int top = p->top - 1; //找到棧頂
return (p->data)[top]; //返回棧頂的數值
}
bool StackEmpty(Stack* p)
{
assert(p);
if (p->top != 0)
{
return false;
}
return true;
}
void StackDestroy(Stack* p)
{
assert(p); //斷言
assert(p->data);
free(p->data); //釋放數據
p->data = NULL; //對data制空
p->top = 0; //回歸初始值
p->capacity = 0;
}queue.h
#pragma once
#include#include
#include#includetypedef int Qdatatype;
typedef struct Qnode
{
Qdatatype data; //數據
struct Queue* next; //指向下個結點
}Qnode;
typedef struct Queue
{
Qnode* head; //隊列的頭
Qnode* tail; //隊列的尾
int size; //大小
}Queue;
void Queueinit(Queue* p); //初始化
void Queuepush(Queue* p, Qdatatype x); //入隊
void Queuepop(Queue* p); //出隊
bool QueueEmpty(Queue* p); //檢測為空
Qdatatype Queuefront(Queue* p); //訪問隊頭的數據
Qdatatype Queueback(Queue* p); //訪問隊尾的數據
int Queuesize(Queue* p); //求隊列的大小 queue.c
#include "queue.h"
void Queueinit(Queue* p)
{
p->head = NULL; //頭尾結點制空
p->tail = NULL;
p->size = 0; //數據量為0
}
bool QueueEmpty(Queue* p)
{
assert(p);
return p->head == NULL || p->tail == NULL; //二者一個為空則隊列為空
}
void Queuepush(Queue* p, Qdatatype x)
{
assert(p); //斷言
Qnode* newnode = (Qnode*)malloc(sizeof(Qnode)); //開辟新結點
if (newnode == NULL) //開辟失敗返回
{
perror(malloc);
exit(-1);
}
newnode->data = x; //賦值
newnode->next = NULL;
if (p->head == NULL) //隊列為空的情況
{
p->head = p->tail = newnode;
}
else
{
p->tail->next = newnode; //鏈接
p->tail = newnode;
}
p->size++; //對size進行處理
}
void Queuepop(Queue* p)
{
assert(p); //斷言p不為空
assert(!QueueEmpty(p)); //斷言隊列不為空
Qnode* next = p->head->next; //存儲下一結點
free(p->head); //釋放當先頭結點
p->head = next; //下一結點變成頭結點
p->size--; //對size進行處理
}
Qdatatype Queuefront(Queue* p)
{
assert(p);
assert(!QueueEmpty(p)); //斷言不為空
return p->head->data; //頭結點存儲的就是隊頭的數據
}
void QueueDestroy(Queue* p)
{
assert(p);
Qnode* cur = p->head;
while (cur)
{
Qnode* next = cur->next;
free(cur);
cur = next;
}
p->head = p->tail = NULL; //頭尾結點制空
p->size = 0; //大小歸0
}
Qdatatype Queueback(Queue* p)
{
assert(p);
assert(!QueueEmpty(p));
return p->tail->data; //尾結點存儲的就是隊尾的數據
}
int Queuesize(Queue* p)
{
assert(p);
return p->size;
}
你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧
