是什么
棧和隊列是2種重要的線性結(jié)構(gòu)。
- 從數(shù)據(jù)結(jié)構(gòu)看斯嚎，棧和隊列也是線性表利虫，其特殊性在于它們的操作受限，可以當(dāng)成操作受限的線性表堡僻。
- 從數(shù)據(jù)類型看列吼，它們是和線性表大不相同的2類重要的抽象數(shù)據(jù)類型。在面向?qū)ο蟮某绦蛟O(shè)計中苦始，它們是多型數(shù)據(jù)類型寞钥。
棧的定義和常用方法的實現(xiàn)
- 棧（Stack）是限定僅在表尾進(jìn)行插入或者刪除操作的線性表。通常陌选，表尾端稱為棧頂（top）,表頭稱為棧底（bottom）;不包含元素的空表稱為空棧理郑。
- 棧的修改是按“后進(jìn)先出”的原則進(jìn)行的
- 棧的存儲結(jié)構(gòu)
- 順序存儲結(jié)構(gòu)
- 鏈?zhǔn)酱鎯Y(jié)構(gòu)
順序棧（順序存儲結(jié)構(gòu)）
- 是利用一組連續(xù)的存儲單元一次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時設(shè)定指針top指示棧頂?shù)臄?shù)據(jù)元素咨油，同時設(shè)定指針top指示棧頂元素的位置您炉。空棧的棧頂指定值為NULL役电，
實現(xiàn)順序棧的常見操作
- Inistack(stack),初始化話一個線性堆棧赚爵，即可返回一個Javascript數(shù)組聲明。
function Inistack(stack) {
stack = new Array();
return stack;
}
- Empty(stack),判斷線性堆棧是否為空法瑟。
function Empty(stack) {
var returnValue = false;
if (stack.length == 0) returnValue = true;
return returnValue;
}
- Push(stack, x),壓入棧操作,將x元素追加放到存儲線性堆棧的數(shù)組的最后冀膝。
function Push(stack,x){
var returnValue = 0;
var stackLength = stack.length;
stack[stackLength] = x;
return stackLength;
}
- Pop(stack),彈出棧操作。即將存儲線性堆棧的數(shù)組的最后一個元素值返回霎挟，并將數(shù)組長度減1.
// 彈出線性堆棧操作
function Pop() {
var returnValue = null;
var stackLength = stack.length;
if(stackLength >= 1) {
returnValue = stack[stackLength-1];
stack.length = stackLength - 1; // 減少元素個數(shù)
}
return returnValue;
}
- Gettop(stack),獲取棧頂元素的值窝剖，即將存儲線性堆棧的數(shù)組的最后一個元素值返回即可
function Gettop() {
var returnValue = null;
var stackLength = stack.length;
returnValue = stack[stackLength-1];
return returnValue;
}
- Clear(stack),清空線性堆棧操作。即將存儲線性堆棧的數(shù)組的長度設(shè)置為0即可
// 清空線性堆棧
function Clear(stack) {
stack.length = 0;
return true;
}
- Current_size(stack),獲得線性堆棧的當(dāng)前大小酥夭。即將存儲線性堆棧的數(shù)組的長度返回即可
function Current_size(stack) {
return stack.length;
}
范例
假設(shè)要做一個文本錄入程序赐纱，為了使程序簡單，我們規(guī)定程序只能輸入26個字母熬北，還能使用回退鍵刪除一個字母疙描。例如，在鍵盤上輸入如下字符序列： "chii<nai<",其中<表示回退鍵讶隐，最后輸出的應(yīng)該是"china"起胰。為此需要設(shè)置一個線性棧來保存從鍵盤上錄入的信息。每當(dāng)從鍵盤上錄入一個非回退鍵時整份，就將該字符串壓入堆棧待错，如果從鍵盤上輸入一個回車鍵，則從堆棧中彈出一個字符烈评。最后在線性堆棧中的就是所需要錄入的正確信息火俄。
var input_stack = new Array();
function key_input(event, stack) {
if(((event.keyCode>=65)&&(event.keyCode<=90)) || (event.keyCode==8)) {
if(event.keyCode == 8) {
Pop(stack);
} else {
Push(stack, keyCode2Char(event.keyCode));
}
}
printStack(stack);
}
// 打印一個線性堆棧的值
function printStack(stack) {
var printMsg = "";
for(var i = 0; i < stack.length; i++) {
printMsg = printMsg + "' " + stack[i] + " , ";
}
alert(printMsg);
}
// 將keyCode轉(zhuǎn)換為字符的函數(shù)
function keyCode2Char(keycode) {
var charArray = "a, b , c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z".split(", ");
return charArray[keyCode-65];
}
分糖果
排排坐，分糖果讲冠。
我們買了一些糖果 candies瓜客，打算把它們分給排好隊的 n = num_people 個小朋友。
給第一個小朋友 1 顆糖果竿开，第二個小朋友 2 顆谱仪，依此類推，直到給最后一個小朋友 n 顆糖果否彩。
然后疯攒，我們再回到隊伍的起點(diǎn)，給第一個小朋友 n + 1 顆糖果列荔，第二個小朋友 n + 2 顆敬尺，依此類推，直到給最后一個小朋友 2 * n 顆糖果贴浙。
重復(fù)上述過程（每次都比上一次多給出一顆糖果砂吞，當(dāng)?shù)竭_(dá)隊伍終點(diǎn)后再次從隊伍起點(diǎn)開始），直到我們分完所有的糖果崎溃。注意蜻直，就算我們手中的剩下糖果數(shù)不夠（不比前一次發(fā)出的糖果多），這些糖果也會全部發(fā)給當(dāng)前的小朋友袁串。
返回一個長度為 num_people概而、元素之和為 candies 的數(shù)組，以表示糖果的最終分發(fā)情況（即 ans[i] 表示第 i 個小朋友分到的糖果數(shù)）囱修。
/**
* @param {number} candies
* @param {number} num_people
* @return {number[]}
*/
var distributeCandies = function(candies, num_people) {
var arr = new Array(num_people).fill(0);
var n = 1
while(candies!==0) {
for (let i = 0; i< arr.length; i++) {
if(candies-n > 0) {
arr[i] += n;
candies = candies-n
n++;
} else {
arr[i] += candies;
candies = 0;
}
}
}
return arr;
};
