資訊專欄INFORMATION COLUMN
摘要：對于棧來說，這個表尾稱為棧的棧頂，相應的表頭稱為棧底。棧和隊列的區(qū)別棧的插入和刪除操作都是在一端進行的，而隊列的操作卻是在兩端進行的。出棧操作出棧操作就是在棧頂取出數(shù)據(jù)，棧頂指針隨之下移的操作。
基本概念
棧和隊列都是動態(tài)的集合，在棧中，可以去掉的元素是最近插入的哪一個。棧實現(xiàn)了后進先出。在隊列中，可以去掉的元素總是在集合中存在的時間最長的那一個。隊列實現(xiàn)了先進先出的策略。
棧的官方定義：棧（Stack）是一個后進先出（Last in first out,LIFO）的線性表，它要求只在表尾進行刪除和插入操作。對于棧來說，這個表尾稱為棧的棧頂，相應的表頭稱為棧底。入棧使用push()方法。出棧使用pop()方法。
最開始棧中不含有任何數(shù)據(jù)，叫做空棧，此時棧頂就是棧底。然后數(shù)據(jù)從棧頂進入，棧頂棧底分離，整個棧的當前容量變大。數(shù)據(jù)出棧時從棧頂彈出，棧頂下移，整個棧的當前容量變小。
我們把作用于隊列上的INSERT操作稱為入隊（Enqueue），把作用于隊列上的DELETE操作稱為出隊（Dequeue）。我們使用變量top來記錄棧頂元素的位置和標記哪里可以加入新的元素，當向棧內(nèi)壓入元素時，該變量增大；從棧內(nèi)彈出元素時，該變量減小。
棧和隊列的區(qū)別棧的插入和刪除操作都是在一端進行的，而隊列的操作卻是在兩端進行的。
typedef struct
{
ElemType *base;
ElemType *top;
int stackSize;
}sqStack;
這里定義了一個順序存儲的棧，它包含了三個元素：base,top,stackSize。
其中base是指向棧底的指針變量，top是指向棧頂?shù)闹羔樧兞?，stackSize指示棧的當前可使用的最大容量。
創(chuàng)建一個棧#define STACK_INIT_SIZE 100
initStack(sqStack *s)
{
s->base = (ElemType *)malloc( STACK_INIT_SIZE * sizeof(ElemType) );
if( !s->base )
exit(0);
s->top = s->base; // 最開始，棧頂就是棧底
s->stackSize = STACK_INIT_SIZE;
}
入棧操作
入棧操作又叫壓棧操作，就是向棧中存放數(shù)據(jù)。
入棧操作要在棧頂進行，每次向棧中壓入一個數(shù)據(jù)，top指針就要+1，知道棧滿為止。
出棧操作出棧操作就是在棧頂取出數(shù)據(jù)，棧頂指針隨之下移的操作。
每當從棧內(nèi)彈出一個數(shù)據(jù)，棧的當前容量就-1。
隊列的順序存儲結(jié)構(gòu)入隊列操作其實就是在隊尾追加一個元素，不需要任何移動，時間復雜度為O(1)。
出隊列則不同，因為我們已經(jīng)架設(shè)下標為0的位置是隊列的隊頭，因此每次出隊列操作所有元素都要向前移動。
棧的方法和屬性push()：入棧操作 pop()：出棧操作（返回棧頂元素并刪除t） peak()：返回棧頂元素而不刪除它 clear()：清除棧內(nèi)所有元素 length()：記錄棧內(nèi)元素的個數(shù) empty屬性：表示棧內(nèi)是否含有元素棧的實現(xiàn)
function Stack(){
this.dataStore = [];
this.top = 0;
this.push = push;
this.pop = pop;
this.peek = peek;
}
用一個數(shù)組dataStore來保存棧內(nèi)元素，變量top記錄棧頂位置
push()方法先來實現(xiàn)push()方法，當向棧中壓入一個新元素時，需要將其保存在數(shù)組中變量top對應的位置，然后將top值加1：
function push(element){
this.dataStore[this.top++] = element;//top值加1，指向下一個空位置
}
pop()方法
function pop(){
return this.dataStore[--this.top];//pop方法與push相反
}
peek()方法
peek方法返回數(shù)組的第一個top-1位置的元素，即棧頂元素：
function peek(){
return this.dataStore[this.top-1];
}
length()方法
length方法通過返回變量top值的方法返回棧內(nèi)的元素的個數(shù)：
function length(){
return this.top;
}
clear()方法
將變量top的值設(shè)為0，就可以清空一個棧了：
function clear(){
this.top = 0;
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/87637.html
摘要：后入先出入棧使用方法，出棧使用方法入棧出棧出站隊列隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端進行刪除操作，而在表的后端進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。 1.棧（stack） 棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入?；驂簵?..
摘要：上一篇數(shù)據(jù)結(jié)構(gòu)與算法棧隊列下一篇數(shù)據(jù)結(jié)構(gòu)與算法集合字典寫在前面說明數(shù)據(jù)結(jié)構(gòu)與算法系列文章的代碼和示例均可在此找到上一篇博客發(fā)布以后，僅幾天的時間竟然成為了我寫博客以來點贊數(shù)最多的一篇博客。 上一篇：JS數(shù)據(jù)結(jié)構(gòu)與算法_棧&隊列下一篇：JS數(shù)據(jù)結(jié)構(gòu)與算法_集合&字典 寫在前面 說明：JS數(shù)據(jù)結(jié)構(gòu)與算法 系列文章的代碼和示例均可在此找到 上一篇博客發(fā)布以后，僅幾天的時間竟然成為了我寫博客以...
閱讀 2611·2021-10-14 09:43
閱讀 3570·2021-10-13 09:39
閱讀 3304·2019-08-30 15:44
閱讀 3154·2019-08-29 16:37
閱讀 3718·2019-08-29 13:17
閱讀 2742·2019-08-26 13:57
閱讀 1834·2019-08-26 11:59
閱讀 1260·2019-08-26 11:46
